题目大意：维护一个集合，支持单点修改、查询小于 X 的数的个数、查询小于 X 的数的和。
题解：学习到了动态开点线段树。对于一棵未经离散化的权值线段树来说，对于静态开点来说，过大的值域会导致不能承受的空间。还可以发现，对于每次修改操作只会涉及一条树链，即：\(O(logn)\) 个节点，因此总共所需的空间为 \(O(mlogn)\)。基于以上想法，采用动态开点的操作，即：该节点被修改，则动态地创建这个节点。反之，没有被用到的节点直接忽略掉即可。
代码如下
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e7+10;
const int mx=1e9+1;
inline int read(){
int x=0,f=1;char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));
do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));
return f*x;
}
int n,m,a[maxn];
struct node{
#define ls(x) t[x].lc
#define rs(x) t[x].rc
int lc,rc,size;
long long sum;
}t[maxn<<1];
int tot,root;
inline void pushup(int o){
t[o].size=t[ls(o)].size+t[rs(o)].size;
t[o].sum=t[ls(o)].sum+t[rs(o)].sum;
}
void modify(int &o,int l,int r,int pos,int val){
if(!o)o=++tot;
if(l==r){t[o].size+=val,t[o].sum+=l*val;return;}
int mid=l+r>>1;
if(pos<=mid)modify(ls(o),l,mid,pos,val);
else modify(rs(o),mid+1,r,pos,val);
pushup(o);
}
long long querys(int o,int l,int r,int x,int y){
if(!o)return 0;
if(l==x&&r==y)return t[o].sum;
int mid=l+r>>1;
if(y<=mid)return querys(ls(o),l,mid,x,y);
else if(x>mid)return querys(rs(o),mid+1,r,x,y);
else return querys(ls(o),l,mid,x,mid)+querys(rs(o),mid+1,r,mid+1,y);
}
int querysz(int o,int l,int r,int x,int y){
if(!o)return 0;
if(l==x&&r==y)return t[o].size;
int mid=l+r>>1;
if(y<=mid)return querysz(ls(o),l,mid,x,y);
else if(x>mid)return querysz(rs(o),mid+1,r,x,y);
else return querysz(ls(o),l,mid,x,mid)+querysz(rs(o),mid+1,r,mid+1,y);
}
void solve(){
n=read(),m=read();
char opt[2];
while(m--){
scanf("%s",opt);
if(opt[0]=='U'){
int pos=read(),val=read();
modify(root,0,mx,a[pos],-1);
modify(root,0,mx,a[pos]=val,1);
}else{
int c=read(),s=read();
int k=querysz(root,0,mx,s,mx);
long long sum=querys(root,0,mx,0,s-1);
puts(sum>=(long long)s*(c-k)?"TAK":"NIE");
}
}
}
int main(){
solve();
return 0;
}