题目描述
维护一个长度为n的序列，一开始都是0，支持以下两种操作：1.U k a 将序列中第k个数修改为a。2.Z c s 在这个序列上，每次选出c个正数，并将它们都减去1，询问能否进行s次操作。每次询问独立，即每次询问不会对序列进行修改。
输入输出格式
输入格式：
第一行包含两个正整数n,m(1<=n,m<=1000000)，分别表示序列长度和操作次数。接下来m行为m个操作，其中1<=k,c<=n，0<=a<=10^9，1<=s<=10^9。
输出格式：
包含若干行，对于每个Z询问，若可行，输出TAK，否则输出NIE。
输入输出样例
输入样例#1：
3 8U 1 5U 2 7Z 2 6U 3 1Z 2 6U 2 2Z 2 6Z 2 1
输出样例#1：
NIETAKNIETAK
说明
维护一个长度为n的序列，一开始都是0，支持以下两种操作：
1.U k a 将序列中第k个数修改为a。
2.Z c s 在这个序列上，每次选出c个正数，并将它们都减去1，询问能否进行s次操作。
每次询问独立，即每次询问不会对序列进行修改。
#include#include #include #include #define maxn 1000010using namespace std;int a[maxn],x[maxn],y[maxn],z[maxn],num[maxn],hash[maxn];int n,m,cnt;struct node{ long long c[maxn]; void add(int x,int y){ while(x<=cnt){ c[x]+=y; x+=x&-x; } } long long query(int x){ long long res=0; while(x){ res+=c[x]; x-=x&-x; } return res; }}bit1,bit2;int main(){ scanf("%d%d",&n,&m); char s[5]; for(int i=1;i<=m;i++){ scanf("%s",s); scanf("%d%d",&x[i],&y[i]);num[i]=y[i]; if(s[0]=='U')z[i]=1; else z[i]=0; } sort(num+1,num+m+1); hash[cnt=1]=num[1]; for(int i=2;i<=m;i++) if(num[i]!=num[i-1])hash[++cnt]=num[i]; for(int i=1;i<=m;i++)y[i]=lower_bound(hash+1,hash+cnt+1,y[i])-hash; for(int i=1;i<=m;i++){ if(z[i]){ if(a[x[i]]){ int j=a[x[i]]; bit1.add(j,-1);bit2.add(j,-hash[j]); } a[x[i]]=y[i]; bit1.add(y[i],1);bit2.add(y[i],hash[y[i]]); } else { long long num1=bit2.query(y[i]-1); long long num2=bit1.query(cnt); long long num3=bit1.query(y[i]-1); if(num1>=1LL*(x[i]-num2+num3)*hash[y[i]])puts("TAK"); else puts("NIE"); } } return 0;}