求助为什么不重构能AC,重构却T了呢?
  • 板块P4148 简单题
  • 楼主Gary88
  • 当前回复2
  • 已保存回复2
  • 发布时间2020/12/30 23:31
  • 上次更新2023/11/5 05:28:40
查看原帖
求助为什么不重构能AC,重构却T了呢?
104963
Gary88楼主2020/12/30 23:31
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define p 0.75
using namespace std;
int n,rt,lastans,tot,num,a[1000001];
queue<int>q;
struct node
{
	int ch[2],tch,tot,f,U,D,L,R,mode;
}t[1000001];
struct pp
{
	int x,y,sz;
}s[1000001];
bool cmp1(int aa,int bb)
{
	return s[aa].x<s[bb].x;
}
bool cmp2(int aa,int bb)
{
	return s[aa].y<s[bb].y;
}
void pushup(int x)
{
	t[x].tch=t[t[x].ch[0]].tch+t[t[x].ch[1]].tch+1;
	t[x].tot=t[t[x].ch[1]].tot+t[t[x].ch[0]].tot+s[x].sz;
	t[x].U=t[x].D=s[x].y;
	t[x].L=t[x].R=s[x].x;
	if(t[x].ch[0])
	{
		t[x].U=max(t[x].U,t[t[x].ch[0]].U),t[x].D=min(t[x].D,t[t[x].ch[0]].D);
		t[x].R=max(t[x].R,t[t[x].ch[0]].R),t[x].L=min(t[x].L,t[t[x].ch[0]].L);
	}
	if(t[x].ch[1])
	{
		t[x].U=max(t[x].U,t[t[x].ch[1]].U),t[x].D=min(t[x].D,t[t[x].ch[1]].D);
		t[x].R=max(t[x].R,t[t[x].ch[1]].R),t[x].L=min(t[x].L,t[t[x].ch[1]].L);
	}
}
void divide(int x)
{
	if(!x)
	return;
	divide(t[x].ch[0]);
	a[++tot]=x;
	divide(t[x].ch[1]);
}
int build(int l,int r,int fa)
{
	if(l>r)
	return 0;
	double avx=0,avy=0,vax=0,vay=0;
	for(int i=l;i<=r;i++)
	{
		avx+=s[a[i]].x;
		avy+=s[a[i]].y;
	}
	avx/=double(r-l+1);
	avx/=double(r-l+1);
	for(int i=l;i<=r;i++)
	{
		vax+=(avx-s[a[i]].x)*(avx-s[a[i]].x);
		vay+=(avy-s[a[i]].y)*(avy-s[a[i]].y);
	}
	int mid=(l+r)>>1;
	if(vax>=vay)
	{
		nth_element(a+l,a+mid,a+r+1,cmp1);
		t[a[mid]].mode=1;
	}
	else
	{
		nth_element(a+l,a+mid,a+r+1,cmp2);
		t[a[mid]].mode=2;
	}
	t[a[mid]].f=fa;
	t[a[mid]].ch[0]=build(l,mid-1,a[mid]),t[a[mid]].ch[1]=build(mid+1,r,a[mid]);
	pushup(a[mid]);
	return a[mid];
}
bool need_rebuild(int x)
{
	return ((double(max(t[t[x].ch[0]].tch,t[t[x].ch[1]].tch)))/(double(t[x].tch)))>=p;
}
int find_rebuild(int x)
{
	if(t[x].f)
	{
		int k=find_rebuild(t[x].f);
		if(k)
		return k;
	}
	if(need_rebuild(x))
		return x;
	else
		return 0;
}
void update(int x)
{
	if(!x)
	return;
	t[x].tch=t[t[x].ch[0]].tch+t[t[x].ch[1]].tch+1;
	t[x].tot=t[t[x].ch[1]].tot+t[t[x].ch[0]].tot+s[x].sz;
	t[x].U=t[x].D=s[x].y;
	t[x].L=t[x].R=s[x].x;
	if(t[x].ch[0])
	{
		t[x].U=max(t[x].U,t[t[x].ch[0]].U),t[x].D=min(t[x].D,t[t[x].ch[0]].D);
		t[x].R=max(t[x].R,t[t[x].ch[0]].R),t[x].L=min(t[x].L,t[t[x].ch[0]].L);
	}
	if(t[x].ch[1])
	{
		t[x].U=max(t[x].U,t[t[x].ch[1]].U),t[x].D=min(t[x].D,t[t[x].ch[1]].D);
		t[x].R=max(t[x].R,t[t[x].ch[1]].R),t[x].L=min(t[x].L,t[t[x].ch[1]].L);
	}
	update(t[x].f);
}
int find(int x,int y)
{
	int u=rt;
	while(s[u].x!=x||s[u].y!=y)
	{
		if(t[u].mode==1)
		{
			if(t[u].ch[s[u].x<x])
			u=t[u].ch[s[u].x<x];
			else
			return u;
		}
		else if(t[u].mode==2)
		{
			if(t[u].ch[s[u].y<y])
			u=t[u].ch[s[u].y<y];
			else
			return u;
		}
		else
		return u;
	}
}
void insert(int x,int y,int z)
{
	if(!rt)
	{
		int K=num;
		rt=K;
		t[K].tot=z;
		t[K].tch=1;
		update(K);
		return;
	}
	int u=find(x,y);
	if(s[u].x==x&&s[u].y==y)
	{
		s[u].sz+=z;
		num--;
		update(u);
	}
	else
	{
		int kk=num;
		if(t[u].mode==1)
		{
			t[u].ch[s[u].x<x]=kk;
		}
		else if(t[u].mode==2)
		{
			t[u].ch[s[u].y<y]=kk;
		}
		else
		{
			if(abs(s[u].x-x)<abs(s[u].y-y))
			{
				t[u].mode=2;
				t[u].ch[s[u].y<y]=kk;
			}
			else
			{
				t[u].mode=1;
				t[u].ch[s[u].x<x]=kk;
			}
		}
		t[kk].f=u;
		update(kk);
		int k=find_rebuild(kk);
		if(k)
		{
			tot=0;
			int y=t[k].f,s=(t[y].ch[1]==k);
			divide(k);
			int z=build(1,tot,y);
			if(y)
			t[y].ch[s]=z;
			else
			rt=z;
			update(y);
		}
	}
}
bool in(int root,int L,int D,int R,int U)
{
	return (t[root].R>=L&&t[root].L<=R&&t[root].D<=U&&t[root].U>=D);
}
int ask(int root,int L,int D,int R,int U)
{
	if(t[root].L>=L&&t[root].R<=R&&t[root].D>=D&&t[root].U<=U)
	{
		return t[root].tot;
	}
	int ans=0;
	if(s[root].x>=L&&s[root].x<=R&&s[root].y>=D&&s[root].y<=U)
	ans+=s[root].sz;
	if(in(t[root].ch[0],L,D,R,U))
	ans+=ask(t[root].ch[0],L,D,R,U);
	if(in(t[root].ch[1],L,D,R,U))
	ans+=ask(t[root].ch[1],L,D,R,U);
	return ans;
}
int main()
{
	scanf("%d",&n);
	int mode;
	while(scanf("%d",&mode)&&mode!=3)
	{
		if(mode==1)
		{
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			x^=lastans,y^=lastans,z^=lastans;
			s[++num].x=x;
			s[num].y=y;
			s[num].sz=z;
			insert(x,y,z);
		}
		else
		{
			int xx,yy,XX,YY;
			scanf("%d%d%d%d",&xx,&yy,&XX,&YY);
			xx^=lastans,yy^=lastans,XX^=lastans,YY^=lastans;
			lastans=ask(rt,xx,yy,XX,YY);
			printf("%d\n",lastans);
		}
	}
	return 0;
}
2020/12/30 23:31
加载中...