mxqz，40分WA

RT，fhq写的，死活过不了

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
int a[1000005];
struct fhq {
    int val[1000005], rd[1000005];
    int size[1000005], sum[1000005];
    int son[1000005][2];
    int f, x, y, z, s;
    void pushup(int k) {
        size[k] = size[son[k][0]] + size[son[k][1]] + 1;
        sum[k] = sum[son[k][0]] + sum[son[k][1]] + val[k];
    }
    int new_node(int v) {
        s++;
        val[s] = sum[s] = v; rd[s] = rand(); size[s] = 1;
        return s;
    }
    void split(int k, int v, int &x, int &y) {
        if (!k) {x = y = 0; return;}
        if (val[k] <= v) x = k, split(son[k][1], v, son[k][1], y);
        else y = k, split(son[k][0], v, x, son[k][0]);
        pushup(k);
    }
    int merge(int x, int y) {
        if (!x || !y) return x + y;
        if (rd[x] < rd[y]) {son[x][1] = merge(son[x][1], y); pushup(x); return x;}
        else {son[y][0] = merge(x, son[y][0]); pushup(y); return y;}
    }
    void insert(int v) {split(f, v, x, y); f = merge(merge(x, new_node(v)), y);}
    void del(int v) {
        split(f, v, x, z); split(x, v - 1, x, y);
        y = merge(son[y][0], son[y][1]); f = merge(merge(x, y), z);
    }
    int query(int s) {
        split(f, s, x, y);
        int ans = val[y] - s * size[y];
        // cout << ":::" << size[y] << ' ' << val[y] << endl;
        f = merge(x, y);
        return sum[f] - ans;
    }
} t;
inline int read() {
    int x = 0, f = 1; char c = getchar();
    while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
    while (isdigit(c)) {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
    return x * f;
}
signed main() {
    n = read(); m = read();
    for (int i = 1; i <= m; i++) {
        char p; int x, y; cin >> p; x = read(); y = read();
        if (p == 'U') {t.del(a[x]); t.insert(y); a[x] = y;}
        else {
            int k = t.query(y);
            if (k >= x * y) printf("TAK\n");
            else printf("NIE\n");
        }
    }
    return 0;
}