CDQZ Challenge 13

앞에서 말 했 듯 이 "CDQZ" 시리즈 의 제목 데 이 터 는 절대 양심 (심혈 을 기울 여 233) 입 니 다. 인터넷 주 소 를 제출 할 때 필요 하 다 면 개인 편지 본 을 보 내 주세요.1013: Challenge 13 보기 제출 통계 질문 총 시간 제한: 10000 ms 단일 테스트 포인트 시간 제한: 1000 ms 메모리 제한: 262144 kB 는 N 길이 의 수열 에 설명 하고 M 번 조작 이 있 으 며 조작 은 하나 밖 에 없습니다 (모든 위 치 는 처음에 각각 하나의 집합 에 속 합 니 다).
두 위치 에 속 하 는 집합 을 합 쳐 두 집합 간 에 형 성 된 역순 대 수 를 구하 다.
첫 줄 의 정수 N 과 M 두 개 를 입력 하 십시오.두 번 째 줄 의 N 개 정 수 는 이 수열 을 나타 낸다.다음 M 줄 은 각 줄 이 두 개의 정수 x 와 y 로 x 와 y 가 속 한 집합 을 합 친 다 는 뜻 이다. 만약 에 x 와 y 가 하나의 집합 에 속 하면 출력 - 1 이다. 그렇지 않 으 면 출력 은 x 가 있 는 집합 을 y 가 있 는 집합 앞 에 놓 을 때 형 성 된 역순 대수 이다.출력 은 모든 질문 동작 에 대해 한 줄 을 따로 출력 하여 답 을 표시 합 니 다.샘플 입력 5 3 1 2 3 4 5 1 2 3 2 1 3 샘플 출력 0 2 - 1 알림 1 < = N < = 10 ^ 5, 1 < = M < = 10 ^ 5, 입력 보증 합 법 적 이 며 모든 정 수 는 기호 32 비트 정형 으로 저장 할 수 있 습 니 다.
문제 풀이: 각 수의 가중치 선분 트 리 에 대해 서 는 집합 으로 유지 하고 집합 할 때마다 당직 선분 트 리 를 합 쳐 답 을 통계 합 니 다.
통계 답 에 대해 다음 과 같은 신기 한 조작 (같은 반 친구 들 이 쓴 것) 이 있다. 아마도 당직 라인 트 리 를 합병 할 때 모든 (현재 X 나무의 노드 가 x, Y 나무의 노드 가 y, x 가 비어 있 지만 y 가 비어 있 지 않 거나 x, y 가 비어 있 지 않 고 그들 이 모두 잎 이 맺 힌 다 고 가정 하면) 이런 노드 y 이다. 그 가 답 에 기여 한 것 은 모두 y - > siz * 이다.(X 트 리 의 총 siz - 합 쳐 진 x 의 siz)
이 『 33951 』 을 잘 모 르 기 때문에 자신 은 다음 과 같은 표기 법 을 썼 습 니 다.

    if (lc[x]&&rc[y])
        ans+=(siz[lc[x]]*siz[rc[y]]);

자기 감각 이 또렷 하 다

#include
#include
#include
#include
#define lson lc[rt],l,mid
#define rson rc[rt],mid+1,r
#define pushup(rt) siz[rt]=siz[lc[rt]]+siz[rc[rt]]
using namespace std;
const int MAXN=1e5+2;
int a[MAXN],b[MAXN],f[MAXN],n,Q,m;
int root[MAXN],lc[MAXN*20],rc[MAXN*20],siz[MAXN*20],tim=0;
int ans,md;
inline int read() {
    int x=0,f=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
int find(int x) {
    return f[x]==x?x:f[x]=find(f[x]);
}
void Insert(int &rt,int l,int r,int val) {
    if (!rt) rt=++tim;
    if (l==r) {
        ++siz[rt];
        return ;
    }
    int mid=(l+r)>>1;
    if (val<=mid) Insert(lson,val);
    else Insert(rson,val);
    pushup(rt);
}
int Merge(int x,int y) {
    if (!x||!y) return x+y;
    if (lc[x]&&rc[y])
        ans+=(siz[lc[x]]*siz[rc[y]]);
    lc[x]=Merge(lc[x],lc[y]),rc[x]=Merge(rc[x],rc[y]);
    pushup(x);
    return x;
}
int main() {
//  freopen("Challenge 13.in","r",stdin);
//  freopen("C13.in","r",stdin);
//  printf("memory==%d
",sizeof(lc)*3+sizeof(a)*5);
    siz[0]=0;
    memset(root,0,sizeof(root)),
    memset(lc,0,sizeof(lc)),
    memset(rc,0,sizeof(rc));
    n=read(),Q=read();
    for (register int i=1;i<=n;++i) b[i]=a[i]=read(),f[i]=i;
    sort(b+1,b+n+1);
    int m=unique(b+1,b+n+1)-b-1;
    for (register int i=1;i<=n;++i)
        a[i]=lower_bound(b+1,b+m+1,a[i])-b,Insert(root[i],1,n,a[i]);
    for (register int i=1;i<=Q;++i) {
        int p=read(),q=read();
        p=find(p),q=find(q);
        if (p==q) {puts("-1");continue;}
        else {
            ans=0,md=0;
            root[q]=Merge(root[q],root[p]);
            f[p]=q;
            printf("%d
",ans);
        }
    }
    return 0;
}