BZOJ 4378 「POI2015」Logistyka

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

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

注意到 <s 的数最少也只能有 ⌈sums−1⌉ 个。
然后注意到 ⌈sums−1⌉≥sums−1>sums⟹⌈sums−1⌉+cnt≥c。
故 sum≥(c−cnt)s 对询问的充分性成立。

随便挑个数据结构维护下就行了。

代码：

#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");
    }
}