BZOJ 4378.「POI2015」Logistyka

首先看到这道题就知道这个询问肯定可以转化为判断某个条件。
考虑构造这个条件。

设这个序列为 {ai}\{a_i\},对于一个询问 ,我们首先贪心地选择 s\ge s 的数来减,减不够了再用 <s< s 的。
于是设 cnt=i=1n[ais],sum=i=1n[ai<s]aicnt = \sum\limits_{i=1}^n [a_i \ge s],sum = \sum\limits_{i=1}^n [a_i < s]a_i
条件即 sum(ccnt)ssum \ge (c-cnt)s
这个显然是必要条件,但是充分性还有待考虑,因为我们无法确定剩下还能选够 cc 个数。

注意到 <s< s 的数最少也只能有 sums1\lceil\frac{sum}{s-1}\rceil 个。
然后注意到
sum(ccnt)ssum \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
#include <cstdio>
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");
}
}