fhq MLE 90求助

#include<bits/stdc++.h>
#define ls tr[u].l
#define rs tr[u].r
using namespace std;
typedef long long LL;
const int N=1e6+10;
int a[N];
struct node
{
    int l,r;
    int key,val;
    int sz;
    LL sum;
}tr[N];
int root,idx;
int n,m;

int get_node(int x)
{
    int u=++idx;
    tr[u]={0,0,x,rand(),1,(LL)x};
    return u;
}

void pushup(int u)
{
    tr[u].sz=(tr[ls].sz+tr[rs].sz+1);
    tr[u].sum=(tr[ls].sum+tr[rs].sum+(LL)tr[u].key);
}

void split(int u,int x,int &a,int &b)
{
    if(!u) a=b=0;
    else
    {
        if(tr[u].key<=x) a=u,split(tr[a].r,x,tr[a].r,b),pushup(a);
        else b=u,split(tr[b].l,x,a,tr[b].l),pushup(b);
    }
}

int merge(int a,int b)
{
    if(!a||!b) return a+b;
    if(tr[a].val<tr[b].val) 
    {
        tr[a].r=merge(tr[a].r,b),pushup(a);
        return a;
    }
    else 
    {
        tr[b].l=merge(a,tr[b].l),pushup(b);
        return b;
    }
}

void insert(int x)
{
    int a,b;
    split(root,x,a,b);
    root=merge(merge(a,get_node(x)),b);
}

void remove(int x)
{
    int a,b,c,d;
    split(root,x-1,a,b);
    split(b,x,c,d);
    c=merge(tr[c].l,tr[c].r);
    root=merge(a,merge(c,d));
}

bool check(int C,int S)
{
    int a,b;
    split(root,S-1,a,b);
    LL sum=tr[a].sum;
    int cnt=tr[b].sz;
    root=merge(a,b);
    return sum>=((LL)(C-cnt)*S);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) insert(0);

    while(m--)
    {
        char c;
        cin>>c;
        if(c=='U')
        {
            int x,y;
            scanf("%d%d",&x,&y);
            remove(a[x]);
            insert(a[x]=y);
        }
        else
        {
            int cnt,s;
            scanf("%d%d",&cnt,&s);
            if(check(cnt,s)) puts("TAK");
            else puts("NIE");
        }
    }

    return 0;
}