Loj 2639 不勤劳的图书管理员

Posted on | Edited on | Views:

分块 + 树状数组处理动态逆序对.

先用树状数组扫一遍,算出初始的答案,考虑交换 $a_x,a_y(x<y)​$ 对答案造成的影响.

$a_x$ 与 $a_y$ 的贡献, $a_x$ 与 $[x+1,y-1]$ 内元素的贡献,以及 $a_y$ 与 $[x+1,y-1]$ 内元素的贡献需要重新计算.

可以先把原来的贡献减掉,重新计算后加回去,于是问题转化为求一个元素与一段区间内的元素产生的贡献.

考虑分块,对每一块开两个树状数组,分别维护该块内 $\le i$ 的元素数目,以及它们的权值和.

询问贡献时,边角暴力,整块的在树状数组中查询,每次修改最多会影响两个块,在对应的树状数组中直接改即可.

时间复杂度 $O(n\sqrt n\log n)$ ,空间复杂度 $O(n\sqrt n)$ .

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=1e9+7;
int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
void inc(int &a,int b)
{
	a=add(a,b);
}
int mul(int a,int b)
{
	return 1LL * a * b % P;
}
const int MAXN=5e4+10,S=320;
int n,m,B,bel[MAXN],a[MAXN],val[MAXN];
int lp[S],rp[S];
struct FenwickTree
{
	int bit[MAXN];
#define lowbit(x) x&(-x)
	void upd(int x,int c)
	{
		inc(c,P);
		for(;x<=n;x+=lowbit(x))
			inc(bit[x],c);
	}
	int sum(int x)
	{
		int s=0;
		for(;x;x-=lowbit(x))
			inc(s,bit[x]);
		return s;
	}
	int query(int l,int r)
	{
		return add(sum(r),P-sum(l-1));
	}
}T[S][2],tmp[2]; // 0:cnt 1:sum
int ans=0;
int calc(int x,int L,int R,int dir)
{
	if(L>R)
		return 0;
	int cnt=0,sum=0;
	if(bel[L]==bel[R])
	{
		for(int i=L;i<=R;++i)
			if(dir^(a[i]<a[x]))
				++cnt,inc(sum,val[i]);
	}
	else
	{
		for(int i=L;i<=rp[bel[L]];++i)
			if(dir^(a[i]<a[x]))
				++cnt,inc(sum,val[i]);
		for(int i=lp[bel[R]];i<=R;++i)
			if(dir^(a[i]<a[x]))
				++cnt,inc(sum,val[i]);
		for(int i=bel[L]+1;i<=bel[R]-1;++i)
		{
			if(!dir)
			{
				inc(cnt,T[i][0].query(1,a[x]-1));
				inc(sum,T[i][1].query(1,a[x]-1));
			}
			else
			{
				inc(cnt,T[i][0].query(a[x]+1,n));
				inc(sum,T[i][1].query(a[x]+1,n));
			}
		}
	}
	return add(mul(cnt,val[x]),sum);
}
void solve(int x,int y)
{
	if(x==y)
		return;
	if(x>y)
		swap(x,y);
	if(a[x]>a[y])
		inc(ans,P-add(val[x],val[y]));
	inc(ans,P-calc(x,x+1,y-1,0));
	inc(ans,P-calc(y,x+1,y-1,1));
	T[bel[x]][0].upd(a[x],-1),T[bel[x]][1].upd(a[x],-val[x]);
	T[bel[y]][0].upd(a[y],-1),T[bel[y]][1].upd(a[y],-val[y]);
	swap(a[x],a[y]),swap(val[x],val[y]);
	T[bel[x]][0].upd(a[x],1),T[bel[x]][1].upd(a[x],val[x]);
	T[bel[y]][0].upd(a[y],1),T[bel[y]][1].upd(a[y],val[y]);
	if(a[x]>a[y])
		inc(ans,add(val[x],val[y]));
	inc(ans,calc(x,x+1,y-1,0));
	inc(ans,calc(y,x+1,y-1,1));
}
int main()
{
	n=read(),m=read();
	B=sqrt(n);
	for(int i=1;i<=n;++i)
	{
		a[i]=read(),val[i]=read();
		bel[i]=(i-1)/B+1;
		lp[bel[i]]=(bel[i]-1)*B+1;
		rp[bel[i]]=lp[bel[i]]+B-1;
		int cnt=tmp[0].query(a[i]+1,n),sum=tmp[1].query(a[i]+1,n);
		inc(ans,mul(cnt,val[i]));
		inc(ans,sum);
		tmp[0].upd(a[i],1),tmp[1].upd(a[i],val[i]);
		T[bel[i]][0].upd(a[i],1),T[bel[i]][1].upd(a[i],val[i]);
	}
	rp[bel[n]]=n;
	for(int i=1;i<=m;++i)
	{
		solve(read(),read());
		printf("%d\n",ans);
	}
	return 0;
}