洛谷3586 [POI2015]LOG

题意

给出一个长度为 $n(\le 10^6)$ 的全 $0$ 序列，要求支持以下操作：

1. 单点修改
2. 给出 $(c,s)$ ，每次取 $c$ 个正数 $-1$ ，问能否操作 $s$ 次。

题解

先考虑操作 $2$ 。设 $\geq s$ 的数有 $x$ 个，这些数每次都可以取，此外还需要 $(c-x)$ 个数。设 $< s$ 的数的和为 $sum$ ，如果 $sum < (c-s)\times s$ 就无解，即每次取 $(c-x)$ 个数无法取 $s$ 次。

所以只需要维护 $\geq s$ 的数的个数以及 $< s$ 的数的和，可以用树状数组维护。因为 $s$ 范围较大，所以需要离线存下来后离散化。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=1000005;
ll t2[N];
bool o[N];
int n,m,cnt,a[N],b[N],num[N],s[N],t[N];

inline void add1(int x,int y) { for (;x<=cnt;x+=x&-x) t[x]+=y; }

inline void add2(int x,int y) { for (;x<=cnt;x+=x&-x) t2[x]+=y; }

inline int query1(int x)
{
    int ans=0;
    for (;x;x-=x&-x) ans+=t[x];
    return ans;
}

inline ll query2(int x)
{
    ll ans=0;
    for (;x;x-=x&-x) ans+=t2[x];
    return ans;
}

signed main()
{
    n=read(); m=read();
    num[++cnt]=0;
    for (int i=1;i<=m;i++)
    {
        char ch[5]; scanf("%s",ch);
        o[i]=ch[0]=='U';
        a[i]=read(); b[i]=read();
        num[++cnt]=b[i];
    }
    sort(num+1,num+cnt+1);
    cnt=unique(num+1,num+cnt+1)-num-1;
    for (int i=1;i<=m;i++)
    {
        b[i]=lower_bound(num+1,num+cnt+1,b[i])-num;
        if (o[i])
        {
            if (s[a[i]]) add1(s[a[i]],-1),add2(s[a[i]],-num[s[a[i]]]); //不为0，需要减去原数的贡献
            s[a[i]]=b[i]; //赋值
            add1(s[a[i]],1);
            add2(s[a[i]],num[s[a[i]]]);
        }
        else
        {
            int x=query1(cnt)-query1(b[i]-1);
            ll sum=query2(b[i]-1);
            if (sum>=1ll*(a[i]-x)*num[b[i]]) puts("TAK");
            else puts("NIE");
        }
    }
    return 0;
}