[Jungol] 동맹 ( World CodeSprinter 13 Competitve Teams )

문제

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2492&sca=50

풀이

일단, 1번 항목에 대한 것은 풀이하지 않겠다. 그 이유는, 단순한 유니온-파인드 자료구조이기 때문이다.

유니온-파인드에 대해 궁금하다면 다음과 같은 사이트를 참조하자.

http://bowbowbow.tistory.com/26

http://koosaga.com/6

다음은 문제가 되는 2번 과정이다.

2번의 c=0일 때는 현재 존재하는 모든 팀들의 쌍의 개수이기 때문에, c=0일때는 무시하고 생각한다.

2번 과정의 간단한 O(nq) 풀이는 다음과 같다.

크기가 1~N인 배열을 만들어놓고, 1번을 수행할 때 동시에 size를 빼고 더해준다.

예를 들어 크기가 4인것들과 크기가 6인것들이 동맹을 맞으면,

인덱스가 4인것과 6인것들을 빼고, 10인것들에 하나를 더하는 식으로 진행한다.

그리고, 2번 쿼리가 들어오면, 투포인터 기법을 통해서 더하고 곱하고 하는 식으로 진행하는 것이다.

이 경우 한 쿼리당 투포인터가 1~N까지 다 꿰고 다니므로 O(2N)=O(N)이 되고, q개의 쿼리가 들어오면 O(NQ)가 된다.

하지만, N과 Q가 10만과 20만이기 때문에 뚝배기 깨지고 남는다.

따라서, 우리는 코드를 개선해야한다.

우리는 여기서, 하나를 관찰할 수 있다.

바로 길이가 서로 다른 것들이 아무리 많아봤자 개밖에 없다는 것이다.

증명은 다음과 같다.

길이가 서로 다른 것들이 최대한 많이 있기 위해서는, 길이가 서로 다른 것들이 1개씩해서 계속 배치된다고 생각하는게 맞다.

또한, 총 팀의 수는 정해져있으므로, 최대한 많이 만들기 위해서는 길이를 짧게 해야한다.

따라서, 1부터 차례대로 시작해서 최대 어디까지 가느냐를 보면 된다.

최대까지 가는 개수를 d라고 하자

그러면, 을 만족하는 최대의 d가 우리가 원하는 숫자임을 알 수 있다.

시그마의 간단한 공식으로 풀어써보면  을 유도해낼 수 있고, 이를 통해 임을 알 수 있다.

Q.E.D

바로, 크기가 0개인것짜리는 우리는 볼 필요가 없다는 것이고, 이것들만 없애면 의 시간에 한 쿼리를 처리할 수 있음을 알 수 있다.

과연 어떻게 이러한 원소들을 처리할까? 바로 이 때 우리는 set과 map을 사용할 수 있다!!

set또는 map을 통해서 만약 동맹을 통해 크기가 0인 것들이 생겨나면 erase 연산을 하고, 추가가 되면 insert 연산을 하면 된다.

정해에서는 set을 썼는데, map을 통해서 관리하는것도 상관없다. 

map을 통해서 내가 세었던게 0이라면 erase 연산을 해주면 된다.

이를 통해 구현한 코드는 다음과 같다

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q,cnt[100007],par[100007];
map<int,int> mp;
int findu(int x)
{
    return x==par[x] ? x : (par[x]=findu(par[x]));
}
int main()
{
    scanf("%d %d",&n,&q);
    mp[1]=n;
    for(int i=1;i<=n;i++) cnt[i]=1,par[i]=i;
    int totuni=n;
    while(q--)
    {
        int Q; scanf("%d",&Q);
        if(Q==1)
        {
            int x,y; scanf("%d %d",&x,&y);
            x=findu(x),y=findu(y);
            if(x!=y){
                totuni--;
                if(!(--mp[cnt[x]])) mp.erase(cnt[x]);
                if(!(--mp[cnt[y]])) mp.erase(cnt[y]);
                cnt[x]+=cnt[y];
                par[y]=x;
                mp[cnt[x]]++;
            }
        }
        else
        {
            vector<pair<int,int> > v(mp.begin(),mp.end());
            int sz=v.size(),j=0,sum=0;
            int c; scanf("%d",&c);
            if(c==0) { printf("%lld\n",(ll)totuni*(ll)(totuni-1)/2); continue; }
            map<int,int>::iterator it;
            ll ans=0;
            for(int i=0;i<sz;i++)
            {
                while(v[i].first-v[j].first >=c) sum+=v[j++].second;
                ans+=(ll)sum*(ll)v[i].second;
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}