[国家集训队]排队

Author Avatar
ZC 1月 26, 2019
  • 在其它设备中阅读本文章

题意:

每次交换两个数然后查询逆序对个数。

题解:

设交换的两个数下标为$l,r(l<r)$

那么对区间$[1,l-1],[r+1,n]​$是没有影响的,只会对$[l+1,r-1]​$中的数产生影响。

对于每次询问 用上一次的答案加上交换l,r的影响,就是这次的答案

设$l<i<r$,序列为$a_1,a_2, … , a_n$那么

$a_i > a_l \Rightarrow ans++​$

$a_i < a_l \Rightarrow ans–$

$a_i > a_r \Rightarrow ans–$

$a_i < a_r \Rightarrow ans++$

那么问题就变成了 在区间$[ l+1,r-1 ]$内,有多少个数满足上述的四种条件

实现方法:

先用归并或树状数组求出初始答案(逆序对数)

接着:

  1. 给每个块排序,然后处理时直接二分,修改时二分后插入
  2. 模仿作诗、蒲公英,预处理出$s[i][j]$表示前i块中j出现的次数,每次求时枚举$1$ ~ $i$ ,$ans+=s[belong[r]−1][i]−sum[belong[l]][i]$,其他三种情况同理(不推荐使用这种做法,以为复杂度太高,但因为数据水,时间只用了做法1的2倍多)

代码

#include<cstdio>
#include<cmath>
#include<algorithm>
namespace FastIO{struct Reader{char buf[1<<20],*s,*t;bool EOF_FLG;Reader():s(buf),t(buf),EOF_FLG(false) {};char gt() {return s==t&&((t=(s=buf)+fread(buf,1,1<<20,stdin))==s)?EOF:(*s++);}Reader& operator>>(char* str) {if(EOF_FLG)return *str=0,*this;while((*str=gt())!=' '&&*str!='\n'&&*str!=EOF)++str;if(*str==EOF)EOF_FLG=true;*str=0;return *this;}template<typename T>Reader&operator>>(T&x) {if(EOF_FLG)return *this;char c=0,d;while(c!=EOF&&(c<'0'||c>'9'))d=c,c=gt();if(c==EOF){EOF_FLG=true;return *this;}else x=0;while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=gt();if(d=='-')x=-x;return *this;}}in;struct Writer{char buf[1<<20],*s,*t;Writer():s(buf),t(buf+(1<<20)){}~Writer(){fwrite(buf,1,s-buf,stdout);}void pt(char c){(s==t)?(fwrite(s=buf,1,1<<20,stdout),*s++=c):(*s++=c);}template<typename T>Writer&operator<<(T x){if(!x)return pt('0'),*this;if(x<0)pt('-'),x=-x;char a[40],t=0;while(x)a[t++]=x%10,x/=10;while(t--)pt(a[t]+'0');return *this;}Writer&operator<<(const char*s) {while(*s)pt(*s++);return *this;}}out;}using namespace FastIO;
#define ri register int
#define Fur(i,x,y) for(ri i=x;i<=y;i++)
int MAX(int x,int y){return x>=y?x:y;}
int MIN(int x,int y){return x<=y?x:y;}
void SWAP(int &x,int &y){x^=y;y^=x;x^=y;}
using namespace std;
#define N 20001
int a[N],b[N],v[N],n,q,L,ans=0,bl[N],kl[N],kr[N],t[N];
void mgs(ri l,ri r){
    if(l==r)return;
    ri m=(l+r)>>1,i=l,j=m+1,d=l;
    mgs(l,m);mgs(m+1,r);
    while(i<=m&&j<=r)
        if(v[i]<=v[j])t[d++]=v[i++];
        else t[d++]=v[j++],ans+=m-i+1;
    while(i<=m)t[d++]=v[i++];
    while(j<=r)t[d++]=v[j++];
    Fur(i,l,r)v[i]=t[i];
}
int main(){
    in>>n;L=sqrt(n);
    Fur(i,1,n)in>>a[i],b[i]=v[i]=a[i],bl[i]=(i-1)/L+1;
    Fur(i,1,bl[n])sort(b+(kl[i]=(i-1)*L+1),b+(kr[i]=MIN(i*L,n))+1);
    mgs(1,n);out<<ans<<"\n";
    in>>q;
    while(q--){
        int l,r;in>>l>>r;
        if(l>r)SWAP(l,r);
        if(a[l]==a[r]){out<<ans<<"\n";continue;}
        ans+=((a[r]>a[l])-(a[l]>a[r]));
        if(bl[l]==bl[r])Fur(i,l+1,r-1)ans+=((a[i]>a[l])-(a[i]<a[l])+(a[i]<a[r])-(a[i]>a[r]));
        else{
            Fur(i,l+1,kr[bl[l]])ans+=((a[i]>a[l])-(a[i]<a[l])+(a[i]<a[r])-(a[i]>a[r]));
            Fur(i,kl[bl[r]],r-1)ans+=((a[i]>a[l])-(a[i]<a[l])+(a[i]<a[r])-(a[i]>a[r]));
            Fur(i,bl[l]+1,bl[r]-1){
                if(b[kl[i]]<a[l]){
                    ri L=kl[i],R=kr[i],c=a[l],m;
                    while(L!=R){
                        m=(L+R)>>1;
                        (b[m]<c)?(L=m+1):(R=m);
                    }
                    if(L>=kl[i]&&b[L]>=c)L--;
                    ans-=L-kl[i]+1;
                }
                if(b[kr[i]]>a[l]){
                    ri L=kl[i],R=kr[i],c=a[l],m;
                    while(L!=R){
                        m=(L+R)>>1;
                        (b[m]<=c)?(L=m+1):(R=m);
                    }
                    ans+=kr[i]-R+1;
                }
                if(b[kl[i]]<a[r]){
                    ri L=kl[i],R=kr[i],c=a[r],m;
                    while(L!=R){
                        m=(L+R)>>1;
                        (b[m]<c)?(L=m+1):(R=m);
                    }
                    if(L>=kl[i]&&b[L]>=c)L--;
                    ans+=L-kl[i]+1;
                }
                if(b[kr[i]]>a[r]){
                    ri L=kl[i],R=kr[i],c=a[r],m;
                    while(L!=R){
                        m=(L+R)>>1;
                        (b[m]<=c)?(L=m+1):(R=m);
                    }
                    ans-=kr[i]-R+1;
                }
            }
            ri L=kl[bl[l]],R=kr[bl[l]],m,c=a[l];
            while(L!=R){
                m=(L+R)>>1;
                (b[m]<c)?(L=m+1):(R=m);
            }
            ri tmp=L;b[tmp]=a[r];
            L=kl[bl[l]],R=kr[bl[l]];
            while(tmp>L&&b[tmp]<b[tmp-1])SWAP(b[tmp],b[tmp-1]),tmp--;
            while(tmp<R&&b[tmp]>b[tmp+1])SWAP(b[tmp],b[tmp+1]),tmp++;
            L=kl[bl[r]],R=kr[bl[r]],c=a[r];
            while(L!=R){
                m=(L+R)>>1;
                (b[m]<c)?(L=m+1):(R=m);
            }
            tmp=L,b[tmp]=a[l];
            L=kl[bl[r]],R=kr[bl[r]];
            while(tmp>L&&b[tmp]<b[tmp-1])SWAP(b[tmp],b[tmp-1]),tmp--;
            while(tmp<R&&b[tmp]>b[tmp+1])SWAP(b[tmp],b[tmp+1]),tmp++;
        }
        SWAP(a[l],a[r]);
        out<<ans<<"\n";
    }
}