BZOJ 4378 「POI2015」Logistyka

发表于 | 分类于 |

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

设这个序列为 \(\{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
#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");
    }
}

Gitalking ...