题面 https://www.luogu.org/problemnew/show/P1975
考虑交换两个数的影响, 发现只有夹在两个数中间的大于 / 小于两个数的数会产生影响, 而两边的状态是不变的, 然后就变成了序列分块的经典问题
注意细节. jpg
- #include<cmath>
- #include<cstdio>
- #include<vector>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- const int N=20005,Sq=150;
- int a[N],uni[N],blo[N],tra[N],pts[Sq][2];
- int n,m,t1,t2,sqr,cnt,len,ans;
- vector<int> v[Sq];
- int prework()
- {
- sqr=sqrt(n)+10,pts[cnt=1][0]=1;
- sort(uni+1,uni+1+n),len=unique(uni+1,uni+1+n)-uni-1;
- for(int i=1;i<=n;i++)
- {
- a[i]=lower_bound(uni+1,uni+1+len,a[i])-uni;
- blo[i]=(i-1)/sqr+1,v[blo[i]].push_back(a[i]);
- if(i%sqr==0) pts[cnt++][1]=i,pts[cnt][0]=i+1;
- }
- pts[cnt][1]=n;
- for(int i=1;i<=cnt;i++)
- sort(v[i].begin(),v[i].end());
- int ret=0;
- for(int i=1;i<=n;i++)
- {
- int tmp=len-a[i]+1,tep=tmp-1;
- while(tep) ret+=tra[tep],tep-=tep&-tep;
- while(tmp<=n) tra[tmp]++,tmp+=tmp&-tmp;
- }
- return ret;
- }
- int query(int x,int t)
- {
- int ret=0;
- if(!t)
- {
- if(blo[t1]!=blo[t2])
- {
- for(int i=t1;i<=pts[blo[t1]][1];i++) ret+=(a[i]<x);
- for(int i=pts[blo[t2]][0];i<=t2;i++) ret+=(a[i]<x);
- for(int i=blo[t1]+1;i<=blo[t2]-1;i++)
- ret+=lower_bound(v[i].begin(),v[i].end(),x)-v[i].begin();
- }
- else
- for(int i=t1;i<=t2;i++) ret+=(a[i]<x);
- }
- else
- {
- if(blo[t1]!=blo[t2])
- {
- for(int i=t1;i<=pts[blo[t1]][1];i++) ret+=(a[i]>x);
- for(int i=pts[blo[t2]][0];i<=t2;i++) ret+=(a[i]>x);
- for(int i=blo[t1]+1;i<=blo[t2]-1;i++)
- ret+=v[i].size()-(upper_bound(v[i].begin(),v[i].end(),x)-v[i].begin());
- }
- else
- for(int i=t1;i<=t2;i++) ret+=(a[i]>x);
- }
- return ret;
- }
- void rebuild(int x,int y)
- {
- swap(a[x],a[y]);
- int b1=blo[x],b2=blo[y]; if(b1==b2) return ;
- v[b1].clear(),v[b2].clear();
- for(int i=pts[b1][0];i<=pts[b1][1];i++)
- v[b1].push_back(a[i]);
- for(int i=pts[b2][0];i<=pts[b2][1];i++)
- v[b2].push_back(a[i]);
- sort(v[b1].begin(),v[b1].end());
- sort(v[b2].begin(),v[b2].end());
- }
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- scanf("%d",&a[i]),uni[i]=a[i];
- printf("%d\n",ans=prework());
- scanf("%d",&m);
- while(m--)
- {
- scanf("%d%d",&t1,&t2);
- if(t1>t2) swap(t1,t2);
- int a1=a[t1],a2=a[t2];
- if(t1!=t2-1)
- {
- t1++,t2--;
- ans+=query(a1,1)-query(a1,0);
- ans+=query(a2,0)-query(a2,1);
- t1--,t2++;
- }
- if(a1<a2) ans++; if(a1>a2) ans--;
- rebuild(t1,t2); printf("%d\n",ans);
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2847183.html