题意

维护一个长度为$n$的序列，一开始都是$0$，支持以下两种操作：

• $U \ k \ a$ 将序列中第$k$个数修改为$a$
• $Z \ c \ s$ 在这个序列上，每次选出$c$个正数，并将它们都减去$1$，询问能否进行$s$次操作

每次询问独立，即每次询问不会对序列进行修改

数据范围：$1 \le n,m \le 1000000$

题解

对于一个询问，记$\ge s$的数有$x$个，$< s$的数的和为$sum$，若$$xs+sum \ge cs$$则可以满足，否则不能满足

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=1000000+10;
int n,m;
char op[N];
int tot;
int a[N],b[N],d[N],p[N],s[N];
LL sum[N];
inline int lowbit(int x){
    return x&-x;
}
template <typename T>
inline void update(T *t,int p,int k){
    for(;p<=tot;p+=lowbit(p))
        t[p]+=k;
}
template <typename T>
inline T query(T *t,int p){
    T res=0;
    for(;p;p-=lowbit(p))
        res+=t[p];
    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    d[++tot]=0;
    for(int i=1;i<=m;i++){
        scanf("%s%d%d",op+i,&a[i],&b[i]);
        d[++tot]=b[i];
    }
    sort(d+1,d+tot+1);
    tot=unique(d+1,d+tot+1)-d-1;
    for(int i=1;i<=m;i++)
        b[i]=lower_bound(d+1,d+tot+1,b[i])-d;
    for(int i=1;i<=m;i++)
        if(op[i]=='U'){
            if(p[a[i]]){
                update(s,p[a[i]],-1);
                update(sum,p[a[i]],-d[p[a[i]]]);
            }
            p[a[i]]=b[i];
            update(s,p[a[i]],1);
            update(sum,p[a[i]],d[p[a[i]]]);
        }
        else{
            int x=query(s,tot)-query(s,b[i]-1);
            LL t=query(sum,b[i]-1);
            if(t>=1ll*(a[i]-x)*d[b[i]])
                puts("TAK");
            else puts("NIE");
        }
    return 0;
}