题解 CF785E 【Anton and Permutation】
一.闲谈
听说本题分块可以过而且吊打树套树？orz。。。我果然还是太菜了。。。
二.分析
1.求逆序对
简化题目:给出序列1-n，以及m个操作，每次交换两个数，求当前序列的逆序对数
如果,交换的两个数相同，我们直接输出当前答案即可，那么其他的情况呢？
假设，我们知道交换前的逆序对数，那么新序列的逆序对数便等于原逆序对数加上两个数交换后的贡献
那么，我们来考虑如何计算两个数交换的贡献
我们设两个数分别为x和y,我们再设find_max(l,r,x)表示区间l->r内比x大的数的个数，find_min(l,r,x)同理，再设a[x]表示x的位置
那么交换后，与x，y有关的逆序对为(注:这里a[x]与a[y]尚未交换,且以下不考虑x与y形成的逆序对):
find_max(1,a[y]-1,x)+find_min(a[y]+1,n,x)+find_max(1,a[x]-1,y)+find_min(a[x]+1,n,y)
那么我们加上这个答案就好了吗？
不对！思考下，交换前，可能有与x,y有关的逆序对，如果我们直接加上当前的逆序对的话，我们就可能重复计算了！所以，我们还需要把答案减去交换前的与x,y有关的逆序对数,即:
find_max(1,a[x]-1,x)+find_min(a[x]+1,n,x)+find_max(1,a[y]-1,y)+find_min(a[y]+1,n,y)
然后，我们再来考虑x,y形成的逆序对:
交换后，x与y有两个情况:
1.x与y形成一个逆序对:
我们直接将答案加一即可
2.x与y不形成逆序对，原逆序对消失:
那么，我们是否需要将答案减一呢？
不是的，因为，我们一开始，不是减去了与x,y有关的逆序对数嘛？这时，我们在x里减去了逆序对(x,y)，又在y里减去了逆序对(x,y)，而我们本来只需要减一次的却减了两次！所以我们也需要将答案加一！
所以，两种情况的处理方式是相同的！
2.求函数find_min、find_max
现在，我们已经知道如何求逆序对了，但是，我们还需要知道如何求find_min、find_max两个函数，我们首先考虑优秀的权值线段树，然而，全局线段树并不擅长区间，于是我们启用它的升级版:主席树，然后我们就可以轻松地求出来了，不过，我们这时，发现，我们还有交换操作没用，如果，我们写普通的主席树，我们就需要对a[x]>a[y]的每一个主席树都修改一遍，这时，我们再给它升级一下:我们用带修主席树来解决这些问题！
至于交换操作，我们可以如此理解:
将a[x]位置上的x修改成y，将a[y]位置上的y修改成x,之后我们再把a[x]与a[y]交换一下就可以了！
复杂度：O(mloglogn*巨大常数(雾))
三.优化
这题甚为毒瘤的一点在于:卡空间
经过试验(类似方法)，开long long的直接凉
开int 2e7会MLE,开1e7会Re
于是我愤怒之下，写了一个垃圾回收，然后空间开成1e7+5e6才过的QwQ
注意:写垃圾回收时，不要把root[i]回收了，因为我们还需要查询值之类的操作。。。
四.代码
//#pragma GCC optimize()//手动Ox优化
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5e6;
struct node{
int val,lson,rson;
}t[N];
int n,m;
int a[N];
int siz,root[N];
int Now[N],Pas[N],L,R;
int sta[N],top;
inline int lowbit(int x){
return x&-x;
}
inline int news(){
if(top){
return sta[top--];
}
return ++siz;
}
inline void delt(int x){
sta[++top]=x;
}
//垃圾回收
inline void mest(int x){
t[x].lson=t[x].rson=t[x].val=0;
}
inline void insert(int &now,int l,int r,int x){
if(!now){
now=news();
mest(now);
}
t[now].val++;
if(l==r){
return;
}
int mid=(l+r)>>1;
if(x<=mid){
insert(t[now].lson,l,mid,x);
}else{
insert(t[now].rson,mid+1,r,x);
}
}
inline int find_Max(int l,int r,int lc,int rc){
int sum=0,tot=0;
for(int i=1;i<=L;++i){
sum-=t[Pas[i]].val;
tot-=t[t[Pas[i]].rson].val;
}
for(int i=1;i<=R;++i){
sum+=t[Now[i]].val;
tot+=t[t[Now[i]].rson].val;
}
if(lc<=l&&r<=rc){
return sum;
}
int mid=(l+r)>>1;
if(rc<=mid){
for(int i=1;i<=L;++i){
Pas[i]=t[Pas[i]].lson;
}
for(int i=1;i<=R;++i){
Now[i]=t[Now[i]].lson;
}
return find_Max(l,mid,lc,rc);
}
if(lc>mid){
for(int i=1;i<=L;++i){
Pas[i]=t[Pas[i]].rson;
}
for(int i=1;i<=R;++i){
Now[i]=t[Now[i]].rson;
}
return find_Max(mid+1,r,lc,rc);
}
for(int i=1;i<=L;++i){
Pas[i]=t[Pas[i]].lson;
}
for(int i=1;i<=R;++i){
Now[i]=t[Now[i]].lson;
}
return find_Max(l,mid,lc,rc)+tot;
}
inline int find_Min(int l,int r,int lc,int rc){
int sum=0,tot=0;
for(int i=1;i<=L;++i){
sum-=t[Pas[i]].val;
tot-=t[t[Pas[i]].lson].val;
}
for(int i=1;i<=R;++i){
sum+=t[Now[i]].val;
tot+=t[t[Now[i]].lson].val;
}
if(lc<=l&&r<=rc){
return sum;
}
int mid=(l+r)>>1;
if(rc<=mid){
for(int i=1;i<=L;++i){
Pas[i]=t[Pas[i]].lson;
}
for(int i=1;i<=R;++i){
Now[i]=t[Now[i]].lson;
}
return find_Min(l,mid,lc,rc);
}
if(lc>mid){
for(int i=1;i<=L;++i){
Pas[i]=t[Pas[i]].rson;
}
for(int i=1;i<=R;++i){
Now[i]=t[Now[i]].rson;
}
return find_Min(mid+1,r,lc,rc);
}
for(int i=1;i<=L;++i){
Pas[i]=t[Pas[i]].rson;
}
for(int i=1;i<=R;++i){
Now[i]=t[Now[i]].rson;
}
return find_Min(mid+1,r,lc,rc)+tot;
}
inline int find_min(int l,int r,int x){
if(!r){
return 0;
}
if(x==1){
return 0;
}
int now=l-1;
L=R=0;
while(now){
Pas[++L]=root[now];
now-=lowbit(now);
}
now=r;
while(now){
Now[++R]=root[now];
now-=lowbit(now);
}
return find_Min(1,n,1,x-1);
}
inline int find_max(int l,int r,int x){//寻找l-r区间内，比x大的数
if(l==n+1){
return 0;
}
if(x==n){
return 0;
}
int now=l-1;
L=R=0;
while(now){
Pas[++L]=root[now];
now-=lowbit(now);
}
now=r;
while(now){
Now[++R]=root[now];
now-=lowbit(now);
}
return find_Max(1,n,x+1,n);
}
inline void delted(int now,int l,int r,int x){
t[now].val--;
if(l==r){
return;
}
int mid=(l+r)>>1;
if(x<=mid){
delted(t[now].lson,l,mid,x);
if(!t[t[now].lson].val){
delt(t[now].lson);
t[now].lson=0;
}
return;
}else{
delted(t[now].rson,mid+1,r,x);
if(!t[t[now].rson].val){
delt(t[now].rson);
t[now].rson=0;
}
}
}
inline void change(int t,int x,int y){//将t位置的x修改为y
int now=t;
while(now<=n){
delted(root[now],1,n,x);
insert(root[now],1,n,y);
now+=lowbit(now);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
a[i]=i;
int now=i;
while(now<=n){
insert(root[now],1,n,i);
now+=lowbit(now);
}
}
long long ans=0;
while(m--){
int x,y;
scanf("%d%d",&x,&y);
if(x>y){
swap(x,y);
}
if(x==y){
printf("%lld\n",ans);
continue;
}
ans-=(find_max(1,a[x]-1,x)+find_min(a[x]+1,n,x));
ans-=(find_max(1,a[y]-1,y)+find_min(a[y]+1,n,y));
ans+=(find_max(1,a[y]-1,x)+find_min(a[y]+1,n,x));
ans+=(find_max(1,a[x]-1,y)+find_min(a[x]+1,n,y));
ans++;
change(a[x],x,y),change(a[y],y,x);
swap(a[x],a[y]);
printf("%lld\n",ans);
}
return 0;
}
京公网安备 11010502036488号