|
我们很容易就可以得到一个非常暴力的模拟算法。 但是我们想要不去模拟就必须要知道每轮冒泡排序改变的是什么东西. 每一轮冒泡 整个序列中 未到位的最大值一定会交换到后面,这个时候考虑一下这个最大值所处的位置 如果为p的话,其应该到的位置为pos 那么说明p+1~pos这些数字对逆序对的贡献减一 (如果这个数字每次都在排头那么我们就可以不用知道序列是什么样子而直接求出来逆序对的变换情况了。 考虑这个最大值p之前的位置会怎么变换 可以发现还是一个较大值被交换到p+1这个位置然后轮到p开始交换。 至此我们不难发现每次冒泡某个数字之前如果有比其大的数字那么这种数字至少减少1. 设b[i]为i之前有多少个比i大的数字.那么进行k轮 每次每个位置上的b[i]都要减减. 答案= ans为初始序列的逆序对个数.这个显然可以利用线段树维护。 考虑修改 ans修改是O(1)的 b[i]的修改也仅限于一个位置 所以这是一个区间求和单点修改的问题. 树状数组好像需要两个才能维护 直接线段树即可。 const int MAXN=200010; int n,m; int a[MAXN],b[MAXN]; ll c[MAXN],ans; inline int ask(int x) { int cnt=0; while(x) { cnt+=c[x]; x-=x&(-x); } return cnt; } inline void add(int x,int y) { if(!x)return; while(x<=n) { c[x]+=y; x+=x&(-x); } } struct wy { int l,r; ll sum; ll add; }t[MAXN<<2]; void build(long long p,long long l,long long r) { t[p].l=l;t[p].r=r; if(r==l)return; ll mid=(l+r)>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); t[p].sum=t[p<<1].sum+t[p<<1|1].sum; } void spread(long long p) { if(t[p].add!=0) { t[p<<1].add+=t[p].add; t[p<<1|1].add+=t[p].add; t[p<<1].sum+=t[p].add*(t[p<<1].r-t[p<<1].l+1); t[p<<1|1].sum+=t[p].add*(t[p<<1|1].r-t[p<<1|1].l+1); t[p].add=0; } } void change(long long p,long long l,long long r,long long k) { if(l>r)return; if(l<=t[p].l&&r>=t[p].r) { t[p].add+=k; t[p].sum+=k*(t[p].r-t[p].l+1); return; } spread(p); long long mid=(t[p].l+t[p].r)>>1; if(l<=mid)change(p<<1,l,r,k); if(r>mid)change(p<<1|1,l,r,k); t[p].sum=t[p<<1].sum+t[p<<1|1].sum; } long long ask(long long p,long long l,long long r) { if(l>r)return 0; if(l<=t[p].l&&r>=t[p].r)return t[p].sum; spread(p); long long mid=(t[p].l+t[p].r)>>1; long long ans=0; if(l<=mid)ans+=ask(p<<1,l,r); if(r>mid)ans+=ask(p<<1|1,l,r); return ans; } int main() { //freopen('bubble.in','r',stdin); //freopen('bubble.out','w',stdout); n=read();m=read(); for(int i=1;i<=n;++i) { a[i]=read(); b[i]=ask(n-a[i]+1); add(n-a[i]+1,1); ans+=b[i]; } build(1,1,n); for(int i=1;i<=n;++i)change(1,1,b[i],1); for(int i=1;i<=m;++i) { int op,x; op=read();x=read(); if(op==1) { if(a[x]>a[x+1]) { change(1,b[x+1],b[x+1],-1); --b[x+1];--ans; swap(a[x],a[x+1]); swap(b[x],b[x+1]); } else { change(1,b[x]+1,b[x]+1,1); ++b[x];++ans; swap(a[x],a[x+1]); swap(b[x],b[x+1]); } } else { x=min(x,n); ll w=ask(1,1,x); printf('%lld\n',ans-w); } } return 0; } 本文由chdy 发表，仅供参考，有任何问题欢迎与我们讨论或者与原作者讨论。原文地址：https://www.cnblogs.com/chdy/p/12451953.html |
|
|
