分块+权值逆序对
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
int n, m, uu, vv, blc, bel[50005], ans, ccnt[50005], cval[500005], num[255];
int sum[255][255];
const int mod=1e9+7;
struct Node{
int idx, val;
}nd[50005], qwq[255][255];
bool cmp1(Node x, Node y){
return x.idx<y.idx;
}
int lb(int x){
return x&-x;
}
void bitAdd(int x, int y){
for(int i=x; i<=n; i+=lb(i)){
ccnt[i]++;
cval[i] = (cval[i] + y) % mod;
}
}
int bitQuery(int x, int &qaq){
int re=0;
for(int i=x; i; i-=lb(i)){
qaq += ccnt[i];
re = (re + cval[i]) % mod;
}
return re;
}
int query1(int l, int r, Node x){
if(l>r) return 0;
int re=0;
if(bel[l]==bel[r]){
for(int i=l; i<=r; i++)
if(nd[i].idx>x.idx)
re = (re + (nd[i].val+x.val)%mod) % mod;
}
else{
for(int i=bel[l]+1; i<=bel[r]-1; i++){
int pos=lower_bound(qwq[i]+1, qwq[i]+1+num[i], x, cmp1)-qwq[i];
int cnt=num[i]-pos+1;
re = (re + (ll)cnt * x.val) % mod;
re = (re + ((sum[i][num[i]] - sum[i][pos-1])%mod + mod)%mod) % mod;
}
for(int i=l; i<=bel[l]*blc; i++)
if(nd[i].idx>x.idx)
re = (re + (nd[i].val+x.val)%mod) % mod;
for(int i=(bel[r]-1)*blc+1; i<=r; i++)
if(nd[i].idx>x.idx)
re = (re + (nd[i].val+x.val)%mod) % mod;
}
return re;
}
int query2(int l, int r, Node x){
if(l>r) return 0;
int re=0;
if(bel[l]==bel[r]){
for(int i=l; i<=r; i++)
if(nd[i].idx<x.idx)
re = (re + (nd[i].val+x.val)%mod) % mod;
}
else{
for(int i=bel[l]+1; i<=bel[r]-1; i++){
int pos=lower_bound(qwq[i]+1, qwq[i]+1+num[i], x, cmp1)-qwq[i];
int cnt=pos-1;
re = (re + (ll)cnt * x.val) % mod;
if(cnt) re = (re + sum[i][cnt]) % mod;
}
for(int i=l; i<=bel[l]*blc; i++)
if(nd[i].idx<x.idx)
re = (re + (nd[i].val+x.val)%mod) % mod;
for(int i=(bel[r]-1)*blc+1; i<=r; i++)
if(nd[i].idx<x.idx)
re = (re + (nd[i].val+x.val)%mod) % mod;
}
return re;
}
void gouzao(int x){
num[x] = 0;
for(int i=(x-1)*blc+1; i<=min(x*blc, n); i++)
qwq[x][++num[x]] = nd[i];
sort(qwq[x]+1, qwq[x]+1+num[x], cmp1);
for(int i=1; i<=num[x]; i++){
sum[x][i] = qwq[x][i].val;
sum[x][i] = (sum[x][i] + sum[x][i-1]) % mod;
}
}
int main(){
cin>>n>>m;
blc = sqrt(n);
for(int i=1; i<=n; i++){
scanf("%d %d", &nd[i].idx, &nd[i].val);
bel[i] = (i - 1) / blc + 1;
}
for(int i=1; i<=n; i++)
qwq[bel[i]][++num[bel[i]]] = nd[i];
for(int i=1; i<=bel[n]; i++)
gouzao(i);
for(int i=1; i<=n; i++){
int tmp1=0, tmp2=0;
ans = (ans + bitQuery(n, tmp1) - bitQuery(nd[i].idx, tmp2)) % mod;
ans = (ans + (ll)(tmp1-tmp2)*nd[i].val) % mod;
bitAdd(nd[i].idx, nd[i].val);
}
while(m--){
scanf("%d %d", &uu, &vv);
if(uu>vv) swap(uu, vv);
ans = (ans - query1(uu+1, vv-1, nd[vv]) + mod) % mod;
ans = (ans - query2(uu+1, vv-1, nd[uu]) + mod) % mod;
if(nd[uu].idx>nd[vv].idx) ans = (ans - (nd[uu].val+nd[vv].val)%mod + mod) % mod;
swap(nd[uu], nd[vv]);
gouzao(bel[uu]); gouzao(bel[vv]);
ans = (ans + query1(uu+1, vv-1, nd[vv])) % mod;
ans = (ans + query2(uu+1, vv-1, nd[uu])) % mod;
if(nd[uu].idx>nd[vv].idx) ans = (ans + (nd[uu].val+nd[vv].val)%mod) % mod;
printf("%d
", ans);
}
return 0;
}