题解 P1975 【[国家集训队]排队】

大菜鸡fks · 2018-04-15 20:28:59 · 题解

复习分块。

这题用树状数组+分块可以做，树套树也可以。

但后者常数巨大，代码复杂度偏高。

这题比较套路。分块以后对于每一块套一个树状数组。两数交换只需要考虑中间一部分。整块的在树状数组进行查询。零散的直接暴力。

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=2e4+5,maxb=200;
struct node{
    int id,x;
}a[maxn];
int n,h[maxn],block,r[maxb],l[maxb],belong[maxn],cnt;
inline bool cmp(node A,node B){
    return A.x<B.x;
}
inline void init(){
    scanf("%d",&n);
    block=(int)sqrt(n);
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i].x); a[i].id=i; 
        belong[i]=(i-1)/block+1;
    }
    sort(a+1,a+1+n,cmp);
    for (int i=1;i<=n;i++){
        if (a[i].x!=a[i-1].x) cnt++;
        h[a[i].id]=cnt;
    }
    cnt=belong[n];
    for (int i=1;i<=cnt;i++){
        l[i]=r[i-1]+1;
        r[i]=i*block;
    }
    r[cnt]=n;
}
int bit[maxb][maxn],m,Bit[maxn];
inline int lowbit(int x){return x&(-x);}
inline void update(int c[],int x,int y){for (;x<=n;x+=lowbit(x)) c[x]+=y;}
inline int query(int c[],int x){int ans=0; for (;x;x-=lowbit(x)) ans+=c[x]; return ans;}
inline void solve(){
    int ans=0;
    for (int i=n;i;i--){
        ans+=query(Bit,h[i]-1);
        update(Bit,h[i],1);
        update(bit[belong[i]],h[i],1);
    }
    printf("%d\n",ans);
    scanf("%d",&m);
    for (int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if (x>y) swap(x,y);
        int ll=belong[x]+1,rr=belong[y]-1;
        if (belong[x]!=belong[y]){
            for (int j=ll;j<=rr;j++){
                ans-=query(bit[j],h[x]-1);
                ans+=query(bit[j],n)-query(bit[j],h[x]);
                ans+=query(bit[j],h[y]-1);
                ans-=query(bit[j],n)-query(bit[j],h[y]);
            }
            for (int j=x+1;j<=r[ll-1];j++){
                if (h[j]>h[x]) ans++;
                if (h[j]>h[y]) ans--;
                if (h[j]<h[x]) ans--;
                if (h[j]<h[y]) ans++; 
            }
            for (int j=l[rr+1];j<y;j++){
                if (h[j]>h[x]) ans++;
                if (h[j]>h[y]) ans--;
                if (h[j]<h[x]) ans--;
                if (h[j]<h[y]) ans++; 
            }
        }else{
            for (int j=x+1;j<y;j++){
                if (h[j]>h[x]) ans++;
                if (h[j]>h[y]) ans--;
                if (h[j]<h[x]) ans--;
                if (h[j]<h[y]) ans++; 
            }
        }
        if (h[x]<h[y]) ans++;
        if (h[x]>h[y]) ans--;
        printf("%d\n",ans);
        update(bit[belong[x]],h[x],-1);
        update(bit[belong[x]],h[y],1);
        update(bit[belong[y]],h[y],-1);
        update(bit[belong[y]],h[x],1);
        swap(h[x],h[y]);
    }
}
int main(){
    init();
    solve();
    return 0;
}