```cpp
/*
Author: EnderDeer
Online Judge: Luogu
*/
#include<bits/stdc++.h>
#define int long long
#define mem(x) memset(x,0,sizeof(x))
using namespace std;
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();
return s * w;
}
int n,m;
int a[1000010];
int b[1000010];
int l[1000010],r[1000010];
int block,len;
int num[1000010];
int c[1000010];
int d[1000010];
int cnt;
void merge(int L, int R, int Mid){
int i = L;int j = Mid + 1;int k = L;
while(i <= Mid && j <= R){
if(c[i] <= c[j])d[k ++] = c[i ++];
else{
cnt += Mid - i + 1;
d[k ++] = c[j ++];
}
}
while(i <= Mid)d[k ++] = c[i ++];
while(j <= R)d[k ++] = c[j ++];
for(i = L; i <= R; i ++)c[i] = d[i];
}
void mergesort(int L, int R){
if(L < R){
int Mid = (L + R) / 2;
mergesort(L, Mid),mergesort(Mid + 1, R);
merge(L, R, Mid);
}
}
void swapp(int x,int y){
if(a[x] > a[y])cnt --;
if(a[y] > a[x])cnt ++;
int posl = num[x];
int posr = num[y];
if(posl == posr){
for(int i = x + 1;i <= y - 1;i ++){
if(a[i] > a[x])cnt ++;
if(a[i] < a[x])cnt --;
if(a[i] < a[y])cnt ++;
if(a[i] > a[y])cnt --;
}
return ;
}
for(int i = x + 1;i <= r[posl];i ++){
if(a[i] > a[x])cnt ++;
if(a[i] < a[x])cnt --;
if(a[i] < a[y])cnt ++;
if(a[i] > a[y])cnt --;
}
for(int i = posl + 1;i <= posr - 1;i ++){
if(b[l[i]] < a[x]){
int ll,rr,mid;
ll = l[i],rr = r[i];
while(ll < rr){
mid = (ll + rr) / 2;
if(b[mid] < a[x])ll = mid + 1;
else rr = mid - 1;
}
cnt -= ll - l[i] + 1;
}
if(b[r[i]] > a[x]){
int ll,rr,mid;
ll = l[i],rr = r[i];
while(ll < rr){
mid = (ll + rr) / 2;
if(b[mid] <= a[x])ll = mid + 1;
else rr = mid - 1;
}
cnt += r[i] - rr + 1;
}
if(b[l[i]] < a[y]){
int ll,rr,mid;
ll = l[i],rr = r[i];
while(ll < rr){
mid = (ll + rr) / 2;
if(b[mid] < a[y])ll = mid + 1;
else rr = mid - 1;
}
if(ll >= l[i] && b[ll] >= a[y])ll --;
cnt += ll - l[i] + 1;
}
if(b[r[i]] < a[y]){
int ll,rr,mid;
ll = l[i],rr = r[i];
while(ll < rr){
mid = (ll + rr) / 2;
if(b[mid] <= a[y])ll = mid + 1;
else rr = mid - 1;
}
cnt -= r[i] - rr + 1;
}
}
for(int i = l[posr];i <= y - 1;i ++){
if(a[i] > a[x])cnt ++;
if(a[i] < a[x])cnt --;
if(a[i] < a[y])cnt ++;
if(a[i] > a[y])cnt --;
}
swap(a[x],a[y]);
b[x] = a[x];
b[y] = a[y];
sort(b + l[num[x]],b + r[num[x]] + 1);
sort(b + l[num[y]],b + r[num[y]] + 1);
}
signed main(){
cin>>n;
block = sqrt(n);
len = ceil(n * 1.0 / block);
for(int i = 1;i <= len;i ++){
l[i] = (i - 1) * block + 1;
r[i] = i * block;
}
r[len] = n;
for(int i = 1;i <= n;i ++){
a[i] = read();
b[i] = a[i];
c[i] = b[i];
num[i] = (i - 1) / block + 1;
}
for(int i = 1;i <= len;i ++)sort(b + l[i],b + r[i] + 1);
mergesort(1,n);
cout<<cnt<<endl;
cin>>m;
while(m --){
int x,y;
x = read(),y = read();
if(x > y)swap(x,y);
if(a[x] == a[y]){
cout<<cnt<<endl;
continue;
}
swapp(x,y);
cout<<cnt<<endl;
}
return 0;
}
```
by EDqwq @ 2021-02-16 12:45:40
我自己都看晕了，估计又是什么傻逼错误但是我真看不出来了（
代码又长又臭的坏处/kk
by EDqwq @ 2021-02-16 12:55:11
你写了个啥啊，这题不是树套树吗/yun
by _5011_ @ 2021-02-16 13:22:34
@[w33z8kqrqk8zzzх33](/user/91127) 分块不行吗/kk
我在分块题单里找到的这个题啊/dk
by EDqwq @ 2021-02-16 13:23:57
https://www.luogu.com.cn/training/11849#problems
题单（
by EDqwq @ 2021-02-16 13:24:12
用根号ds写polylog题的都是邪教！!1
by _5011_ @ 2021-02-16 13:27:39
不帮我调代码，可恶！！1（不是
by EDqwq @ 2021-02-16 13:32:33
草这题不是Onm暴力吗/yiw
by Gemini7X @ 2021-02-16 13:48:04