CF785E Anton and Permutation

題意：

對于一個長度為 n 的序列進行 k 次操作，每次操作都是交換序列中的某兩個數。對于每一個操作，回答當前序列中有多少個逆序對。
1<=n<=200000
1<=q<=50000

題解：

動態逆序對（樹套樹模板題）
用分塊的方法做
假設 x=a[l],y=a[r] 且 x<y, swap(a[l],a[r])時，只有下標區間 (l,r) 中值域在 [x,y] 中的數會影響逆序對數量。分塊，每塊維護1個有序vector，用 upper_bound(y) - lower_bound(x) 就能二分出值域[x,y]中的數個數。修改的話，在adj[idl]中find出x的下標，替換為y后暴力sort這塊即可。
lower_bound( begin,end,num) 大于等于
upper_bound( begin,end,num) 大于

本質：二維數點
離線版：掃描線
在線版（帶修改）：分塊，線段樹等方法

代碼：

細細品品代碼

#include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } int n,B,q; const int maxn=2e5+9; int a[maxn]; vector<int>adj[maxn]; void init() {B=sqrt(n);for(int i=1;i<=n;i++){a[i]=i;adj[i/B].push_back(i);} } ll work(int l,int r) {if(l==r)return 0;int idl,idr,x,y,k;x=a[l];y=a[r];//值域[x,y] //將x修改成y，并x所在塊重新排序 idl=l/B;k=find(adj[idl].begin(),adj[idl].end(),x)-adj[idl].begin();adj[idl][k]=y;sort(adj[idl].begin(),adj[idl].end());//同上idr = r/B;k = find(adj[idr].begin(), adj[idr].end(), y) - adj[idr].begin();adj[idr][k] = x;//將y修改成x sort(adj[idr].begin(), adj[idr].end());int ans=0;int f;if(x>y)f=-1,swap(x,y);//逆序對減少 else f=1;//逆序對增加 if(idl==idr)//在同一個塊內 {for(int i=l+1;i<=r-1;i++){if(x<a[i]&&a[i]<y)ans++;} }else //在不同塊 {for(int i=l+1;i<(idl+1)*B;i++){if(x<a[i]&&a[i]<y)ans++;}for(int id=idl+1;id<idr;id++){vector<int> ::iterator L,R;R=upper_bound(adj[id].begin(),adj[id].end(),y);L=lower_bound(adj[id].begin(),adj[id].end(),x);ans+=R-L;//查看值在[x,y]內的數量 }for(int i=idr*B;i<r;i++){if(x<a[i]&&a[i]<y)ans++;} }swap(a[l],a[r]);//交換return (ans*2+1)*f;//乘2是因為和x和y都組成逆序對，加一是因為x和y交換對逆序對也造成影響 } int main() {cin>>n>>q;init();int l,r;ll ans=0;while(q--){cin>>l>>r;if(l>r)swap(l,r);ans+=work(l,r);cout<<ans<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的CF785E Anton and Permutation的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。