题解 CF785E 【Anton and Permutation】

· · 题解

分块大法好！！！！！

考虑用块中在 vector 中二分，边角暴力，swap 两个元素就二分然后 erase,insert 一下，时间复杂度为 O(n\sqrt{n}\log n)

个人经验：以下两种分块写法是不等价的

写法一：

    for(int i=1;i<=blo;i++){
        L[i]=(i-1)*blo+1,R[i]=i*blo;
        for(int j=L[i];j<=R[i];j++) pos[j]=i,v[i].push_back(j);
    }
    if(blo*blo!=n){
        int i=blo+1;L[i]=(i-1)*blo+1,R[i]=n;
        for(int j=L[i];j<=R[i];j++) pos[j]=i,v[i].push_back(j);
    }
    for(int i=1;i<=n;i++) a[i]=i;

写法二：

    for(int i=1;i<=blo;i++){
        L[i]=(i-1)*blo+1,R[i]=i*blo;
        for(int j=L[i];j<=R[i];j++) v[i].push_back(j);
    }
    if(blo*blo!=n){
        int i=blo+1;L[i]=(i-1)*blo+1,R[i]=n;
        for(int j=L[i];j<=R[i];j++) v[i].push_back(j);
    }
    for(int i=1;i<=n;i++) pos[i]=(i-1)/blo+1,a[i]=i;

注意：写法二的 pos[i] 是错的，因为最后一块的大小可以超过 \sqrt{n} 的！！！

Code\ Below: 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=200000+10;
const int inf=0x3f3f3f3f;
int n,m,a[maxn],pos[maxn],L[maxn],R[maxn],cnt[maxn],blo;ll ans;

vector<int> v[500];

inline int read(){
    register int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return (f==1)?x:-x;
}

void update(int l,int r){
    int p=pos[l],q=pos[r];
    if(p < q){
        v[p].erase(lower_bound(v[p].begin(),v[p].end(),a[l]));
        v[p].insert(upper_bound(v[p].begin(),v[p].end(),a[r]),a[r]);
        v[q].erase(lower_bound(v[q].begin(),v[q].end(),a[r])); 
        v[q].insert(upper_bound(v[q].begin(),v[q].end(),a[l]),a[l]);
    }
    swap(a[l],a[r]);
}
ll query(int l,int r,int k){
    if(l > r) return 0;
    int p=pos[l],q=pos[r];ll ans=0,num;
    if(p+1>=q){
        for(int i=l;i<=r;i++)
            if(a[i]<k) ans++;
    }
    else {
        for(int i=l;i<=R[p];i++)
            if(a[i]<k) ans++;
        for(int i=L[q];i<=r;i++)
            if(a[i]<k) ans++;
        for(int i=p+1;i<=q-1;i++){
            num=upper_bound(v[i].begin(),v[i].end(),k)-v[i].begin();
            ans+=num;
        }
    }
    return ans;
}

int main()
{
    n=read(),m=read();blo=sqrt(n);
    for(int i=1;i<=blo;i++){
        L[i]=(i-1)*blo+1,R[i]=i*blo;
        for(int j=L[i];j<=R[i];j++) pos[j]=i,v[i].push_back(j);
    }
    if(blo*blo!=n){
        int i=blo+1;L[i]=(i-1)*blo+1,R[i]=n;
        for(int j=L[i];j<=R[i];j++) pos[j]=i,v[i].push_back(j);
    }
    for(int i=1;i<=n;i++) a[i]=i;
    int l,r;
    for(int i=1;i<=m;i++){
        l=read(),r=read();
        if(l>r) swap(l,r);
        if(l==r) printf("%I64d\n",ans);
        else {
            ans+=2*query(l+1,r-1,a[r])-(r-l-1);
            ans+=(r-l-1)-2*query(l+1,r-1,a[l]);
            ans+=(a[l]<a[r])?1:(a[l]>a[r])?-1:0;
            update(l,r);
            printf("%I64d\n",ans);
        }
    }
    return 0;
}