首先看到这道题就知道这个询问肯定可以转化为判断某个条件。
考虑构造这个条件。
设这个序列为 \(\{a_i\}\)，对于一个询问 \(\texttt Z\ c\ s\)，我们首先贪心地选择 \(\ge s\) 的数来减，减不够了再用 \(< s\) 的。
于是设 \(cnt = \sum\limits_{i=1}^n [a_i \ge s],sum = \sum\limits_{i=1}^n [a_i < s]a_i\)。
条件即 \(sum \ge (c-cnt)s\)。
这个显然是必要条件，但是充分性还有待考虑，因为我们无法确定剩下还能选够 \(c\) 个数。
注意到 \(< s\) 的数最少也只能有 \(\lceil\frac{sum}{s-1}\rceil\) 个。
然后注意到 \(\lceil\frac{sum}{s-1}\rceil \ge \frac{sum}{s-1} > \frac{sum}s \implies \lceil\frac{sum}{s-1}\rceil + cnt \ge c\)。
故 \(sum \ge (c-cnt)s\) 对询问的充分性成立。
随便挑个数据结构维护下就行了。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
using namespace std;
const int N = 1e6;
const int C = 1e9;
int n,m,a[N + 5];
struct node
{
int cnt;
long long sum;
int ls,rs;
} seg[(N << 3) + 10];
int rt;
void insert(int x,int k,int &p,int tl,int tr)
{
static int tot = 0;
!p && (p = ++tot),seg[p].cnt += k,seg[p].sum += x * k;
if(tl == tr)
return ;
int mid = tl + tr >> 1;
x <= mid ? insert(x,k,seg[p].ls,tl,mid) : insert(x,k,seg[p].rs,mid + 1,tr);
}
int query_cnt(int l,int r,int p,int tl,int tr)
{
if(!p || (l <= tl && tr <= r))
return seg[p].cnt;
int ret = 0;
int mid = tl + tr >> 1;
l <= mid && (ret += query_cnt(l,r,seg[p].ls,tl,mid));
r > mid && (ret += query_cnt(l,r,seg[p].rs,mid + 1,tr));
return ret;
}
long long query_sum(int l,int r,int p,int tl,int tr)
{
if(!p || (l <= tl && tr <= r))
return seg[p].sum;
long long ret = 0;
int mid = tl + tr >> 1;
l <= mid && (ret += query_sum(l,r,seg[p].ls,tl,mid));
r > mid && (ret += query_sum(l,r,seg[p].rs,mid + 1,tr));
return ret;
}
int main()
{
scanf("%d%d",&n,&m),insert(0,n,rt,0,C);
char op;
int x,k;
for(;m;--m)
{
scanf(" %c%d%d",&op,&x,&k);
if(op == 'U')
insert(a[x],-1,rt,0,C),a[x] = k,insert(a[x],1,rt,0,C);
else
puts(query_sum(0,k - 1,rt,0,C) >= (long long)(x - query_cnt(k,C,rt,0,C)) * k ? "TAK" : "NIE");
}
}