Description：

一个长度序列一开始都是 $0$ ，支持两种操作： $1$ 、 $U\ k\ a$ 将序列中第 $k$ 个数修改为 $a$ 。 $2$ 、 $Z\ c\ s$ 在这个序列上，每次选出 $c$ 个正数，并将它们都减去 $1$ ，询问能否进行 $s$ 次操作。

$1\leqslant n\leqslant 10^6$

Solution：

首先要知道什么样的集合满足条件，然后再说用什么来维护他。

发现小于等于 $d$ 的是可以用完的，大于等于 $s$ 的只能用 $s$ 个，所以序列中大于等于的数的个数 $\times s+$ 小于 $s$ 的数的和如果大于 $c\times s$ 的话就行，发现这个可以离散化后用两棵树状数组分别维护每个权值的个数和每个权值的和来做。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define R register

inline int read()

{

	R int res = 0,f = 1;

	R char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

inline int getc()

{

	R char c = getchar();

	while(c != 'U' && c != 'Z')c = getchar();

	return (c == 'U' ? 0 : 1);

}

int n,m;

#define MAXN 1000010

struct opt

{

	int type,x,y;

}q[MAXN];

int b[MAXN],tot = 0;

int cnt = 0;

typedef long long ll;

struct BIT

{

	inline int lowbit(int x){return x & (-x);}

	int n;

	inline void init(int k){n = k;}

	ll c[MAXN];

	inline void add(int p,int k){for(R int i = p;i <= n;i += lowbit(i))c[i] += k;return;}

	inline ll query(int p){R ll res = 0;for(R int i = p;i >= 1;i -= lowbit(i))res += c[i];return res;}

}s,g;

int a[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	for(R int i = 1;i <= m;++i)

	{

		q[i].type = getc();

		q[i].x = read();q[i].y = read();

		if(q[i].type == 0)b[++tot] = q[i].y;

	}

	b[++tot] = 0;b[++tot] = 0x3f3f3f3f;

	sort(b + 1,b + 1 + tot);

	cnt = unique(b + 1,b + 1 + tot) - b - 1;

	s.init(cnt);g.init(cnt);

	for(R int i = 1;i <= n;++i)g.add(1,1);

	for(R int i = 1;i <= m;++i)

	{

		if(q[i].type == 0)

		{

			R int pos = lower_bound(b + 1,b + 1 + cnt,a[q[i].x]) - b;

			s.add(pos,-a[q[i].x]);

			g.add(pos,-1);

			a[q[i].x] = q[i].y;

			pos = lower_bound(b + 1,b + 1 + cnt,a[q[i].x]) - b;

			s.add(pos,a[q[i].x]);

			g.add(pos,1);

		}

		else

		{

			R int pos = upper_bound(b + 1,b + 1 + cnt,q[i].y) - b - 1;

			R ll sum = (g.query(cnt) - g.query(pos)) * q[i].y + s.query(pos);

			if(sum >= (ll)q[i].x * q[i].y)puts("TAK");

			else puts("NIE");

		}

	}

	return 0;

}