题目描述
加里敦大学有个帝国图书馆，小豆是图书馆阅览室的一个书籍管理员。他的任务是把书排成有序的，所以无序的书让他产生厌烦，两本乱序的书会让小豆产生 这两本书页数的和的厌烦度。现在有n本被打乱顺序的书，在接下来m天中每天都会因为读者的阅览导致书籍顺序改变位置。因为小豆被要求在接下来的m天中至少 要整理一次图书。小豆想知道，如果他前i天不去整理，第i天他的厌烦度是多少，这样他好选择厌烦度最小的那天去整理。
输入输出格式
输入格式：
第一行会有两个数，n，m分别表示有n本书，m天
接下来n行，每行两个数，ai和vi，分别表示第i本书本来应该放在ai的位置，这本书有vi页，保证不会有放置同一个位置的书
接下来m行，每行两个数，xj和yj，表示在第j天的第xj本书会和第yj本书会因为读者阅读交换位置
输出格式：
一共m行，每行一个数，第i行表示前i天不去整理，第i天小豆的厌烦度，因为这个数可能很大，所以将结果模10^9 +7后输出
输入输出样例
说明
对于20%的数据，1 ≤ ai; xj; yj ≤ n ≤ 5000, m ≤ 5000, vi ≤ 10^5
对于100%的数据，1 ≤ ai; xj; yj ≤ n ≤ 50000, m ≤ 50000, vi ≤ 10^5
不想写或者不会写数据结构的用分块就好，然后有两种写法，一种是对每一块排序，一种是对每块维护一个树状数组。
这样分L和R在同一块，L和R所在的两个不完整的块，L和R跨过的完整的块三种情况讨论即可。
注意！！这题前两种情况一定不能暴力重建块！暴力重建的用时是1200+s，如果只更新变化的部分就只要80+s。
还有一个问题，因为整块标记的复杂度是$O(\frac{n}{S} \log n)$的（其中S是块的大小），所以S设为$\sqrt{n \log n}$的速度是设为$\sqrt{n}$的两倍。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long ll;
#define rep(i,l,r) for (register int i=l; i<=r; i++)
using namespace std; const ll N=,md=;
int n,m,mx,L,R,B,a[N],v[N],sz[N],bl[N],cnt,sum[N],d[],c[][N],c1[][N],ans; void add(int c[],int x,int k){ for (; x<=n; x+=x&-x) c[x]=(c[x]+k)%md; }
int que(int c[],int x){ ll res=; for (; x; x-=x&-x) res=(res+c[x])%md; return res; }
void add1(int c1[],int x,int k){ for (; x<=n; x+=x&-x) c1[x]=(c1[x]+k)%md; }
int que1(int c1[],int x){ ll res=; for (; x; x-=x&-x) res=(res+c1[x])%md; return res; }
int get(int x){ return x>= ? x : x+md; } void cal(int x,int y,int z){
if (a[x]<a[z]) ans=(ans+v[x]+v[z])%md; else ans=(ans-v[x]-v[z]+md+md)%md;
if (a[y]<a[z]) ans=(ans+md+md-v[y]-v[z])%md; else ans=(ans+v[y]+v[z])%md;
} void work(int L,int R){
if (L==R) return;
if (bl[L]==bl[R]){
rep(i,L+,R-) cal(L,R,i); swap(a[L],a[R]); swap(v[L],v[R]);
}else{
rep(i,L+,(bl[L]-)*B+sz[bl[L]]) cal(L,R,i);
rep(i,(bl[R]-)*B+,R-) cal(L,R,i);
swap(a[L],a[R]); swap(v[L],v[R]);
sum[bl[L]]=(sum[bl[L]]+md-v[R]+v[L])%md; sum[bl[R]]=(sum[bl[R]]+md-v[L]+v[R])%md;
add(c[bl[R]],a[L],-v[L]); add(c[bl[L]],a[R],-v[R]); add1(c1[bl[R]],a[L],-); add1(c1[bl[L]],a[R],-);
add(c[bl[L]],a[L],v[L]); add(c[bl[R]],a[R],v[R]); add1(c1[bl[L]],a[L],); add1(c1[bl[R]],a[R],);
rep(i,bl[L]+,bl[R]-){
ans=get((1ll*ans-(que(c[i],a[R]-)+1ll*que1(c1[i],a[R]-)*v[R])%md));
ans=get((1ll*ans+(que(c[i],a[L]-)+1ll*que1(c1[i],a[L]-)*v[L]))%md);
ans=get((1ll*ans-(sum[i]-que(c[i],a[L])+1ll*(sz[i]-que1(c1[i],a[L]))*v[L]))%md);
ans=get((1ll*ans+(sum[i]-que(c[i],a[R])+1ll*(sz[i]-que1(c1[i],a[R]))*v[R]))%md);
}
}
if (a[R]<a[L]) ans=(1ll*ans+v[L]+v[R])%md; else ans=get((1ll*ans-(v[L]+v[R]))%md);
} int main(){
freopen("book.in","r",stdin);
freopen("book.out","w",stdout);
scanf("%d%d",&n,&m); B=(int)sqrt(n*);
rep(i,,n) scanf("%d%d",&a[i],&v[i]);
rep(i,,n) bl[i]=(i-)/B+; mx=(n-)/B+;
rep(i,,mx-) sz[i]=B; sz[mx]=n-(mx-)*B;
rep(i,,n) add(c[bl[i]],a[i],v[i]),add1(c1[bl[i]],a[i],),sum[bl[i]]=(sum[bl[i]]+v[i])%md;
rep(i,,n){
ans=get((1ll*ans+(i--1ll*que1(c1[],a[i]-))*v[i]+cnt-que(c[],a[i]-))%md);
add(c[],a[i],v[i]); add1(c1[],a[i],); cnt=(cnt+v[i])%md;
}
rep(i,,m) scanf("%d%d",&L,&R),work(min(L,R),max(L,R)),printf("%d\n",ans);
return ;
}