C88 两个树状数组 P3586 [POI2015] LOG

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10;
template<typename T>void qr(T &x)
{
	x=0;int f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-')f=-1;
	for(; isdigit(c);c=getchar()) x=x*10+c-'0';
	x=x*f;
}
int n,m;
char op[N];
int c[N],s[N],b[N],p[N];
LL cnt,sum,s1[N],s2[N]; //s1种类数,s2数量和
void change(LL*s,int x,int k){for(; x<=m; x+=x&-x)s[x]+=k;}
LL query(LL*s,int x){LL t=0;for(; x; x-=x&-x)t+=s[x];return t;}
int main()
{
	qr(n);qr(m);
	for(int i=1; i<=m; i++)scanf(" %c",&op[i]),qr(c[i]),qr(s[i]),b[i]=s[i];
	sort(b+1,b+m+1); //离散化
	for(int i=1; i<=n; i++) p[i]=m+1; //无用位置
	for(int i=1,si,k; i<=m; i++)
	{
		if(op[i]=='U')
		{
			k=c[i]; //修改值的下标
			si=lower_bound(b+1,b+m+1,s[i])-b; //修改值的离散值
			change(s1,si,1);          //加上新种类数的贡献
			change(s1,p[k],-1);       //减去旧种类数的贡献
			change(s2,si,b[si]);      //加上新数量的贡献
			change(s2,p[k],-b[p[k]]); //减去旧数量的贡献
			p[k]=si; //记录第k个数的离散值
		}
		else
		{
			si=lower_bound(b+1,b+m+1,s[i])-b; //高度的离散值
			cnt=query(s1,m)-query(s1,si-1); //>=s的种类数

C88 两个树状数组 P3586 [POI2015] LOG

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10;
template<typename T>void qr(T &x)
{
	x=0;int f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-')f=-1;
	for(; isdigit(c);c=getchar()) x=x*10+c-'0';
	x=x*f;
}
int n,m;
char op[N];
int c[N],s[N],b[N],p[N];
LL cnt,sum,s1[N],s2[N]; //s1种类数,s2数量和
void change(LL*s,int x,int k){for(; x<=m; x+=x&-x)s[x]+=k;}
LL query(LL*s,int x){LL t=0;for(; x; x-=x&-x)t+=s[x];return t;}
int main()
{
	qr(n);qr(m);
	for(int i=1; i<=m; i++)scanf(" %c",&op[i]),qr(c[i]),qr(s[i]),b[i]=s[i];
	sort(b+1,b+m+1); //离散化
	for(int i=1; i<=n; i++) p[i]=m+1; //无用位置
	for(int i=1,si,k; i<=m; i++)
	{
		if(op[i]=='U')
		{
			k=c[i]; //修改值的下标
			si=lower_bound(b+1,b+m+1,s[i])-b; //修改值的离散值
			change(s1,si,1);          //加上新种类数的贡献
			change(s1,p[k],-1);       //减去旧种类数的贡献
			change(s2,si,b[si]);      //加上新数量的贡献
			change(s2,p[k],-b[p[k]]); //减去旧数量的贡献
			p[k]=si; //记录第k个数的离散值
		}
		else
		{
			si=lower_bound(b+1,b+m+1,s[i])-b; //高度的离散值
			cnt=query(s1,m)-query(s1,si-1); //>=s的种类数
			sum=query(s2,si-1); //<s的数量和
			printf("%s\n",sum>=(c[i]-cnt)*s[i]?"TAK":"NIE");
		}
	}
	return 0;
}