警示后人

不要用普通线段树写！（WA #8

再怎么卡常都是过不了的

Cao

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

const int N=1e6+5;
int n,m,Max[N<<2],Min[N<<2],num[N<<2],c,x;
long long sum[N<<2],ans;
char opt;

char buf[N+5],*p1,*p2;
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2)?EOF:*p1++)

inline int read()
{
	int r=0;
	char c=gc;
	while(!isdigit(c)) c=gc;
	while(isdigit(c))
	{ 
		r=(r<<1)+(r<<3)+c-48;
		c=gc;
	}
	return r;
}


inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}

inline void pushup(int x)
{
	Max[x]=max(Max[ls(x)],Max[rs(x)]);
	Min[x]=min(Min[ls(x)],Min[rs(x)]);
	sum[x]=sum[ls(x)]+sum[rs(x)];
	num[x]=num[ls(x)]+num[rs(x)];
}
inline void update(int p,int l,int r,int L,int k)
{
	if(l==r)
	{
		sum[p]=Max[p]=Min[p]=k;
		num[p]=(k>0);
		return ;
	}
	int mid=(l+r)>>1;
	if(L<=mid) update(ls(p),l,mid,L,k);
	else 	   update(rs(p),mid+1,r,L,k);
	pushup(p);
}
inline long long querysum(int p,int l,int r,int s)
{
	if(Max[p]<s) return sum[p];
	if(Min[p]>=s)
	{
		c-=(r-l+1);
		return 0;
	}
	int mid=(l+r)>>1;
	return querysum(ls(p),l,mid,s)+querysum(rs(p),mid+1,r,s);
}

// inline int querycnt(int p,int l,int r,int s)
// {
// 	// if(l==r) puts("qwq");
// 	// printf("[%lld %lld] %lld\n",l,r,Max[p]);
// 	if(Min[p]>=s) return r-l+1;
// 	if(Max[p]<s) return 0;
// 	int mid=(l+r)>>1;
// 	return querycnt(ls(p),l,mid,s)+querycnt(rs(p),mid+1,r,s);
// }

signed main()
{
	// printf("%lld\n",read());
	n=read(); m=read();
	// build(1,1,n);
	// puts("qwq");
	while(m--)
	{
		while(!isalpha(opt=gc));
		c=read(); x=read();
		if(opt=='U') update(1,1,n,c,x);
		else
		{
			if(num[1]<c)
			{
				printf("%s\n","NIE");
				continue;
			}
			// printf("%lld\n",c);
			ans=querysum(1,1,n,x);
			printf("%s\n",(c*x<=ans?"TAK":"NIE"));
		}
	}

}