C++11(clang++ 3.9) 解法, 执行用时: 1641ms, 内存消耗: 45416K, 提交时间: 2019-03-09 18:28:11

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn=50010;
const ll mod=1000000007;
ll ans;
int n,m,B;
ll s[2][250][maxn],v[maxn];
int p[maxn];
int rd()
{
    int ret=0;  char gc=getchar();
    while(gc<'0'||gc>'9') gc=getchar();
    while(gc>='0'&&gc<='9')   ret=ret*10+gc-'0',gc=getchar();
    return ret;
}
void updata(int z,int y,int x,ll val)
{
    if(!x)  return ;
    for(int i=x;i<=n;i+=i&-i)    s[z][y][i]=(s[z][y][i]+val+mod)%mod;
}
ll query(int z,int y,int x)
{
    if(x<0)  return 0;
    ll ret=0;
    for(int i=x;i;i-=i&-i)  ret=(ret+s[z][y][i])%mod;
    return ret;
}
void calc(int a,int b,int c)
{
    if(p[a]<p[c])    ans=(ans+v[a]+v[c])%mod;
    else    ans=(ans-v[a]-v[c]+mod+mod)%mod;
    if(p[b]<p[c])    ans=(ans-v[b]-v[c]+mod+mod)%mod;
    else    ans=(ans+v[b]+v[c])%mod;
}
int main()
{
    int i,j,a,b,c,d;
    n=rd(),m=rd(),B=int(sqrt(n*17));
    for(i=0;i<n;i++) p[i]=rd(),v[i]=rd(),updata(0,i/B,p[i],v[i]),updata(1,i/B,p[i],1);
    for(i=n-1;i>=0;i--)
    {
        ans=(ans+query(0,n/B+1,p[i])+query(1,n/B+1,p[i])*v[i])%mod;
        updata(0,n/B+1,p[i],v[i]),updata(1,n/B+1,p[i],1);
    }
    for(i=1;i<=m;i++)
    {
        a=rd()-1,b=rd()-1;
        if(a==b)
        {
            printf("%lld\n",ans);
            continue;
        }
        if(a>b)  swap(a,b);
        c=a/B,d=b/B;
        if(p[a]<p[b])    ans=(ans+v[a]+v[b])%mod;
        else    ans=(ans-v[a]-v[b]+mod+mod)%mod;
        if(c==d)
        {
            for(j=a+1;j<b;j++)   calc(a,b,j);
            swap(p[a],p[b]),swap(v[a],v[b]);
            printf("%lld\n",ans);
            continue;
        }
        for(j=a+1;j<c*B+B;j++)   calc(a,b,j);
        for(j=d*B;j<b;j++)   calc(a,b,j);
        for(j=c+1;j<d;j++)
        {
            ans=(ans-2*query(0,j,p[a])+query(0,j,n)-(2*query(1,j,p[a])-B+mod)*v[a]%mod+mod)%mod;
            ans=(ans+2*query(0,j,p[b])-query(0,j,n)+(2*query(1,j,p[b])-B+mod)*v[b]%mod+mod)%mod;
        }
        updata(0,c,p[a],-v[a]),updata(0,d,p[b],-v[b]),updata(1,c,p[a],-1),updata(1,d,p[b],-1);
        swap(p[a],p[b]),swap(v[a],v[b]);
        updata(0,c,p[a],v[a]),updata(0,d,p[b],v[b]),updata(1,c,p[a],1),updata(1,d,p[b],1);
        printf("%lld\n",ans);
    }
    return 0;
}