bzoj4378: [POI2015]Logistyka

4378: [POI2015]Logistyka
Time Limit: 20 Sec Memory Limit: 256 MB

Description

维护一个长度为n的序列，一开始都是0，支持以下两种操作：
1.U k a 将序列中第k个数修改为a。
2.Z c s 在这个序列上，每次选出c个正数，并将它们都减去1，询问能否进行s次操作。
每次询问独立，即每次询问不会对序列进行修改。

Input

第一行包含两个正整数n,m(1<=n,m<=1000000)，分别表示序列长度和操作次数。
接下来m行为m个操作，其中1<=k,c<=n，0<=a<=10^9，1<=s<=109。

Output

包含若干行，对于每个Z询问，若可行，输出TAK，否则输出NIE。

Sample Input

3 8
U 1 5
U 2 7
Z 2 6
U 3 1
Z 2 6
U 2 2
Z 2 6
Z 2 1

Sample Output

NIE
TAK
NIE
TAK

#include<algorithm>
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int N=1000005;
struct node{
    int siz,sum;
    friend node operator + (node i,node j){
        return (node){i.siz+j.siz,i.sum+j.sum};
    }
}t[N];
int n,a[N],sor[N],k[N],c[N],m;
char ch[N][2];
void add(int i,node val){
    for (;i<=m+2;i+=(i&(-i)))
        t[i]=t[i]+val;
}
node query(int i){
    node sum=(node){0,0};
    for (;i;i-=(i&(-i)))
        sum=sum+t[i];
    return sum;
}
main (){
    scanf ("%lld%lld",&n,&m);
    add(1,(node){n,0});
    for (int i=1;i<=m;++i){
        scanf ("%s%lld%lld",ch[i],&k[i],&c[i]);
        sor[i]=c[i];
    }
    sort(sor+1,sor+m+1);
    for (int i=1;i<=m;++i){
        int t=lower_bound(sor+1,sor+m+1,c[i])-sor;
        if (ch[i][0]=='U'){
            add(a[k[i]]+1,(node){-1,-sor[a[k[i]]]});
            a[k[i]]=t;
            add(t+1,(node){1,c[i]});
        }
        else {
            node tmp=query(t+1);
            if ((n-tmp.siz)*c[i]+tmp.sum>=c[i]*k[i])puts("TAK");
            else puts("NIE");
        }
    }
    return 0;
}