fhq80pts,wa on#5#8求条

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int maxn=5000010;
const int mo=1000000007;
const int inf=0x7f7f7f7f7f7f7f7f;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

int n,m,a[maxn];
mt19937 myr(time(0));
int rt,tot;
int ls[maxn],rs[maxn],sum[maxn],siz[maxn],rnd[maxn],v[maxn],vsiz[maxn];

void up(int p){
    sum[p]=sum[ls[p]]+sum[rs[p]]+v[p]*vsiz[p];
    siz[p]=siz[ls[p]]+siz[rs[p]]+vsiz[p];
    return ;
}

int newn(int x){
    v[++tot]=x;
    sum[tot]=x;
    vsiz[tot]=1;
    siz[tot]=1;
    rnd[tot]=myr();
    ls[x]=rs[x]=0;
    return tot;
}

void split(int p,int vv,int &x,int &y){
    if(!p){
        x=y=0;
        return ;
    }
    if(vv>=v[p]){
        x=p;
        split(rs[p],vv,rs[p],y);
    }
    else{
        y=p;
        split(ls[p],vv,x,ls[p]);
    }
    up(p);
    return ;
}

int merge(int x,int y){
    if(!x||!y)
        return x|y;
    if(rnd[x]>rnd[y]){
        rs[x]=merge(rs[x],y);
        up(x);
        return x;
    }
    ls[y]=merge(x,ls[y]);
    up(y);
    return y;
}

void del(int vv){
    int x=0,y=0,z=0;
    split(rt,vv,x,z);
    split(x,vv-1,x,y);
    if(siz[y]==1)
        rt=merge(x,z);
    else{
        vsiz[y]--;
        siz[y]--;
        sum[y]-=vv;
        rt=merge(merge(x,y),z);
    }
    return ;
}

void insert(int vv){
    int x=0,y=0,z=0;
    split(rt,vv,x,z);
    split(x,vv-1,x,y);  
    if(!y)
        rt=merge(merge(x,newn(vv)),z);
    else{
        vsiz[y]++;
        siz[y]++;
        sum[y]+=vv;
        rt=merge(merge(x,y),z);
    }
    return ;
}

int getsum(int v){
    int x=0,y=0;
    split(rt,v-1,x,y);  
    int ret=sum[x];
    rt=merge(x,y);
    return ret;
}

int getsiz(int v){
    int x=0,y=0;
    split(rt,v-1,x,y);
    int ret=siz[y];
    rt=merge(x,y);
    return ret;
}

signed main(){
    n=read();
    m=read();
    while(m--){
        string op;
        cin>>op;
        int c=read(),s=read();
        if(op[0]=='U'){
            if(a[c]!=0)
                del(a[c]);
            if(s!=0)
                insert(s);
            a[c]=s;
        }
        else{
        //  cout<<getsiz(s)<<" "<<getsum(s)<<endl;
            int ccc=c-getsiz(s);
            if(getsum(s)>=ccc*s)
                printf("TAK\n");
            else
                printf("NIE\n");                
        }
    }
    return 0;
}