LibreOJ 2639 「TJOI2017」不勤劳的图书管理员

非常套路 & 码农的一道树套树题……
正解被分块吊起来打……

树状数组套平衡树，平衡树维护个数和权值和。
然后就是套路。

十分艰难地提交了并且心态崩了。
成功超时。

此代码无法在 LibreOJ 上通过。

代码：

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define ls(p) p->lson
#define rs(p) p->rson
#define lowbit(x) ((x) & -(x))
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    while(ch < '0' || ch > '9')
        w |= ch == '-',ch = gc();
    while(ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc();
    w ? x = -x : x;
}

const int N = 5e4;
const long long mod = 1e9 + 7;
int n,m,a[N + 10];
long long v[N + 10],ans;
struct node
{
    int key,rnd,sz;
    long long val,sum;
    node *lson,*rson;
} *rt[N + 10];
inline node *new_node(int k,long long v)
{
    node *ret = new node();
    ret->key = k;
    ret->val = ret->sum = v;
    ret->rnd = rand();
    ret->sz = 1;
    return ret;
}
inline void up(node *p)
{
    p->sz = 1,p->sum = p->val;
    if(ls(p))
        p->sz += ls(p)->sz,p->sum = (p->sum + ls(p)->sum) % mod;
    if(rs(p))
        p->sz += rs(p)->sz,p->sum = (p->sum + rs(p)->sum) % mod;
}
node *merge(node *x,node *y)
{
    if(!x)
        return y;
    if(!y)
        return x;
    if(x->rnd < y->rnd)
    {
        rs(x) = merge(rs(x),y);
        up(x);
        return x;
    }
    else
    {
        ls(y) = merge(x,ls(y));
        up(y);
        return y;
    }
}
void split(node *p,int k,node *&x,node *&y)
{
    if(!p)
    {
        x = y = NULL;
        return ;
    }
    if(!k)
    {
        x = NULL,y = p;
        return ;
    }
    if(k == n)
    {
        x = p,y = NULL;
        return ;
    }
    if(p->key <= k)
        x = p,split(rs(p),k,rs(p),y);
    else
        y = p,split(ls(p),k,x,ls(p));
    up(p);
}
void update(int x,int key,long long v,int k)
{
    node *a,*b,*c;
    for(;x <= n;x += lowbit(x))
        if(k)
        {
            split(rt[x],key,a,b);
            rt[x] = merge(merge(a,new_node(key,v)),b);
        }
        else
        {
            split(rt[x],key,a,c);
            split(a,key - 1,a,b);
            if(b)
                delete b;
            rt[x] = merge(a,c);
        }
}
long long query(int x,int keyl,int keyr)
{
    long long ret = 0;
    node *a,*b,*c;
    for(;x;x -= lowbit(x))
    {
        split(rt[x],keyr,a,c);
        split(a,keyl - 1,a,b);
        if(b)
            ret = (ret + b->sum) % mod;
        rt[x] = merge(merge(a,b),c);
    }
    return ret;
}
int ask(int x,int keyl,int keyr)
{
    int ret = 0;
    node *a,*b,*c;
    for(;x;x -= lowbit(x))
    {
        split(rt[x],keyr,a,c);
        split(a,keyl - 1,a,b);
        if(b)
            ret += b->sz;
        rt[x] = merge(merge(a,b),c);
    }
    return ret;
}
int main()
{
    read(n),read(m);
    int x;
    long long val;
    for(register int i = 1;i <= n;++i)
    {
        read(x);
        read(val);
        a[i] = x,v[i] = val;
        update(i,x,val,1);
    }
    for(register int i = 1;i <= n;++i)
        ans = (ans + v[i] * (ask(n,1,a[i] - 1) - ask(i,1,a[i] - 1)) + (query(n,1,a[i] - 1) - query(i,1,a[i] - 1))) % mod;
    int y;
    while(m--)
    {
        read(x),read(y);
        if(x == y)
        {
            printf("%lld\n",ans);
            continue;
        }
        if(x > y)
            swap(x,y);
        ans = (ans - v[x] * (ask(y,1,a[x] - 1) - ask(x,1,a[x] - 1)) - (query(y,1,a[x] - 1) - query(x,1,a[x] - 1))) % mod;
        ans = (ans - v[y] * (ask(y - 1,a[y] + 1,n) - ask(x - 1,a[y] + 1,n)) - (query(y - 1,a[y] + 1,n) - query(x - 1,a[y] + 1,n))) % mod;
        if(a[x] > a[y])
            ans = (ans + v[x] + v[y]) % mod;
        update(x,a[x],v[x],0),update(y,a[y],v[y],0);
        swap(a[x],a[y]),swap(v[x],v[y]);
        update(x,a[x],v[x],1),update(y,a[y],v[y],1);
        ans = (ans + v[x] * (ask(y,1,a[x] - 1) - ask(x,1,a[x] - 1)) + (query(y,1,a[x] - 1) - query(x,1,a[x] - 1))) % mod;
        ans = (ans + v[y] * (ask(y - 1,a[y] + 1,n) - ask(x - 1,a[y] + 1,n)) + (query(y - 1,a[y] + 1,n) - query(x - 1,a[y] + 1,n))) % mod;
        if(a[x] > a[y])
            ans = (ans - v[x] - v[y]) % mod;
        ans = (ans + mod) % mod;
        printf("%lld\n",ans);
    }
}