4378: [POI2015]Logistyka
Time Limit: 20 Sec Memory Limit: 256 MB
Description
維護(hù)一個長度為n的序列辫呻，一開始都是0清钥，支持以下兩種操作：
1.U k a 將序列中第k個數(shù)修改為a。
2.Z c s 在這個序列上放闺，每次選出c個正數(shù)，并將它們都減去1缕坎，詢問能否進(jìn)行s次操作怖侦。
每次詢問獨立，即每次詢問不會對序列進(jìn)行修改。
Input
第一行包含兩個正整數(shù)n,m(1<=n,m<=1000000)匾寝，分別表示序列長度和操作次數(shù)搬葬。
接下來m行為m個操作，其中1<=k,c<=n艳悔，0<=a<=109急凰，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;
}
