洛谷P3586 [POI2015] LOG 题解

题目链接：P3586 [POI2015] LOG

题意：

维护一个长度为 $n$ 的序列，一开始都是 $0$，支持以下两种操作：

U k a 将序列中第 $k$ 个数修改为 $a$。

Z c s 在这个序列上，每次选出 $c$ 个正数，并将它们都减去 $1$，询问能否进行 $s$ 次操作。

每次询问独立，即每次询问不会对序列进行修改。

【数据范围】

对于 $100\%$ 的数据，$1\leq n,m\leq 10^6$，$1\leq k,c\leq n$，$0\leq a\leq 10^9$，$1\leq s\leq 10^9$。

~~不是区间询问。注意了嗷。~~

先考虑2操作

对于大于 $s$ 的数，显然最多只能减 $s$ 次

对于小于等于 $s$ 的数，肯定要把它全部减成 $0$

设 $S=\sum x_i [x_i\le s]$ ，则剩下的 $c\times s - S$ 由大于 $s$ 的数贡献

设 $\text{cnt} = \sum [x_i \le s]$ ，则大于 $s$ 的数共有 $(n-\text{cnt})$ 个

于是我们只要判断下面的柿子是否成立

$(n-\text{cnt}) \times s \ge c \times s -S$

即

$S \ge s \times (c-n+\text{cnt})$

问题就转化为了如何求解 $S$ 和 $\text{cnt}$

「比一个数小的数的数量」，显然树状数组
「比一个数小的数的和」，我们把这个和看成这些数的权值

那么这个就是上个问题的 add(x,1) 改成 add(x,x)，还是树状数组

当然，我们直接用树状数组肯定是不行的，因为 $a\le 10^9$

考虑把原数组（本题中只有 $0$ ）和所有询问中的 $a,s$ 离散化

相信学过主席树的都知道这个操作吧（其实没学过也没关系）

时间复杂度 $O(m \log m)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e6+15)

int n,m,o,b[N],t[N];
struct Query
{int op,c,s;}q[N];
struct BIT
{
    int tree[N];
    int lowbit(int x){return x&(-x);}
    void add(int x,int v)
    {
        for(; x&&x<=o; x+=lowbit(x))
            tree[x]+=v;
    }
    int qSum(int x)
    {
        int res=0;
        for(; x>=1; x-=lowbit(x))
            res+=tree[x];
        return res;
    }
}t1,t2;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    char ch; b[++o]=0;
    cin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        cin >> ch >> q[i].c >> q[i].s;
        q[i].op=(ch=='U')?1:2; b[++o]=q[i].s;
    }
    sort(b+1,b+1+o);
    o=unique(b+1,b+1+o)-b-1;
    for(int i=1,x; i<=m; i++)
    {
        q[i].s=lower_bound(b+1,b+1+o,q[i].s)-b;
        if(q[i].op==1)
        {
            if(t[q[i].c]) // 删除这个数之前去掉它的贡献
                x=t[q[i].c],t1.add(x,-1),t2.add(x,-b[x]);
            x=t[q[i].c]=q[i].s; // 这里的x是我从其他题解学的，只是减少代码用的
            t1.add(x,1);t2.add(x,b[x]);
        }
        else
        {
            x=t1.qSum(o)-t1.qSum(q[i].s-1);
            int sum=q[i].s?t2.qSum(q[i].s-1):0;
            cout << ((sum>=(q[i].c-x)*(b[q[i].s]))?"TAK\n":"NIE\n");
        }
    }
    return 0;
}