WA0分求调
  • 板块P4148 简单题
  • 楼主Ahler
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/8/1 10:46
  • 上次更新2025/8/1 16:02:58
查看原帖
WA0分求调
1772213
Ahler楼主2025/8/1 10:46
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define cen cout << endl
#define c1 cout << 1 << " "
#define cs cout << " ";
using namespace std;
using namespace __gnu_pbds;
const float Ar=0.75;
int n,last_ans,root=0,now_wd=0,top=0,sum=0,st[200009];
struct point {
	int x[2],w;
} p[200009];
bool operator<(point a,point b) {
	return a.x[now_wd]<b.x[now_wd];
}
struct node {
	int mi[2],mx[2],sum,ls,rs,sz;
	point tp;
} tr[200009];
int newnode() {
	if(top) {
		return st[top--];
	}
	else {
		return ++sum;
	}
}
void up(int k) {
	int l=tr[k].ls,r=tr[k].rs;
	for(int i=0; i<2; i++) {
		tr[k].mi[i]=tr[k].mx[i]=tr[k].tp.x[i];
		if(l) {
			tr[k].mi[i]=min(tr[k].mi[i],tr[l].mi[i]);
			tr[k].mx[i]=max(tr[k].mx[i],tr[l].mx[i]);
		}
		if(r) {
			tr[k].mi[i]=min(tr[k].mi[i],tr[r].mi[i]);
			tr[k].mx[i]=max(tr[k].mx[i],tr[r].mx[i]);
		}
	}
	tr[k].sum=tr[l].sum+tr[r].sum+tr[k].tp.w;
	tr[k].sz=tr[l].sz+tr[r].sz+1;
}
int build(int l,int r,int wd) {
	if(l>r) {
		return 0;
	}
	int mid=(l+r)/2;
	int k=newnode();
	now_wd=wd;
	nth_element(p+l,p+mid,p+r+1);
	tr[k].tp=p[mid];
	tr[k].ls=build(l,mid-1,wd^1);
	tr[k].rs=build(mid+1,r,wd^1);
	up(k);
	return k;
}
void pia_qwq(int k,int &num) {
	if(tr[k].ls) {
		pia_qwq(tr[k].ls,num);
	}
	p[++num]=tr[k].tp;
	st[++top]=k;
	if(tr[k].rs) {
		pia_qwq(tr[k].rs,num);
	}
}
void check(int &k,int wd) {
	if(max(tr[tr[k].ls].sz,tr[tr[k].rs].sz)>tr[k].sz*Ar) {
		pia_qwq(k,0);
		k=build(1,tr[k].sz,wd);
	}
}
void insert(int &k,point temp,int wd) {
	if(!k) {
		k=newnode();
		tr[k].ls=tr[k].rs=0;
		tr[k].tp=temp;
		up(k);
		return;
	}
	if(temp.x[wd]<=tr[k].tp.x[wd]) {
		insert(tr[k].ls,temp,wd^1);
	}
	else {
		insert(tr[k].rs,temp,wd^1);
	}
	up(k);
	check(k,wd);
}
bool in(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2) {
	return(X1<=x1&&x2<=X2&&Y1<=y1&&y2<=Y2);
}
bool out(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2) {
	return(x1>X2||x2<X1||y1>Y2||y2<Y1);
}
int query(int &k,int x1,int y1,int x2,int y2) {
	if(!k) {
		return 0;
	}
	int temp=0;
	if(in(x1,y1,x2,y2,tr[k].mi[0],tr[k].mi[1],tr[k].mx[0],tr[k].mx[1])) {
		return tr[k].sum;
	}
	if(out(x1,y1,x2,y2,tr[k].mi[0],tr[k].mi[1],tr[k].mx[0],tr[k].mx[1])) {
		return 0;
	}
	if(in(x1,y1,x2,y2,tr[k].tp.x[0],tr[k].tp.x[1],tr[k].tp.x[0],tr[k].tp.x[1])) {
		temp+=tr[k].tp.w;
	}
	temp+=query(tr[k].ls,x1,y1,x2,y2);
	temp+=query(tr[k].rs,x1,y1,x2,y2);
	return temp;
}
signed main() {
	cin >> n;
	while(1) {
		int op;
		cin >> op;
		if(op==1) {
			int a,b,c;
			cin >> a >> b >> c;
			a^=last_ans,b^=last_ans,c^=last_ans;
			insert(root, {a,b,c},0);
		}
		if(op==2) {
			int x1,x2,y1,y2;
			cin >> x1 >> y1 >> x2 >> y2;
			x1^=last_ans;
			y1^=last_ans;
			x2^=last_ans;
			y2^=last_ans;
			last_ans=query(root,x1,y1,x2,y2);
			cout << last_ans;
			cen;
		}
		if(op==3) {
			break;
		}
	}
	return 0;
}
2025/8/1 10:46
加载中...