不勤劳的图书管理员

暴力可以AC

题目链接

先算出不修改时的答案;

对于的位置i贡献就是

$\Sigma_{j=1}^{jv[i])$

然后对于每一次修改,考虑对答案的影响就是y移到x减少的和x移到y增加的
而影响只会出现在(x,y)

具体就是:

(x,y)对x产生的逆序对,y对(x,y)产生的逆序对会失去

(x,y)对y产生的逆序对,x对(x,y)产生的逆序对会增加入答案

如何维护a[i]+a[j]?

用树套树维护(x,y)大于等于x的数个数这些数的和


不能用指针,不然空间会GG

要外层树状数组内层线段树,不然空间GG

外层线段树内层平衡树空间OK的,不过时间就呵呵了
机房某大佬卡了一上午常之后彻底弃疗,写了暴力


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
/*
Author: zxy_hhhh
date: 2018/12/05
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cmath>
#define rep(x,a,b) for (int x=int(a);x<=(int)(b);x++)
#define drp(x,a,b) for (int x=int(a);x>=(int)(b);x--)
#define cross(x,a) for (int x=hd[a];x;x=nx[x])
#define ll long long
using namespace std;
inline ll rd()
{
ll _x=0;int _ch=getchar(),_f=1;
for(;!isdigit(_ch)&&(_ch!='-')&&(_ch!=EOF);_ch=getchar());
if (_ch=='-'){_f=0;_ch=getchar();}
for(;isdigit(_ch);_ch=getchar()) _x=_x*10+_ch-'0';
return _f?_x:-_x;
}
void write(ll _x){if (_x>=10) write(_x/10),putchar(_x%10+'0'); else putchar(_x+'0'); }
inline void wrt(ll _x,char _p){if (_x<0) putchar('-'),_x=-_x; write(_x); if (_p) putchar(_p);}
#define mod 1000000007
#define mid ((l + r) >> 1)
#define lb(x) (x & -x)
#define maxn 50005
int n, a[maxn], w[maxn], m, Ans;
inline int Mod(int x) { return x < 0 ? (x + mod) : (x >= mod ? x - mod : x); }
namespace xtree {
struct node {
int sum,ls,rs;
}tr[20000000];
int cnt;
void insert(int &u, int l, int r, int x, int k) {
if (!u) u = ++cnt;
tr[u].sum = Mod(tr[u].sum + k);
if (l == r) return;
if (x <= mid)
insert(tr[u].ls, l, mid, x, k);
else
insert(tr[u].rs, mid + 1, r, x, k);
}
inline int query(int u, int l, int r, int ql, int qr) {
if (!u) return 0;
if (r < ql || l > qr) return 0;
if (ql <= l && r <= qr) return tr[u].sum;
return (query(tr[u].ls, l, mid, ql, qr) + query(tr[u].rs, mid + 1, r, ql, qr)) %
mod;
}
} // namespace xtree
struct {
int tr[maxn];
inline void update(int x, int k, int val) {
for (; x <= n; x += lb(x)) xtree::insert(tr[x], 1, n, k, val);
}
inline int query(int x, int L, int R) {
int ans = 0;
for (; x; x -= lb(x)) ans = Mod(ans + xtree::query(tr[x], 1, n, L, R));
return ans;
}
inline int query(int L, int R, int l, int r) {
return Mod(query(R, l, r) - query(L - 1, l, r));
}
} tr1, tr2;
int main() {
n = rd(), m = rd();
rep(i, 1, n) {
w[i] = rd(), a[i] = rd();
tr1.update(i, w[i], a[i]), tr2.update(i, w[i], 1);
Ans = Mod(Ans + tr1.query(i - 1, w[i], n)),
Ans = Mod(Ans + 1ll * tr2.query(i - 1, w[i], n) * a[i] % mod);
}
rep(i, 1, m) {
int x = rd(), y = rd();
if (x > y) swap(x, y);
if (x==y) {wrt(Ans,'\n');continue;}
Ans = Mod(Ans - tr1.query(x + 1, y - 1, w[y], n));
Ans = Mod(Ans + tr1.query(x + 1, y - 1, w[x], n));
Ans = Mod(Ans - tr1.query(x + 1, y - 1, 1, w[x]));
Ans = Mod(Ans + tr1.query(x + 1, y - 1, 1, w[y]));
Ans = Mod(Ans - 1ll * tr2.query(x + 1, y - 1, w[y], n) * a[y] % mod);
Ans = Mod(Ans + 1ll * tr2.query(x + 1, y - 1, w[x], n) * a[x] % mod);
Ans = Mod(Ans - 1ll * tr2.query(x + 1, y - 1, 1, w[x]) * a[x] % mod);
Ans = Mod(Ans + 1ll * tr2.query(x + 1, y - 1, 1, w[y]) * a[y] % mod);
if (w[x] > w[y])
Ans -= a[x] + a[y];
else
Ans += a[x] + a[y];
Ans=Mod(Ans);
tr1.update(x, w[x], -a[x]), tr1.update(x, w[y], a[y]);
tr1.update(y, w[y], -a[y]), tr1.update(y, w[x], a[x]);
tr2.update(x, w[x], -1), tr2.update(x, w[y], 1);
tr2.update(y, w[y], -1), tr2.update(y, w[x], 1);
swap(w[x], w[y]), swap(a[x], a[y]);
wrt(Ans, '\n');
}
//wrt(xtree::cnt,'\n');
}
avatar
about-zxy