维护一个长度为 \(n\) 的序列，一开始都是 \(0\)，支持以下两种操作：
\(U\) \(k\) \(a\) 将序列中第 \(k\) 个数修改为 \(a\)。
\(Z\) \(c\) \(s\) 在这个序列上，每次选出 \(c\) 个正数，并将它们都减去 \(1\)，询问能否进行 \(s\) 次操作。
每次询问独立，即每次询问不会对序列进行修改。
第一行包含两个正整数 \(n\),\(m\)，分别表示序列长度和操作次数。
接下来 \(m\) 行为 \(m\) 个操作。
包含若干行，对于每个 \(Z\) 询问，若可行，输出 \(TAK\)，否则输出 \(NIE\)。
输入 #1
3 8
U 1 5
U 2 7
Z 2 6
U 3 1
Z 2 6
U 2 2
Z 2 6
Z 2 1
输出 #1
NIE
TAK
NIE
TAK
对于 100% 的数据，1≤n,m≤10^6，1≤k,c≤n，0≤a≤10^9，1≤s≤10^9。
这题我天真的写了个后缀树状数组（一个连我都不知道自己当初怎么想出来的）
然后就有了差不多一页的提交记录。
直到今天下午 WZ 大佬给我看了他的代码，才注意到那种方法是可行的,是我写的有问题。
果然，还是我太菜了，被 WZ 大佬吊着打。
一句话题意 给你几种操作，操作一 区间修改，操作二 区间选 \(c\) 个数，看能否减 \(s\) 回。
操作1 还是很好实现的。关键是如何实现操作二。
我们分情况讨论一下。
大于等于 \(s\) 的数，那他对答案的贡献就是 \(s\) 因为我们最多每一轮都选他，这样他最多就会被减 \(s\) 次。
小于等于 \(s\) 的数，假设大于等于 \(s\) 的数 为 \(k\) 那我们剩下的数就要减去 \((c-k) \times s\)
也就是说 小于 \(s\) 的数的和 要大于等于 \((c-k) \times s\)
那么树状数组就完全可以胜任这种操作。
我们开两个树状数组 简称 权值树状数组 也就是桶。
一个维护大于等于 \(x\) 的个数，一个维护 小于等于 \(x\) 的权值和。
一开始我想的是把第一个树状数组写成后缀树状数组的形式。
可后来发现维护一个前缀和，求一个差值就是答案。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
const int N = 1e6;
int n,m,tot,b[1000010],tong[1000010],a[1000010];//tong 数组维护小于等于 x 的数的个数
long long tr[1000010];//tr 数组维护小于等于 x 的权值和
struct node
{
int x,y,opt;
}q[1000010];
inline int read()
{
int s = 0,w = 1;char ch = getchar();
while(ch < ‘0‘ || ch > ‘9‘){if(ch == ‘-‘) w = -1; ch = getchar();}
while(ch >= ‘0‘ && ch <= ‘9‘){s =s * 10+ch - ‘0‘; ch = getchar();}
return s * w;
}
int lowbit(int x){return x & -x;}
void chenge(int x,int val)//修改第一个树状数组
{
for(; x <= N; x += lowbit(x)) tong[x] += val;
}
void modify(int x,int val)//修建第二个树状数组
{
for(; x <= N; x += lowbit(x)) tr[x] += val;
}
int query_num(int x)
{
int res = 0;
for(; x; x -= lowbit(x)) res += tong[x];
return res;
}
long long query_sum(int x)
{
long long res = 0;
for(; x; x -= lowbit(x)) res += tr[x];
return res;
}
signed main()
{
n = read(); m = read();
for(int i = 1; i <= m; i++)//把询问离线下来
{
char ch; cin>> ch;
if(ch == ‘U‘)
{
q[i].opt = 1;
q[i].x = read();
q[i].y = read();
b[++tot] = q[i].y;
}
else if(ch == ‘Z‘)
{
q[i].opt = 2;
q[i].x = read();
q[i].y = read();
b[++tot] = q[i].y;
}
}
sort(b+1,b+tot+1); //离散化操作
int t = unique(b+1,b+tot+1)-b-1;
for(int i = 1; i <= m; i++)
{
if(q[i].opt == 1)
{
if(a[q[i].x])
{
int num = lower_bound(b+1,b+t+1,a[q[i].x])-b;
chenge(num,-1); modify(num,-a[q[i].x]);//把原来得数的贡献减掉
}
int id = lower_bound(b+1,b+t+1,q[i].y)-b;
chenge(id,1);//加上现在的贡献
modify(id,q[i].y);
a[q[i].x] = q[i].y;//记录一下当前位置上的数
}
else if(q[i].opt == 2)
{
int id = lower_bound(b+1,b+t+1,q[i].y)-b;
int num = query_num(N) - query_num(id);//询问一下大于等于 id 的个数
long long sum = query_sum(id);//询问小于等于 id 的权值和
if(sum >= (q[i].x - num) * q[i].y) cout<<"TAK"<<"\n";//判断能否成立
else cout<<"NIE"<<"\n";
}
}
return 0;
}
WZ大佬后缀树状数组的 Code
//没有注释，凑合着看吧，注释先咕着吧
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define int long long
const int N = 1e6 + 9;
int bac[N],num[N],b[N],a[N],t;
struct node{
int opt,x,y;
}q[N];
void modi(int x,int one,int two){
for(int i = x ; i ; i -= lowbit(i)){
bac[i] += one;
}
for(int i = x ; i <= t ; i += lowbit(i)){
num[i] += two;
}
}
int que(int x,int val){
int ans = 0;
for(int i = x + 1 ; i <= t ; i += lowbit(i)){
ans += bac[i];
}
ans *= val;
for(int i = x ; i ; i -= lowbit(i)){
ans += num[i];
}
return ans;
}
signed main(){
int n,m,k,aa,tot = 0; char opt;
scanf("%lld %lld",&n,&m);
for(int i = 1 ; i <= m ; i ++){
cin>>opt; scanf("%lld %lld",&k,&aa);
q[i].x = k; q[i].y = aa; b[++tot] = aa;
if(opt == ‘U‘) q[i].opt = 1;
if(opt == ‘Z‘) q[i].opt = 2;
}
sort(b + 1,b + tot + 1);
t = unique(b + 1,b + tot + 1) - b - 1;
for(int i = 1 ; i <= m ; i ++){
if(q[i].opt == 1){
if(a[q[i].x]){
int id = lower_bound(b + 1,b + t + 1,a[q[i].x]) - b;
modi(id,-1,-a[q[i].x]);
}
int id = lower_bound(b + 1,b + t + 1,q[i].y) - b;
modi(id,1,q[i].y); a[q[i].x] = q[i].y;
}
if(q[i].opt == 2){
int id = lower_bound(b + 1,b + t + 1,q[i].y) - b;
int sum = q[i].x * q[i].y;
if(que(id,q[i].y) >= sum) cout<<"TAK"<<"\n";
else cout<<"NIE"<<"\n";
}
}
return 0;
}
原文：https://www.cnblogs.com/genshy/p/13567915.html