题目描述
On a permutation $ p $ of length $ n $ , we define a bully swap as follows:
- Let $ i $ be the index of the largest element $ p_i $ such that $ p_i \neq i $ .
- Let $ j $ be the index of the smallest element $ p_j $ such that $ i < j $ .
- Swap $ p_i $ and $ p_j $ .
We define $ f(p) $ as the number of bully swaps we need to perform until $ p $ becomes sorted. Note that if $ p $ is the identity permutation, $ f(p)=0 $ .
You are given $ n $ and a permutation $ p $ of length $ n $ . You need to process the following $ q $ updates.
In each update, you are given two integers $ x $ and $ y $ . You will swap $ p_x $ and $ p_y $ and then find the value of $ f(p) $ .
Note that the updates are persistent. Changes made to the permutation $ p $ will apply when processing future updates.
输入格式
The first line of the input contains two integers $ n $ and $ q $ ( $ 2 \le n \le 5 \cdot 10^5 $ , $ 1 \le q \le 5 \cdot 10^4 $ ) — the length of the permutation and the number of updates.
The second line of input contains $ n $ integer $ p_1,p_2,\ldots,p_n $ ( $ 1 \leq p_i \leq n $ ) — the permutation $ p $ . All elements of $ p $ are distinct.
The $ i $ -th of the next $ q $ lines of input contains two integers $ x_i $ and $ y_i $ ( $ 1 \le x_i < y_i \le n $ ) — describing the $ i $ -th update.
神仙题。
现在主要问题是如何快速求出 \(f(p)\) 的答案。
结论是 \(\sum\limits_{i=1}^n |i-p_i|-\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n[a_i>a_j]\)
因为在一次交换 \(i,j\) 时，逆序对减少 \(2(j-i)-1\) 次，\(|i-p_i|\) 减少 \(2(j-i)\) 个，于是减一下就是答案。
然后动态维护逆序对就好，我打了个常数巨大的 KDT。
#include<bits/stdc++.h>
using namespace std;
const int N=6e5+5;
typedef long long LL;
LL ans;
int n,q,mxx[N],mnx[N],mxy[N],mny[N],idx,c[N],tr[N],g[N],p[N],m;
pair<int,int>a[N];
int cmp(pair<int,int>x,pair<int,int>y)
{
return x.second^y.second? x.second<y.second:x.first<y.first;
}
int ask(int l,int r,int u,int d)
{
int o=l+r>>1;
if(l>r||mnx[o]>u||mxy[o]<d)
return 0;
if(mxx[o]<=u&&mny[o]>=d)
return c[o];
return ask(l,o-1,u,d)+ask(o+1,r,u,d)+(a[o].first<=u&&a[o].second>=d&&g[o]);
}
int build(int l,int r,int op)
{
if(l>r)
return 0;
int o=l+r>>1;
if(!op)
nth_element(a+l,a+o,a+r+1);
else
nth_element(a+l,a+o,a+r+1,cmp);
int lc=build(l,o-1,!op),rc=build(o+1,r,!op);
mxx[o]=max({mxx[lc],mxx[rc],a[o].first});
mnx[o]=min({mnx[lc],mnx[rc],a[o].first});
mxy[o]=max({mxy[lc],mxy[rc],a[o].second});
mny[o]=min({mny[lc],mny[rc],a[o].second});
return o;
}
void add(int l,int r,int a0,int a1,int t,int op)
{
int o=l+r>>1;
c[o]+=t;
if(a0==a[o].first&&a1==a[o].second)
return g[o]+=t,void();
if(!op&&make_pair(a0,a1)<a[o]||op&&cmp(make_pair(a0,a1),a[o]))
return add(l,o-1,a0,a1,t,!op),void();
add(o+1,r,a0,a1,t,!op);
}
int read()
{
int s=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
s=s*10+ch-48,ch=getchar();
return s;
}
void upd(int x)
{
for(;x<=n;x+=x&-x)
tr[x]++;
}
int query(int x)
{
int ret=0;
for(;x;x-=x&-x)
ret+=tr[x];
return ret;
}
void jia(int x,int op)
{
ans+=op*abs(x-p[x]);
int k=ask(1,m,x-1,p[x]);
ans-=op*k;
ans-=op*(p[x]-x+k);
}
int main()
{
static int x[N],y[N],g[N];
mnx[0]=mny[0]=1000000000;
mxx[0]=mxy[0]=-1;
n=read(),q=read();
for(int i=1;i<=n;i++)
g[i]=p[i]=read(),a[++m]=make_pair(i,p[i]);
for(int i=1;i<=q;i++)
{
x[i]=read(),y[i]=read();
swap(g[x[i]],g[y[i]]);
a[++m]=make_pair(x[i],g[x[i]]);
a[++m]=make_pair(y[i],g[y[i]]);
}
build(1,m,0);
for(int i=1;i<=n;i++)
add(1,m,i,p[i],1,0),upd(p[i]),ans+=abs(i-p[i])-i+query(p[i]);
for(int i=1;i<=q;i++)
{
jia(x[i],-1);
jia(y[i],-1);
add(1,m,x[i],p[x[i]],-1,0);
add(1,m,y[i],p[y[i]],-1,0);
if(p[x[i]]>p[y[i]])
--ans;
swap(p[x[i]],p[y[i]]);
add(1,m,x[i],p[x[i]],1,0);
add(1,m,y[i],p[y[i]],1,0);
jia(x[i],1);
jia(y[i],1);
if(p[x[i]]>p[y[i]])
++ans;
printf("%lld\n",ans);
}
}