洛谷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;
}