可爱线段树在线求调(WA #6 #8)
查看原帖
可爱线段树在线求调(WA #6 #8)
179253
无尽星空楼主2024/3/15 09:46
#include<bits/stdc++.h>
#define gc getchar()
#define ls nw<<1
#define rs ls|1
#define md (l+r>>1)
using namespace std;
const int N=100005;
int q,t[2][N<<2],nm[N],fm[N],fz[N],op[N],qr[N],Q,zr,id[N],cnt;
bool us[N];
inline int read()
{
	int s=0,w=1;char c=gc;
	while(c<48||c>57)  w=(c=='-')?-1:w,c=gc;
	while(c>47&&c<58)  s=s*10+(c^48),c=gc;
	return s*w;
}
bool cmp(int i,int j) {return 1ll*fz[i]*fm[j]<1ll*fz[j]*fm[i];}
void cg(int nw,int l,int r,int x,int a,bool lct)
{
	t[lct][nw]+=a;
	if(l==r)  return;
	if(x>md)  cg(rs,md+1,r,x,a,lct);
	else  cg(ls,l,md,x,a,lct);
}
inline bool les(int v,int i) {return 1ll*v*fm[i]<fz[i];}
inline bool lesn(int v,int i) {return 1ll*v*fm[i]<=fz[i];}
inline bool grtn(int v,int i) {return 1ll*v*fm[i]>=fz[i];}
inline bool grt(int v,int i) {return 1ll*v*fm[i]>fz[i];}
int qry(int nw,int l,int r,int v,bool lct)
{
	if(lct)
	{
		if(les(v,qr[l]))  return t[1][nw];
		if(grtn(v,qr[r]))  return 0;
		if(l!=r)  return grtn(v,qr[md])?qry(rs,md+1,r,v,1):qry(ls,l,md,v,1)+t[1][rs];
	}
	else
	{
		if(grt(v,qr[r]))  return t[0][nw];
		if(lesn(v,qr[l]))  return 0;
		if(l!=r)  return lesn(v,qr[md+1])?qry(ls,l,md,v,0):t[0][ls]+qry(rs,md+1,r,v,0);
	}
}
int main()
{
	q=read();
	for(int i=1;i<=q;i++)
	{
		char c=gc;
		while(c<'A'||c>'Q')  c=gc;
		if(c=='A')
		{
			fm[i]=read();fz[i]=read();fz[i]=read()-fz[i];
			id[++cnt]=i;
			if(fm[i]==0)  continue;
			if(fm[i]<0)  fm[i]*=-1,fz[i]*=-1,op[i]=1;
			qr[++Q]=i;
		}
		else  op[i]=2+(c=='Q'),nm[i]=read();
	}
	sort(qr+1,qr+1+Q,cmp);
	if(Q)  nm[qr[1]]=1;
	for(int i=2;i<=Q;i++)
		if(1ll*fz[qr[i]]*fm[qr[i-1]]!=1ll*fz[qr[i-1]]*fm[qr[i]])  nm[qr[i]]=i;
	for(int i=1;i<=q;i++)
		if(op[i]<2)
		{
			us[i]=1;
			if(fm[i]!=0)  cg(1,1,Q,nm[i],1,op[i]);
			else  zr+=fz[i]<0;
		}
		else
			if(op[i]==2)
			{
				int x=id[nm[i]];
				if(!us[x])  continue;
				if(fm[x]!=0)  cg(1,1,Q,nm[x],-1,op[x]);
				else  zr-=fz[x]<0;
				us[x]=0;
			}
			else  printf("%d\n",zr+qry(1,1,Q,nm[i],0)+qry(1,1,Q,nm[i],1));
	return 0;
}
2024/3/15 09:46
加载中...