[Aug17] Inversions

我爱长者,长者赐予我时间!(逃

(取个快递

(不会咕掉题解的233

题意

长度为n的序列,每次询问如果交换两个元素,序列中将会有多少个逆序对。(注意每次操作后会回复)。

思路

首先可以用BIT维护原序列逆序对个数。

考虑交换两个元素,显然只有中间部分会受影响。

用主席树维护求变换产生的贡献即可。

(karriganasta巨爷居然直接用BIT维护信息,高超做法)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#define S 32768
char buf[S];int len = 0,pos = 0;
char buf2[S],*pp = buf2;
inline char __getchar()
{
if(pos == len)pos = 0,len = fread(buf,1,S,stdin);if(pos == len)return '\0';
return buf[pos++];
}
inline void __putchar(char c) {if(pp == buf2 + S)fwrite(buf2,1,S,stdout),pp = buf2;*pp++ = c;}
inline void flush(){fwrite(buf2,1,pp - buf2,stdout);}
inline void putint(int x)
{
if(!x) {__putchar('0');return;}
if(x > 9) putint(x / 10);
__putchar((x % 10) ^ '0');
}
inline int getint()
{
int r = 0,s = 1;char c = __getchar();for(;!isdigit(c);c = __getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = __getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
const int N = 200020,alpha = 25;
typedef long long LL;
int n,q,a[N],b[N],ncnt = 0;
struct FenwickTree
{
FenwickTree(){memset(C,0,sizeof(C));}
int C[N << 1];
inline int lowbit(int x){return (x & (-x));}
inline void add(int p,int v){for(int i = p;i;i -= lowbit(i)) C[i] += v;}
inline int sum(int p){int ret = 0;for(int i = p;i < N;i += lowbit(i)) ret += C[i];return ret;}
}BIT;
struct FotileTree
{
int lc[N * alpha],rc[N * alpha],sum[N * alpha];
int root[N],sz;
FotileTree(){sz = 0;}
inline void insert(int &x,int y,int l,int r,int p)
{
x = ++sz;
lc[x] = lc[y];rc[x] = rc[y];sum[x] = sum[y] + 1;
if(l == r) return;
int mid = (l + r) >> 1;
if(p <= mid) insert(lc[x],lc[y],l,mid,p);
else insert(rc[x],rc[y],mid + 1,r,p);
}
inline int query(int x,int y,int l,int r,int L,int R)
{
if(L > R) return 0;
if(l == L && r == R) return sum[x] - sum[y];
int mid = (l + r) >> 1;
if(R <= mid) return query(lc[x],lc[y],l,mid,L,R);
if(L > mid) return query(rc[x],rc[y],mid + 1,r,L,R);
return query(lc[x],lc[y],l,mid,L,mid) + query(rc[x],rc[y],mid + 1,r,mid + 1,R);
}
}PT;
LL tot = 0;
int main()
{
n = getint(),q = getint();
for(int i = 1;i <= n;i++) b[i] = a[i] = getint();
std::sort(b + 1,b + n + 1);
ncnt = std::unique(b + 1,b + n + 1) - b - 1;
for(int i = 1;i <= n;i++) a[i] = std::lower_bound(b + 1,b + ncnt + 1,a[i]) - b;
for(int i = 1;i <= n;i++)
{
PT.insert(PT.root[i],PT.root[i - 1],1,ncnt,a[i]);
tot += BIT.sum(a[i] + 1);
BIT.add(a[i],1);
}
while(q--)
{
int x = getint(),y = getint();
if(x > y) std::swap(x,y);
if(x == y)
{
LL ret = tot;
if(a[x] > a[y]) ret--;if(a[x] < a[y]) ret++;
printf("%lld\n",ret);
}
else
{
LL ret = tot;
ret -= PT.query(PT.root[y - 1],PT.root[x],1,ncnt,1,a[x] - 1);
ret -= PT.query(PT.root[y - 1],PT.root[x],1,ncnt,a[y] + 1,ncnt);
ret += PT.query(PT.root[y - 1],PT.root[x],1,ncnt,a[x] + 1,ncnt);
ret += PT.query(PT.root[y - 1],PT.root[x],1,ncnt,1,a[y] - 1);
if(a[x] > a[y]) ret--;if(a[x] < a[y]) ret++;
printf("%lld\n",ret);
}
}
return 0;
}