树套树
树套树有很多种，可以是树状数组套线段树，也可以是线段树套线段树，线段树套平衡树等等。我们这里先只讨论树状数组套线段树。
该数据结构实现在主席树基础上。
所谓树套树，就是一颗树上面的每一个点，不仅表示一个区间信息，还是一个树，emmm可见最外面这棵树有多大，当然空间会炸，但是注意到树上面的结点大部分都是空结点，所以可以省掉大量空间。一般来说，最外面那棵树是区间线段树，对应的是原序列中的区间。里面的树是权值线段树，对应的是外面那棵树所表示的区间内所有元素的值，所组成的一颗树。
大概就是这个样子，剩下的几种树套树也都是这个形式。
那么树状数组套线段树，就是，树状数组上的每个点，表示的区间是[i-lowbit(i)+1, i]，同时还是一个权值线段树，这颗权值线段树是建立在原序列[i-lowbit(i)+1, i]区间上的。
树套树的思想部分就这，接下来看实现。
我们在解决静态区间第k大/小时，只需维护前缀和线段树，然后两个线段树相减可以得到任一区间内元素组成的权值线段树，这样可以很容易求得第k大，时空复杂度均为O(nlogn)，但是当题目要求要更改某些元素值时，就没辙了。。也就是动态区间第k大/小，这个时候需要用到树套树，那么需要更改元素值时，只需更改logn棵权值线段树(跟普通树状数组更改单点值一样)，然后每颗权值线段树的更改时间复杂度也为logn，加起来就是O(log^2n)；查询的时候，想要表示出某个区间，其实就是logn棵权值线段树减去另外logn棵权值线段树(跟普通树状数组查询一样)，比如要查询[l, r]，[1, r]可以有logn棵树表示，[1, l-1]也可以由logn棵树表示，两个相减就得到[l, r]的权值线段树了。
树的变量定义：
struct tree{
int left, right, w; //左右孩子和结点权值 区间信息在递归函数中给出
}tree[maxn*200]; //数据池
int root[maxn]; //树状数组每个结点在数据池中的下标
int top; //数据池使用情况
int len1, len2, q1[100], q2[100];用到的最多的函数：
add函数：在某个结点所表示的子树上更新某个点的值。
//l,r表示区间信息，x表示源结点，k表示要更改的权值点，flag表示该点出权值+1还是-1
inline int add(int x, int l, int r, int k, int flag) {
int tmp; //新结点为tmp
if (x) tmp = x; //这两行代码至关重要，下面会讲
else tmp = ++top;
if (l == r) {
tree[tmp].w = tree[x].w + flag;
return tmp;
}
int mid = (l + r) >> 1;
if (k <= mid) { //k在左区间时，源节点的右区间直接赋给tmp即可，然后进一步修改左区间
tree[tmp].left = add(tree[x].left, l, mid, k, flag);
tree[tmp].right = tree[x].right;
} else {
tree[tmp].left = tree[x].left;
tree[tmp].right = add(tree[x].right, mid + 1, r, k, flag);
}
tree[tmp].w = tree[tree[tmp].left].w + tree[tree[tmp].right].w;
return tmp;
}
在代码中有两行是用来节约大量空间的，当使用静态主席树时，直接++top。
if (x) tmp = x;
else tmp = ++top;在静态主席树中，每颗权值线段树都是在前一棵树的基础上更改值，即线段树中的结点可能是被多颗树所共用的，不可随意更改。而在动态主席树中，每颗权值线段树是在它的上一个版本的权值线段树的基础上进行修改的，树里面的结点(除了空结点)就它这一个点在使用，因此当要修改的结点不是空结点时，我们可以直接在该源结点上进行修改，不需要顾忌其它因素。
update函数：更改单点值
没啥好说的。。在下标i出把权值线段树中k的值增加flag，共更新logn棵权值线段树。
inline void update(int i, int k, int flag){
while (i<=n){
root[i] = add(root[i], k, flag, 1, cnt);
i += lowbit(i);
}
return;
}查询函数src: 因题而定的查询操作
由于是logn棵线段树相减，没办法递归，所以使用迭代。表示[1, l-1]的logn棵权值线段树的树根们放在q1[maxn]里，共有len1棵；表示[1, r]的logn棵权值线段树的树根们放在q2[maxn]里，共有len2棵。
inline int src(int x, int y, int k, int l, int r, int flag){ //区间内查询比k小的数的个数
len1 = len2 = 0;
int ans = 0;
x--; //这里x，y表示要求[x, y]区间的信息
while (x){
q1[++len1] = root[x];
x -= lowbit(x);
}
while (y){
q2[++len2] = root[y];
y -= lowbit(y);
}
int mid;
while (l<r){
mid = (l+r)>>1;
x = y = 0; //这里x，y表示所求区间内左右孩子各自的权值
for (int i=1; i<=len2; i++) x += tree[tree[q2[i]].left].w, y += tree[tree[q2[i]].right].w;
for (int i=1; i<=len1; i++) x -= tree[tree[q1[i]].left].w, y -= tree[tree[q1[i]].right].w;
if (flag==2)
if (k<=mid){
r = mid;
for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].left;
for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].left;
}else{
l = mid+1, ans += x;
for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].right;
for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].right;
}
else
if (k<=mid){
r = mid, ans += y;
for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].left;
for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].left;
}else{
l = mid+1;
for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].right;
for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].right;
}
}
return ans;
}题目
P2617 Dynamic Rankings
动态区间第k小，，，以后离散化直接unordered_map比较好。。。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int n, m, cnt;
int nums[maxn];
//mp12分别表示原数组和询问中数值对应的编号,,,mp4表示离散化值对应的原数 原数->编号->离散化值->原数 12->3->4
int mp1[maxn], mp2[maxn], mp3[maxn*2], mp4[maxn*2];
int se[maxn];
struct z{
int w, idx; //w表示原来的值， v表示离散化后的值
}disc[maxn*2];
struct y{
int opt, l, r, k;
}query[maxn];
struct tree{
int left, right, w;
}tree[maxn*400];
int top, root[maxn];
queue<int> q1, q2;
inline int lowbit(int i){return i&(-i);}
inline int add(int x, int k, int flag, int l, int r){ //给结点x所表示的线段树加上权值k，flag=1表示加，-1表示减
int tmp;
if (x) tmp = x;
else tmp = ++top;
if (l==r){
tree[tmp].w = flag + tree[x].w;
return tmp;
}
int mid = (l+r)>>1;
if (k<=mid){
tree[tmp].left = add(tree[x].left, k, flag, l, mid);
tree[tmp].right = tree[x].right;
}else{
tree[tmp].left = tree[x].left;
tree[tmp].right = add(tree[x].right, k, flag, mid+1, r);
}
tree[tmp].w = tree[tree[tmp].left].w + tree[tree[tmp].right].w;
return tmp;
}
inline void update(int i, int k, int flag){
while (i<=n){
root[i] = add(root[i], k, flag, 1, cnt);
i += lowbit(i);
}
return;
}
inline int src(int x, int y, int l, int r, int k){ //区间[x+1, y]内第k小
while (!q1.empty()) q1.pop();
while (!q2.empty()) q2.pop();
while (x){
q1.push(root[x]);
x -= lowbit(x);
}
while (y){
q2.push(root[y]);
y -= lowbit(y);
}
int mid, left, len1, len2, tmp;
while (l<r){
mid = (l+r) >> 1;
left = x = 0;
len1 = q1.size(),len2 = q2.size();
while (len2--){
tmp = q2.front(); q2.pop();
x += tree[tree[tmp].left].w;
q2.push(tmp);
}
while (len1--){
tmp = q1.front(); q1.pop();
x -= tree[tree[tmp].left].w;
q1.push(tmp);
}
if (k <= x){
r = mid;
len1 = q1.size(),len2 = q2.size();
while (len2--){
tmp = q2.front(); q2.pop();
q2.push(tree[tmp].left);
}
while (len1--){
tmp = q1.front(); q1.pop();
q1.push(tree[tmp].left);
}
}else{
l = mid+1, k -= x;
len1 = q1.size(),len2 = q2.size();
while (len2--){
tmp = q2.front(); q2.pop();
q2.push(tree[tmp].right);
}
while (len1--){
tmp = q1.front(); q1.pop();
q1.push(tree[tmp].right);
}
}
}
return l;
}
inline int read(){
int x=0; char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9'){
x = x*10 + ch-'0';
ch=getchar();
}
return x;
}
inline char cread(){
char ch=getchar();
while (!isalpha(ch)) ch=getchar();
return ch;
}
inline bool cmp1(struct z a, struct z b){
return a.w < b.w;
}
int main(){
n = read(), m = read();
for (int i=1; i<=n; i++) nums[i] = read();
for (int i=1; i<=m; i++){
if (cread()=='Q'){
query[i].opt = 1;
query[i].l = read(), query[i].r = read(), query[i].k = read();
}else{
query[i].opt = 2;
query[i].l = read(), query[i].r = read();
}
}
for (int i=1; i<=n; i++) disc[i].w = nums[i], mp1[i] = i, disc[i].idx = i;
cnt = n;
for (int i=1; i<=m; i++) if (query[i].opt==2){
cnt++;
disc[cnt].w = query[i].r, mp2[i] = cnt, disc[cnt].idx = cnt;
}
sort (disc+1, disc+cnt+1, cmp1);
for (int i=1; i<=cnt; i++){
mp3[disc[i].idx] = i;
mp4[i] = disc[i].w;
}
top = 0;
for (int i=1; i<=n; i++) se[i] = i;
for (int i=1; i<=n; i++){
update(i, mp3[se[i]], 1);
}
for (int i=1; i<=m; i++){
if (query[i].opt==2){
update(query[i].l, mp3[se[query[i].l]], -1);
se[query[i].l] = mp2[i];
update(query[i].l, mp3[se[query[i].l]], 1);
}else{
int ans = src(query[i].l-1, query[i].r, 1, cnt, query[i].k);
printf ("%d\n", mp4[ans]);
}
}
return 0;
}P3157 动态逆序对
每次去掉一个点，求每次更改前的逆序对数。
先求得原始序列的逆序对数ans，然后去掉一个元素时，剩下的逆序对数是ans-前面比该元素小的个数-后面比该元素大的个数。然后注意更新。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
typedef long long ll;
int n, m;
int nums[maxn], mp[maxn];
ll c[maxn], ans;
struct tree{
int left, right, w;
}tree[maxn*150];
int root[maxn], top;
int len1, len2, q1[maxn], q2[maxn];
inline int lowbit(int i){
return i & -i;
}
inline void update_(int i, int k){
while (i<=n){
c[i] += k;
i += lowbit(i);
}
return;
}
inline ll sum_(int i){
ll ans = 0;
while (i){
ans += c[i];
i -= lowbit(i);
}
return ans;
}
inline int add(int x, int k, int flag, int l, int r){ //
int tmp;
if (x) tmp = x;
else tmp = ++top;
if (l==r){
tree[tmp].w = tree[x].w + flag;
return tmp;
}
int mid = (l+r)>>1;
if (k<=mid){
tree[tmp].left = add(tree[x].left, k, flag, l, mid);
tree[tmp].right = tree[x].right;
}else{
tree[tmp].left = tree[x].left;
tree[tmp].right = add(tree[x].right, k, flag, mid+1, r);
}
tree[tmp].w = tree[tree[tmp].left].w + tree[tree[tmp].right].w;
return tmp;
}
inline void update(int i, int k, int flag){
while (i<=n){
root[i] = add(root[i], k, flag, 1, n);
i += lowbit(i);
}
return;
}
inline int src(int x, int y, int k, int l, int r, int flag){ //区间内查询比k小的数的个数
len1 = len2 = 0;
int ans = 0;
x--;
while (x){
q1[++len1] = root[x];
x -= lowbit(x);
}
while (y){
q2[++len2] = root[y];
y -= lowbit(y);
}
int mid;
while (l<r){
mid = (l+r)>>1;
x = y = 0;
for (int i=1; i<=len2; i++) x += tree[tree[q2[i]].left].w, y += tree[tree[q2[i]].right].w;
for (int i=1; i<=len1; i++) x -= tree[tree[q1[i]].left].w, y -= tree[tree[q1[i]].right].w;
if (flag==2)
if (k<=mid){
r = mid;
for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].left;
for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].left;
}else{
l = mid+1, ans += x;
for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].right;
for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].right;
}
else
if (k<=mid){
r = mid, ans += y;
for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].left;
for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].left;
}else{
l = mid+1;
for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].right;
for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].right;
}
}
return ans;
}
int main(){
int x;
ans = top = 0;
scanf ("%d %d", &n, &m);
for (int i=1; i<=n; i++){
scanf ("%d", nums+i);
mp[nums[i]] = i;
update(i, nums[i], 1);
update_(nums[i], 1);
ans += sum_(n) - sum_(nums[i]);
}
for (int i=1; i<=m; i++){
scanf ("%d", &x);
printf ("%lld\n", ans);
ans -= src(1, mp[x], x, 1, n, 1) + src(mp[x], n, x, 1, n, 2);
update(mp[x], x, -1);
}
return 0;
}
/*
1 5 3 4 2
*/P3380 【模板】二逼平衡树（树套树）
比较恶心的一题，，因为询问的操作种类比较多，代码长
这里我在求前驱后继时，先查询k的排名x，然后输出排名x-1和x+1的数。
/*树状数组套主席树*/
#include <bits/stdc++.h>
using namespace std;
const int maxn = 50005;
int n, m;
int nums[maxn], se[maxn*2], cnt; //cnt是离散后的最大编号
struct opt{
int opt;
int l, r, k;
int pos;
}query[maxn];
unordered_map<int, int> mp1, mp2; //mp1: 原数值->离散值 mp2:离散值->原数值
struct tree{
int left, right, w;
}tree[maxn*250];
int root[maxn], top;
int len1, len2, q1[maxn], q2[maxn];
int lowbit(int i){
return i & -i;
}
int add(int x, int k, int flag, int l, int r){
int tmp = ++top;
if (l==r){
tree[tmp].w = tree[x].w + flag;
return tmp;
}
int mid = (l+r) >> 1;
if (k <= mid){
tree[tmp].left = add(tree[x].left, k, flag, l, mid);
tree[tmp].right = tree[x].right;
}else{
tree[tmp].left = tree[x].left;
tree[tmp].right = add(tree[x].right, k, flag, mid+1, r);
}
tree[tmp].w = tree[tree[tmp].left].w + tree[tree[tmp].right].w;
return tmp;
}
void update(int i, int k, int flag){
while (i<=n){
root[i] = add(root[i], k, flag, 1, cnt);
i += lowbit(i);
}
return;
}
int src1(int x, int y, int k){ //区间[x, y]内，k排第几
len1 = len2 = 0, x -= 1;
while (x){
q1[++len1] = root[x];
x -= lowbit(x);
}
while (y){
q2[++len2] = root[y];
y -= lowbit(y);
}
int l = 1, r = cnt, mid, ans = 0;
while (l<r){
mid = (l+r) >> 1, x = y = 0;
for (int i=1; i<=len2; i++) x += tree[tree[q2[i]].left].w;
for (int i=1; i<=len1; i++) x -= tree[tree[q1[i]].left].w;
if (k>mid){
ans += x, l = mid+1;
for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].right;
for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].right;
}else{
r = mid;
for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].left;
for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].left;
}
}
return ans+1;
}
int src2(int x, int y, int k){ //区间[x, y]内，排第k的数
len1 = len2 = 0, x -= 1;
while (x){
q1[++len1] = root[x];
x -= lowbit(x);
}
while (y){
q2[++len2] = root[y];
y -= lowbit(y);
}
int l = 1, r = cnt, mid;
while (l<r){
mid = (l+r) >> 1, x = y = 0;
for (int i=1; i<=len2; i++) x += tree[tree[q2[i]].left].w;
for (int i=1; i<=len1; i++) x -= tree[tree[q1[i]].left].w;
if (k>x){
k -= x, l = mid+1;
for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].right;
for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].right;
}else{
r = mid;
for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].left;
for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].left;
}
}
return l;
}
int src5(int x, int y, int k){ //区间[x, y]内，k的后继
int tmp = src1(x, y, k);
int tmpx = x, tmpy = y;
len1 = len2 = 0, x -= 1;
while (x){
q1[++len1] = root[x];
x -= lowbit(x);
}
while (y){
q2[++len2] = root[y];
y -= lowbit(y);
}
int l = 1, r = cnt, mid, ans = 0, tot = 0; //这个ans表示的是k的个数
for (int i=1; i<=len2; i++) tot += tree[q2[i]].w;
for (int i=1; i<=len1; i++) tot -= tree[q1[i]].w;
while (l<r){
mid = (l+r) >> 1;
if (k>mid){
l = mid+1;
for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].right;
for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].right;
}else{
r = mid;
for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].left;
for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].left;
}
}
for (int i=1; i<=len2; i++) ans += tree[q2[i]].w;
for (int i=1; i<=len1; i++) ans -= tree[q1[i]].w;
if (ans+tmp > tot) return -1;
return src2(tmpx, tmpy, ans + tmp);
}
int main(){
scanf ("%d %d", &n, &m);
for (int i=1; i<=n; i++) scanf ("%d", nums+i);
for (int i=1; i<=n; i++) se[i] = nums[i];
cnt = n;
for (int i=1; i<=m; i++){
scanf ("%d", &query[i].opt);
if (query[i].opt==3) scanf ("%d %d", &query[i].pos, &query[i].k);
else scanf ("%d %d %d", &query[i].l, &query[i].r, &query[i].k);
//if (query[i].opt>=3)
se[++cnt] = query[i].k;
}
sort (se+1, se+cnt+1);
mp1[se[1]] = 1, mp2[1] = se[1];
for (int i=2; i<=cnt; i++) if (se[i]!=se[i-1]){
mp1[se[i]] = mp1[se[i-1]]+1;
mp2[mp1[se[i]]] = se[i];
}
cnt = mp1.size(), top = 0;
for (int i=1; i<=n; i++) update(i, mp1[nums[i]], 1);
mp2[-1] = 2147483647;
for (int i=1; i<=m; i++){
if (query[i].opt==3){
update(query[i].pos, mp1[nums[query[i].pos]], -1);
nums[query[i].pos] = query[i].k;
update(query[i].pos, mp1[nums[query[i].pos]], 1);
continue;
}else if (query[i].opt==1){
printf ("%d\n", src1(query[i].l, query[i].r, mp1[query[i].k]));
continue;
}else if (query[i].opt==2){
printf ("%d\n", mp2[src2(query[i].l, query[i].r, query[i].k)]);
continue;
}else if (query[i].opt==4){
//src4(query[i].l, query[i].r, mp1[query[i].k]);
int tmp = src1(query[i].l, query[i].r, mp1[query[i].k]);
if (tmp==1) puts("-2147483647");
else printf ("%d\n", mp2[src2(query[i].l, query[i].r, tmp-1)]);
continue;
}else{
printf ("%d\n", mp2[src5(query[i].l, query[i].r, mp1[query[i].k])]);
}
}
return 0;
}P3759 [TJOI2017]不勤劳的图书管理员
类似于动态逆序对
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 50005, mod = 1e9 + 7;
int n, m;
int nums[maxn], nums1[maxn];
struct tree {
int left, right;
short int w;
int sum;
} tree[maxn * 200];
int root[maxn], top;
int len1, len2, q1[maxn], q2[maxn];
inline int lowbit(int i) { return i & -i; }
inline int add(int x, int l, int r, int k, int flag) {
int tmp;
if (x)
tmp = x;
else
tmp = ++top;
if (l == r) {
tree[tmp].w = tree[x].w + flag;
tree[tmp].sum = tree[tmp].w * nums[k];
return tmp;
}
int mid = (l + r) >> 1;
if (k <= mid) {
tree[tmp].left = add(tree[x].left, l, mid, k, flag);
tree[tmp].right = tree[x].right;
} else {
tree[tmp].left = tree[x].left;
tree[tmp].right = add(tree[x].right, mid + 1, r, k, flag);
}
tree[tmp].w = tree[tree[tmp].left].w + tree[tree[tmp].right].w;
tree[tmp].sum = (tree[tree[tmp].left].sum + tree[tree[tmp].right].sum) % mod;
return tmp;
}
inline void update(int i, int k, int flag) {
while (i <= n) {
root[i] = add(root[i], 1, n, k, flag);
i += lowbit(i);
}
return;
}
inline void src(int x, int y, int k, int flag, ll &t, ll &ans) { // t表示个数,, ans表示值 1大于 0小于
t = ans = 0;
if (x > y)
return;
len1 = len2 = 0;
x--;
while (x) {
q1[++len1] = root[x];
x -= lowbit(x);
}
while (y) {
q2[++len2] = root[y];
y -= lowbit(y);
}
int l = 1, r = n, mid;
ll left1, left2, right1, right2;
while (l < r) {
left1 = left2 = right1 = right2 = 0;
for (int i = 1; i <= len1; i++) left1 -= tree[tree[q1[i]].left].w;
for (int i = 1; i <= len2; i++) left1 += tree[tree[q2[i]].left].w;
for (int i = 1; i <= len1; i++) left2 -= tree[tree[q1[i]].left].sum;
for (int i = 1; i <= len2; i++) left2 += tree[tree[q2[i]].left].sum;
for (int i = 1; i <= len1; i++) right1 -= tree[tree[q1[i]].right].w;
for (int i = 1; i <= len2; i++) right1 += tree[tree[q2[i]].right].w;
for (int i = 1; i <= len1; i++) right2 -= tree[tree[q1[i]].right].sum;
for (int i = 1; i <= len2; i++) right2 += tree[tree[q2[i]].right].sum;
mid = (l + r) >> 1;
if (flag) {
if (k <= mid) {
t += right1, ans += right2, r = mid;
for (int i = 1; i <= len1; i++) q1[i] = tree[q1[i]].left;
for (int i = 1; i <= len2; i++) q2[i] = tree[q2[i]].left;
} else {
l = mid + 1;
for (int i = 1; i <= len1; i++) q1[i] = tree[q1[i]].right;
for (int i = 1; i <= len2; i++) q2[i] = tree[q2[i]].right;
}
} else {
if (k > mid) {
t += left1, ans += left2, l = mid + 1;
for (int i = 1; i <= len1; i++) q1[i] = tree[q1[i]].right;
for (int i = 1; i <= len2; i++) q2[i] = tree[q2[i]].right;
} else {
r = mid;
for (int i = 1; i <= len1; i++) q1[i] = tree[q1[i]].left;
for (int i = 1; i <= len2; i++) q2[i] = tree[q2[i]].left;
}
}
}
return;
}
inline int read() {
int x = 0;
char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x;
}
int main() {
int tmp, x, y;
ll now = 0, t, ans;
top = 0;
// scanf ("%d %d", &n, &m);
n = read(), m = read();
for (int i = 1; i <= n; i++) {
// scanf ("%d", &nums1[i]);
// scanf ("%d", &nums[nums1[i]]);
nums1[i] = read();
nums[nums1[i]] = read();
}
for (int i = 1; i <= n; i++) {
src(1, i - 1, nums1[i], 1, t, ans);
now += ans + t * nums[nums1[i]];
now %= mod;
update(i, nums1[i], 1);
}
for (int i = 1; i <= m; i++) {
// scanf ("%d %d", &x, &y);
x = read(), y = read();
src(1, x - 1, nums1[x], 1, t, ans);
now -= ans + t * nums[nums1[x]];
src(x + 1, n, nums1[x], 0, t, ans);
now -= ans + t * nums[nums1[x]];
update(x, nums1[x], -1);
src(1, y - 1, nums1[y], 1, t, ans);
now -= ans + t * nums[nums1[y]];
src(y + 1, n, nums1[y], 0, t, ans);
now -= ans + t * nums[nums1[y]];
update(y, nums1[y], -1);
swap(nums1[x], nums1[y]);
src(1, x - 1, nums1[x], 1, t, ans);
now += ans + t * nums[nums1[x]];
src(x + 1, n, nums1[x], 0, t, ans);
now += ans + t * nums[nums1[x]];
update(x, nums1[x], 1);
src(1, y - 1, nums1[y], 1, t, ans);
now += ans + t * nums[nums1[y]];
src(y + 1, n, nums1[y], 0, t, ans);
now += ans + t * nums[nums1[y]];
update(y, nums1[y], 1);
now %= mod;
now = (now + mod) % mod;
printf("%lld\n", now);
}
return 0;
}
0 条评论