285484026

[CQOI2011]动态逆序对 CDQ分治
[[CQOI2011]动态逆序对][1]题解:将时间转化为一个维度以后就变成了一个三维偏序的问题,然后把删除改为反...
扫描右侧二维码阅读全文
13
2019/07

[CQOI2011]动态逆序对 CDQ分治

[[CQOI2011]动态逆序对][1]

题解:
将时间转化为一个维度以后就变成了一个三维偏序的问题,然后把删除改为反向插入,插入的时候记得统计每个点前面把它大的数加上后面比它小的作为新加入的逆序对。

#include <bits/stdc++.h>

const int MAXN = 100000;

using namespace std;

int n,m;
int p[MAXN],C[MAXN],ans[MAXN];
bool vis[MAXN];

struct node{
    int a,b,c;
    long long f;
}P[MAXN],T[MAXN];

void init(){
    int x;
    for(int i = 1;i <= n;i++){
        scanf("%d",&x);
        p[x] = i;
    }
    
    stack<int>S;
    for(int i = 1;i <= m;i++){
        scanf("%d",&x);
        S.push(x);
    }
    
    for(int i = n - m + 1;i <= n;i++){
        x = S.top();S.pop();vis[x] = true;
        P[i].a = i;
        P[i].b = p[x];
        P[i].c = x;
    }
    int cnt = 0;
    for(int i = 1;i <= n;i++)
        if(!vis[i]){
            ++cnt;
            P[cnt].a = cnt;
            P[cnt].b = p[i];
            P[cnt].c = i;
        }
}

inline bool cmpA(const node &A,const node &B){
    return A.a < B.a;
}

inline int lowbit(int x){return x & (-x);}

inline void add(int x,int d){
    for(;x <= n;x += lowbit(x)) C[x] += d;
}

inline int sum(int x){
    if(x == 0) return 0;
    int ret = 0;
    for(;x;x -= lowbit(x)) ret += C[x];
    return ret;
}

inline void CDQ(int L,int R){
    if(L == R) return ;
    int M = (L + R) >> 1;
    CDQ(L,M);CDQ(M+1,R);
    
    int lc,rc,cnt;
    lc = L;rc = M + 1;//统计左边比他大的点
    while(lc <= M && rc <= R){
        if(P[lc].b < P[rc].b) add(P[lc].c,1),lc++;
        else P[rc].f += sum(n) - sum(P[rc].c-1),rc++;
    }
    while(lc <= M) add(P[lc].c,1),lc++;
    
    while(rc <= R) P[rc].f += sum(n) - sum(P[rc].c-1),rc++;

    for(int i = L;i <= M;i++) add(P[i].c,-1);

    lc = M;rc = R;//统计右边比他小的点
    while(lc >= L && rc >= M+1){
        if(P[lc].b > P[rc].b) add(P[lc].c,1),lc--;
        else P[rc].f += sum(P[rc].c),rc--;
    }

    while(lc >= L) add(P[lc].c,1),lc--;
    while(rc >= M + 1) P[rc].f += sum(P[rc].c),rc--;

    for(int i = L;i <= M;i++)add(P[i].c,-1);

    lc = cnt = L;rc = M + 1;
    while(lc <= M && rc <= R){
        if(P[lc].b < P[rc].b) T[cnt++] = P[lc++];
        else T[cnt++] = P[rc++];

    }

    while(lc <= M) T[cnt++] = P[lc++];
    while(rc <= R) T[cnt++] = P[rc++];
    
    for(int i = L;i <= R;i++) P[i] = T[i];
}

int main()
{
    scanf("%d %d",&n,&m);
    init();
    sort(P+1,P+n+1,cmpA);
    CDQ(1,n);
    sort(P+1,P+n+1,cmpA);
    for(int i = 1;i <= n;i++) P[i].f += P[i-1].f;
    for(int i = n;i > n-m;i--) printf("%lld\n",P[i].f);

    return 0;
}
Last modification:July 13th, 2019 at 10:01 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment