【BZOJ4378】【POI2015】Logistyka

  对于每次询问c，s，首先统计出数列中大于等于s的元素个数cnt。如果cnt>=c那么显然满足条件；否则对剩下的n-cnt个小于s的数，如果他们的和大于等于s*(n-cnt)那么满足条件（请感性地去理解 ---- JD）。

  用两个树状数组维护一下就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=1000010;

void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}
char readchar() {char ch;while ((ch=getchar())!='U' && ch!='Z');return ch;}

struct Info {int type,a,b;}I[maxn];
int s[maxn],v[maxn],vcnt;
LL f1[maxn],f2[maxn];
int n,m;

inline int lowbit(int x) {return x&-x;}
void Change(LL *arr,int pos,LL c) {while (pos<=vcnt) arr[pos]+=c,pos+=lowbit(pos);}
LL Query(LL *arr,int pos) {LL res=0;while (pos) res+=arr[pos],pos-=lowbit(pos);return res;}

int main()
{
	read(n);read(m);
	for (int i=1;i<=m;i++)
	{
		char cot=readchar();
		I[i].type=cot=='Z';
		read(I[i].a),read(I[i].b);
		v[i]=I[i].b;
	}
	v[n+1]=0;
	sort(v+1,v+2+m);vcnt=unique(v+1,v+2+m)-(v+1);
	Change(f1,1,n);
	for (int i=1;i<=n;i++) s[i]=1;
	for (int i=1;i<=m;i++) if (I[i].type==0) I[i].b=lower_bound(v+1,v+1+vcnt,I[i].b)-v;
	for (int i=1;i<=m;i++)
	if (I[i].type==0)
	{
		int numu=s[I[i].a],numv=I[i].b;
		Change(f1,numu,-1),Change(f2,numu,-v[numu]);
		Change(f1,numv, 1),Change(f2,numv, v[numv]);
		s[I[i].a]=I[i].b;
	}
	else
	{
		int pos=lower_bound(v+1,v+1+vcnt,I[i].b)-v;
		int cnt=n-Query(f1,pos-1);
		LL prev=Query(f2,pos-1);
		if (cnt>=I[i].a || prev>=(LL)(I[i].a-cnt)*(I[i].b)) puts("TAK");else puts("NIE");
	}
	return 0;
}