正确的,确实是取模少了:
```c++
#include <bits/stdc++.h>
#define ll long long
const int N= 5e4+ 10, M= 2e5+ 10, inf= 1e9+ 10;
const ll mod= 1e9+ 7;
inline int read() {
int x= 0, f= 1;
char ch= getchar();
for (; ! isdigit(ch); ch= getchar()) if (ch== '-') f= -1;
for (; isdigit(ch); ch= getchar()) x= (x<< 3)+ (x<< 1)+ (ch^ 48);
return x*= f;
}
using namespace std;
int n, m, tot; ll ans;
int a[N], rt[N]; ll v[N];
int ls[N* 17* 17], rs[N* 17* 17];
ll val[N* 17* 17], sum[N* 17* 17];
vector< pair< int, ll> > q;
#define mid ((l+ r)>> 1)
void insert( int & k, int l, int r, int x, ll v, ll op) {
if (! k) k= ++tot; ; if (l== r) return val[k]= ((val[k]+ v* op%mod)%mod+ mod)% mod, sum[k]= ((sum[k]+ op)% mod+mod)%mod, void();
x<= mid? insert(ls[k], l, mid, x, v, op): insert(rs[k], mid+ 1, r, x, v, op);
val[k]= (val[ls[k]]+ val[rs[k]])% mod, sum[k]= (sum[ls[k]]+ sum[rs[k]])% mod;
}
void add( int u, int x, ll v, ll op) { for (; u<= n; u+= (u& -u)) insert(rt[u], 0, n+ 1, x, v, op); }
void query( int u, ll op) { for (; u; u-= (u& -u)) q.push_back({rt[u], op}); }
pair< ll, ll> ask( int l, int r, int x, int y, vector< pair< int, ll> > tmp) {
if (x<= l&& r<= y) {
pair< int, int> res= {0, 0};
for ( auto i: tmp) res.first= ((res.first+ sum[i.first]* i.second%mod)% mod+mod)%mod,
res.second= ((res.second+ val[i.first]* i.second%mod)%mod+mod)% mod;
return res;
}
pair< ll, ll> res= {0, 0};
if (x<= mid) {
vector< pair< int, ll> > now= tmp;
for ( auto & i: now) i.first= ls[i.first];
pair< ll, ll> t= ask(l, mid, x, y, now);
res.first= (res.first+ t.first)% mod, res.second= (res.second+ t.second+ mod)% mod;
}
if (y> mid) {
vector< pair< int, ll> > now= tmp;
for ( auto & i: now) i.first= rs[i.first];
pair< ll, ll> t= ask(mid+ 1, r, x, y, now);
res.first= (res.first+ t.first)% mod, res.second= (res.second+ t.second+ mod)% mod;
}
tmp.clear();
return res;
}
/*
5 5
1 1
2 2
3 3
4 4
5 5
1 5
1 5
2 4
5 3
1 3
*/
signed main() {
n= read(), m= read();
for ( int i= 1; i<= n; i++) a[i]= read(), v[i]= read();
for ( int i= 1; i<= n; i++) {
q.clear(), query(i, 1);
pair< ll, ll> res= ask(0, n+ 1, a[i], n+ 1, q);
ans= (ans+ res.first* v[i]% mod+ res.second% mod)% mod;
add(i, a[i], v[i], 1);
}
while (m--) {
int x= read(), y= read();
if (x> y) swap(x, y);
if (x== y) { printf("%lld\n", ans); continue ; }
if (x+ 1== y) {
int t= (v[x]+ v[y])% mod;
if (a[x]< a[y]) ans= (ans+ t)% mod;
else ans= (ans- t+ mod)% mod;
add(x, a[x], v[x], -1), add(y, a[y], v[y], -1);
add(x, a[y], v[y], 1), add(y, a[x], v[x], 1);
swap(a[x], a[y]), swap(v[x], v[y]);
} else {
int l= x+ 1, r= y- 1; q.clear();
query(r, 1), query(l- 1, -1);
pair< ll, ll> res1= ask(0, n+ 1, a[x]+ 1, n+ 1, q);
pair< ll, ll> res2= ask(0, n+ 1, 0, a[x]- 1, q);
int t= (res1.first* v[x]% mod+ res1.second% mod)% mod;
ans= (ans+ t)% mod;
t= (res2.first* v[x]% mod+ res2.second% mod)% mod;
ans= (ans- t)% mod;
res1= ask(0, n+ 1, a[y]+ 1, n+ 1, q);
res2= ask(0, n+ 1, 0, a[y]- 1, q);
t= (res1.first* v[y]% mod+ res1.second% mod)% mod;
ans= (ans- t)% mod;
t= (res2.first* v[y]% mod+ res2.second% mod)% mod;
ans= (ans+ t)% mod;
t= (v[x]+ v[y])% mod;
if (a[x]< a[y]) ans= (ans+ t)% mod;
else ans= (ans- t+ mod)% mod;
add(x, a[x], v[x], -1), add(y, a[y], v[y], -1);
add(x, a[y], v[y], 1), add(y, a[x], v[x], 1);
swap(a[x], a[y]), swap(v[x], v[y]);
}
ans=(ans%mod+mod)%mod;
printf("%lld\n", ans);
}
}
```
by 123456xwd @ 2024-03-28 22:11:33