20pts 其余 MLE 求助
查看原帖
20pts 其余 MLE 求助
518232
Sternenlicht楼主2023/6/27 18:57

rt

#include <algorithm>
#define LL long long
inline LL read(){LL x=0,f=1;char c=getchar();for(;c<'0'||c>'9';c=getchar())if (c=='-')f=-1;for (;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^48);return x*f;}
inline void write(LL x,char c='\n'){if (x){if (x<0)x=-x,putchar('-');char a[30];short l;for (l=0;x;x/=10)a[l++]=x%10^48;for (l--;l>=0;l--)putchar(a[l]);}else putchar('0');putchar(c);}
using namespace std;

const double alpha = 0.75;
const int N = 5e5+10;
struct Point{int x,y,val;}point[N];
int idx[N],tot,root,cnt,n,lastans;
int ls[N],rs[N],d[N],mx[N][2],mn[N][2],siz[N],sum[N];
inline bool cmpx(int x,int y){return point[x].x<point[y].y;}
inline bool cmpy(int x,int y){return point[x].y<point[y].y;}
void save(int u){if (!u)return ;save(ls[u]);idx[++tot]=u;save(rs[u]);}
inline void pushup(int u){
	siz[u]=siz[ls[u]]+siz[rs[u]]+1;
	sum[u]=sum[ls[u]]+sum[rs[u]]+point[u].val;
	mx[u][0]=mn[u][0]=point[u].x;
	mx[u][1]=mn[u][1]=point[u].y;
	if (ls[u])
		mx[u][0]=max(mx[u][0],mx[ls[u]][0]),
		mn[u][0]=min(mn[u][0],mn[ls[u]][0]),
		mx[u][1]=max(mx[u][1],mx[ls[u]][1]),
		mn[u][1]=min(mn[u][1],mn[ls[u]][1]);
	if (rs[u])
		mx[u][0]=max(mx[u][0],mx[rs[u]][0]),
		mn[u][0]=min(mn[u][0],mn[rs[u]][0]),
		mx[u][1]=max(mx[u][1],mx[rs[u]][1]),
		mn[u][1]=min(mn[u][1],mn[rs[u]][1]);
}
int build(int l,int r){
	if (l>r)return 0;
	int mid=(l+r)>>1;
	double ave1=0,ave2=0,sum1=0,sum2=0;
	for (int i=l;i<=r;i++)ave1+=point[idx[i]].x,ave2+=point[idx[i]].y;
	ave1/=(r-l+1),ave2/=(r-l+1);
	for (int i=l;i<=r;i++)
		sum1+=(ave1-point[idx[i]].x)*(ave1-point[idx[i]].x),
		sum2+=(ave2-point[idx[i]].y)*(ave2-point[idx[i]].y);
	if (sum1>sum2)nth_element(idx+l,idx+mid,idx+r+1,cmpx),d[mid]=1;
	else nth_element(idx+l,idx+mid,idx+r+1,cmpy),d[mid]=2;
	ls[mid]=build(l,mid-1);
	rs[mid]=build(mid+1,r);
	pushup(mid);
	return mid;
}
inline void rebuild(int &u){tot=0;save(u);u=build(1,tot);}
inline bool notbalance(int u){return alpha*siz[u]<=(double)max(siz[ls[u]],siz[rs[u]]);}
void Insert(int &u,int pos){
	if (!u){u=pos;pushup(u);return ;}
	if (d[u]==1)
		if (point[pos].x<=point[u].x)
			Insert(ls[u],pos);
		else
			Insert(rs[u],pos);
	else
		if (point[pos].y<=point[u].y)
			Insert(ls[u],pos);
		else
			Insert(rs[u],pos);
	pushup(u);
	if (notbalance(u))rebuild(u);
}
int query(int u,int x1,int y1,int x2,int y2){
	if (!u||x2<mn[u][0]||x1>mx[u][0]||y2<mn[u][1]||y1>mx[u][1])return 0;
	if (x1<=mn[u][0]&&x2>=mx[u][0]&&y1<=mn[u][1]&&y2>=mx[u][1])return sum[u];
	int in_or_out=0;//判断当前点是否在所求矩形(x1,y1)(x2,y2)中 
	if (x1<=point[u].x&&x2>=point[u].x&&y1<=point[u].y&&y2>=point[u].y)in_or_out+=point[u].val;
	return query(ls[u],x1,y1,x2,y2)+query(rs[u],x1,y1,x2,y2)+in_or_out;
}
int main(){
	n=read();
	while (1){
		int opt=read();
		if (opt==3)break;
		if (opt==1){
			cnt++;
			point[cnt].x=read()^lastans;
			point[cnt].y=read()^lastans;
			point[cnt].val=read()^lastans;
			Insert(root,cnt);
		}
		if (opt==2){
			int x1=read()^lastans,y1=read()^lastans;
			int x2=read()^lastans,y2=read()^lastans;
			write(lastans=query(root,x1,y1,x2,y2));
		}
	}
	return 0;
}
2023/6/27 18:57
加载中...