https://www.luogu.com.cn/record/112548164

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1000100;
int n,m;
ll a[N],qc[N],bmic[N],bmis[N],sum,w,qs,c,k;
struct node
{
	char ch;
	ll q1,q2;
}q[N];
int lowbit(int x)
{
	return x&(-x);
}
void add_mic(int p,int x)
{
	for(int i=p;i<=n;i+=lowbit(i)) bmic[i]+=x;
}
void add_mis(int p,int x)
{
	for(int i=p;i<=n;i+=lowbit(i)) bmis[i]+=x;
}
/*void add_s(int p,int x)
{
	for(int i=p;i<=n;i+=lowbit(i)) bs[i]+=x;
}*/
ll sum_mic(int p)
{
	ll s=0;
	for(int i=p;i;i-=lowbit(i)) s+=bmic[i];
	return s;
}
ll sum_mis(int p)
{
	ll s=0;
	for(int i=p;i;i-=lowbit(i)) s+=bmis[i];
	return s;
}
/*int sum_s(int p)
{
	int s=0;
	for(int i=p;i;i-=lowbit(i)) s+=bs[i];
	return s;
}*/
int two_find(int x)
{
	int l=0,r=k+1,mid;
	while(l+1<r)
	{
		mid=(l+r)/2;
		if(qc[mid]==x) return mid;
		if(qc[mid]>x) r=mid;
		else l=mid;
	}
	return l;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) 
	{
		cin>>q[i].ch;
		scanf("%lld%lld",&q[i].q1,&q[i].q2);
		if(q[i].ch=='Z') qc[++k]=q[i].q2;
	}
	sort(qc+1,qc+k+1);
	k=unique(qc+1,qc+k+1)-qc;
	for(int i=1;i<=m;i++)
	{
		if(q[i].ch=='U') 
		{
			w=two_find(a[q[i].q1]);
			if(qc[w+1]<=a[q[i].q1]) w++;
			add_mic(1,-1);
			add_mic(w+1,1);
			add_mis(1,-a[q[i].q1]);
			add_mis(w+1,a[q[i].q1]);
			//add_s(q[i].q1,-a[q[i].q1]);
			sum-=a[q[i].q1];
			a[q[i].q1]=q[i].q2;
			w=two_find(q[i].q2);
			if(qc[w+1]<=q[i].q2) w++;
			add_mic(1,1);
			add_mic(w+1,-1);
			add_mis(1,a[q[i].q1]);
			add_mis(w+1,-a[q[i].q1]);
			//add_s(q[i].q1,q[i].q2);
			sum+=q[i].q2;
		}
		else
		{
			w=two_find(q[i].q2);
			qs=sum-sum_mis(w);
			c=sum_mic(w)+qs/q[i].q2;
			c>=q[i].q1?puts("TAK"):puts("NIE");
			//printf("w=%lld qs=%lld c=%lld\n",w,qs,c);
		}
	}
	return 0;
}