题目大意是在能够改变两个数的位置的情况下计算逆序对数
这因为是动态记录逆序对
本来单纯逆序对只要用树状数组计算即可，但这里因为更新，所以利用TReap树的删点和增加点来进行更新
大致是把每个树状数组所管理的点都放在对应的Treap树下，
这样x-=lowbit(x)下来，正好访问到是所有比他小范围下的点了
然后根据每棵访问到的Treap树有多少个节点是比当前值小的即可
每次交换ai , aj ， （i<j）只要考虑(i,j)范围内比ai大的数，比aj小的数，然后加加减减即可
如果ai!=aj也是要加减1
#include <bits/stdc++.h> using namespace std;
#define N 20005 struct Node{
int l , r , val , sz , pri , cnt;
//cnt表示当前位置相同的数有多少个，pri表示优先级，sz表示这棵子树所含有的节点总个数
Node(){
l = r = ;
cnt = sz = , pri = rand();
val = ;
}
Node(int v){
Node();
val = v;
}
};
#define ls node[x].l
#define rs node[x].r
namespace Treap{
int tot;//Treap Node节点的总个数
int A[N];//有n棵treap树，A[]表示每棵treap树的起始位置
Node node[N*];
void init(){
node[] = Node();
node[].cnt = node[].sz = ;
memset(A , , sizeof(A));
tot = ;
}
int newNode(int v){
++tot;
node[tot].cnt = node[tot].sz = ;
node[tot].l = node[tot].r = ;
node[tot].pri = rand();
node[tot].val = v;
return tot;
}
void push_up(int x) {
// cout<<"here: "<<x<<" "<<ls<<" "<<rs<<endl;
if(x>)
node[x].sz = node[ls].sz+node[rs].sz+node[x].cnt;
}
void rotL(int &x){
int y = rs;
rs = node[y].l;
node[y].l = x; push_up(x);
push_up(y);
x = y;
}
void rotR(int &x){
int y = ls;
ls = node[y].r;
node[y].r = x; push_up(x);
push_up(y);
x = y;
}
void insert(int &x , int v){
// cout<<x<<" "<<v<<endl;
if(x == ) x = newNode(v);
else if(node[x].val>v){
insert(ls , v);
if(node[ls].pri>node[x].pri) rotR(x);
}
else if(node[x].val<v){
insert(rs , v);
if(node[rs].pri>node[x].pri) rotL(x);
}
else node[x].cnt++;
push_up(x);
// cout<<x<<" "<<v<<" "<<"endd"<<endl;
}
void erase(int &x , int v){
if(x == ) return ;
else if(v<node[x].val) erase(ls , v);
else if(v>node[x].val) erase(rs , v);
else {
node[x].cnt--;
if(node[x].cnt<=){
if(ls==&&rs==) x = ;
else if(ls == ) x = rs;
else if(rs == ) x = ls;
else{
if(node[ls].pri <node[rs].pri) rotL(x),erase(ls,v);
else rotR(x) , erase(rs , v);
}
}
}
push_up(x);
}
int getCnt(int x , int v){//从x号节点出发找到对应的子树下小于等于v的值的个数
if(x == ) return ;
int ans = ;
if(node[x].val>v) ans = getCnt(ls , v);
else if(node[x].val<v) ans = node[x].cnt+node[ls].sz+getCnt(rs , v);
else ans = node[x].cnt+node[ls].sz;
return ans;
}
}
int n , m , h[N] , a[N] , tot;
//树状数组部分
#define lowbit(x) x&(-x)
void Add(int id , int v)
{
for(int x=id ; x<=n ; x+=lowbit(x)){
Treap::insert(Treap::A[x] , v);
}
}
void Erase(int id , int v)
{
for(int x=id ; x<=n ; x+=lowbit(x)){
Treap::erase(Treap::A[x] , v);
}
}
int getSum(int p , int v)//cal 1~p区间内小于等于v的值的个数
{
int sum = ;
for(int x=p ; x> ; x-=lowbit(x)){
sum+=Treap::getCnt(Treap::A[x] , v);
}
return sum;
}
int getSumMin(int p , int v)//cal 1~p区间内小于v的值的个数
{
v--;//important保证等于的情况被排除
return getSum(p , v);
} int main()
{
// freopen("a.in" , "r" , stdin);
scanf("%d" , &n);
for(int i= ; i<=n ; i++){
scanf("%d" , &h[i]);
a[i] = h[i];
}
sort(a+ , a+n+);
tot = unique(a+ , a+n+)-(a+);
Treap::init();
int sum = ;
for(int i= ; i<=n ; i++){
h[i] = lower_bound(a+ , a+tot+ , h[i])-a;
Add(i , h[i]);
sum+=i--getSum(i- , h[i]);
}
printf("%d\n" , sum); scanf("%d" , &m);
while(m--){
// for(int i=1 ; i<=n ; i++)
// cout<<h[i]<<" ";
// cout<<endl;
int ai , bi;
scanf("%d%d" , &ai , &bi);
if(ai>bi) swap(ai , bi);
if(h[ai]<h[bi]) sum++;
else if(h[ai]>h[bi]) sum--;
else{
printf("%d\n" , sum);
continue;
}
int add = ;
if(bi-ai>){
add += getSumMin(bi- , h[bi])-getSumMin(ai , h[bi]);
add -= (bi-ai-)-(getSum(bi- , h[bi])-getSum(ai , h[bi]));
add += (bi-ai-)-(getSum(bi- , h[ai])-getSum(ai , h[ai]));
add -= getSumMin(bi- , h[ai])-getSumMin(ai , h[ai]);
} sum += add; Erase(ai , h[ai]);
Erase(bi , h[bi]);
Add(ai , h[bi]);
Add(bi , h[ai]);
swap(h[ai] , h[bi]);
printf("%d\n" , sum);
}
return ;
}