题目大意是在能够改变两个数的位置的情况下计算逆序对数
这因为是动态记录逆序对
本来单纯逆序对只要用树状数组计算即可，但这里因为更新，所以利用TReap树的删点和增加点来进行更新
大致是把每个树状数组所管理的点都放在对应的Treap树下，
这样x-=lowbit(x)下来，正好访问到是所有比他小范围下的点了
然后根据每棵访问到的Treap树有多少个节点是比当前值小的即可
每次交换ai , aj ， （i<j）只要考虑(i,j)范围内比ai大的数，比aj小的数，然后加加减减即可
如果ai!=aj也是要加减1
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 #define N 20005 5 6 struct Node{ 7 int l , r , val , sz , pri , cnt; 8 //cnt表示当前位置相同的数有多少个，pri表示优先级，sz表示这棵子树所含有的节点总个数 9 Node(){ 10 l = r = 0; 11 cnt = sz = 1 , pri = rand(); 12 val = 0; 13 } 14 Node(int v){ 15 Node(); 16 val = v; 17 } 18 }; 19 #define ls node[x].l 20 #define rs node[x].r 21 namespace Treap{ 22 int tot;//Treap Node节点的总个数 23 int A[N];//有n棵treap树，A[]表示每棵treap树的起始位置 24 Node node[N*50]; 25 void init(){ 26 node[0] = Node(); 27 node[0].cnt = node[0].sz = 0; 28 memset(A , 0 , sizeof(A)); 29 tot = 0; 30 } 31 int newNode(int v){ 32 ++tot; 33 node[tot].cnt = node[tot].sz = 1; 34 node[tot].l = node[tot].r = 0; 35 node[tot].pri = rand(); 36 node[tot].val = v; 37 return tot; 38 } 39 void push_up(int x) { 40 // cout<<"here: "<<x<<" "<<ls<<" "<<rs<<endl; 41 if(x>0) 42 node[x].sz = node[ls].sz+node[rs].sz+node[x].cnt; 43 } 44 void rotL(int &x){ 45 int y = rs; 46 rs = node[y].l; 47 node[y].l = x; 48 49 push_up(x); 50 push_up(y); 51 x = y; 52 } 53 void rotR(int &x){ 54 int y = ls; 55 ls = node[y].r; 56 node[y].r = x; 57 58 push_up(x); 59 push_up(y); 60 x = y; 61 } 62 void insert(int &x , int v){ 63 // cout<<x<<" "<<v<<endl; 64 if(x == 0) x = newNode(v); 65 else if(node[x].val>v){ 66 insert(ls , v); 67 if(node[ls].pri>node[x].pri) rotR(x); 68 } 69 else if(node[x].val<v){ 70 insert(rs , v); 71 if(node[rs].pri>node[x].pri) rotL(x); 72 } 73 else node[x].cnt++; 74 push_up(x); 75 // cout<<x<<" "<<v<<" "<<"endd"<<endl; 76 } 77 void erase(int &x , int v){ 78 if(x == 0) return ; 79 else if(v<node[x].val) erase(ls , v); 80 else if(v>node[x].val) erase(rs , v); 81 else { 82 node[x].cnt--; 83 if(node[x].cnt<=0){ 84 if(ls==0&&rs==0) x = 0; 85 else if(ls == 0) x = rs; 86 else if(rs == 0) x = ls; 87 else{ 88 if(node[ls].pri <node[rs].pri) rotL(x),erase(ls,v); 89 else rotR(x) , erase(rs , v); 90 } 91 } 92 } 93 push_up(x); 94 } 95 int getCnt(int x , int v){//从x号节点出发找到对应的子树下小于等于v的值的个数 96 if(x == 0) return 0; 97 int ans = 0; 98 if(node[x].val>v) ans = getCnt(ls , v); 99 else if(node[x].val<v) ans = node[x].cnt+node[ls].sz+getCnt(rs , v); 100 else ans = node[x].cnt+node[ls].sz; 101 return ans; 102 } 103 } 104 int n , m , h[N] , a[N] , tot; 105 //树状数组部分 106 #define lowbit(x) x&(-x) 107 void Add(int id , int v) 108 { 109 for(int x=id ; x<=n ; x+=lowbit(x)){ 110 Treap::insert(Treap::A[x] , v); 111 } 112 } 113 void Erase(int id , int v) 114 { 115 for(int x=id ; x<=n ; x+=lowbit(x)){ 116 Treap::erase(Treap::A[x] , v); 117 } 118 } 119 int getSum(int p , int v)//cal 1~p区间内小于等于v的值的个数 120 { 121 int sum = 0; 122 for(int x=p ; x>0 ; x-=lowbit(x)){ 123 sum+=Treap::getCnt(Treap::A[x] , v); 124 } 125 return sum; 126 } 127 int getSumMin(int p , int v)//cal 1~p区间内小于v的值的个数 128 { 129 v--;//important保证等于的情况被排除 130 return getSum(p , v); 131 } 132 133 int main() 134 { 135 // freopen("a.in" , "r" , stdin); 136 scanf("%d" , &n); 137 for(int i=1 ; i<=n ; i++){ 138 scanf("%d" , &h[i]); 139 a[i] = h[i]; 140 } 141 sort(a+1 , a+n+1); 142 tot = unique(a+1 , a+n+1)-(a+1); 143 Treap::init(); 144 int sum = 0; 145 for(int i=1 ; i<=n ; i++){ 146 h[i] = lower_bound(a+1 , a+tot+1 , h[i])-a; 147 Add(i , h[i]); 148 sum+=i-1-getSum(i-1 , h[i]); 149 } 150 printf("%d " , sum); 151 152 scanf("%d" , &m); 153 while(m--){ 154 // for(int i=1 ; i<=n ; i++) 155 // cout<<h[i]<<" "; 156 // cout<<endl; 157 int ai , bi; 158 scanf("%d%d" , &ai , &bi); 159 if(ai>bi) swap(ai , bi); 160 if(h[ai]<h[bi]) sum++; 161 else if(h[ai]>h[bi]) sum--; 162 else{ 163 printf("%d " , sum); 164 continue; 165 } 166 int add = 0; 167 if(bi-ai>1){ 168 add += getSumMin(bi-1 , h[bi])-getSumMin(ai , h[bi]); 169 add -= (bi-ai-1)-(getSum(bi-1 , h[bi])-getSum(ai , h[bi])); 170 add += (bi-ai-1)-(getSum(bi-1 , h[ai])-getSum(ai , h[ai])); 171 add -= getSumMin(bi-1 , h[ai])-getSumMin(ai , h[ai]); 172 } 173 174 sum += add; 175 176 Erase(ai , h[ai]); 177 Erase(bi , h[bi]); 178 Add(ai , h[bi]); 179 Add(bi , h[ai]); 180 swap(h[ai] , h[bi]); 181 printf("%d " , sum); 182 } 183 return 0; 184 }