题解 CF785E 【Anton and Permutation】
Owen_codeisking
2018-11-23 08:05:17
## 分块大法好！！！！！
考虑用块中在 $vector$ 中二分，边角暴力，$swap$ 两个元素就二分然后 $erase,insert$ 一下，时间复杂度为 $O(n\sqrt{n}\log n)$
个人经验：以下两种分块写法是不等价的
写法一：
```cpp
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;
```
写法二：
```cpp
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:$
```cpp
#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;
}
```