90求助
查看原帖
90求助
400201
WuyanruVR楼主2021/5/30 11:55

蒟蒻的代码#10一直TLE,超时0.08秒左右,请问各位大神有没有什么常数优化。

做法:x轴排序维护,y轴和z轴使用线段树涛线段树进行处理。

代码:

#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
struct coor {
	int x,y,z;
} a[100002];
bool operator < (coor a,coor b) {
	if(a.x!=b.x)
		return a.x<b.x;
	if(a.y!=b.y)
		return a.y<b.y;
	return a.z<b.z;
}
int ans[100000];
struct tr3 {
	int num;
	int lson,rson;
	tr3 () {
		num=0;
		lson=0;
		rson=0;
	}
};
struct tr2 {
	int num;
	int lson,rson;
	vector<tr3>leaftr;
	tr2() {
		num=0;
		lson=0;
		rson=0;
		leaftr.clear();
		leaftr.push_back(tr3());
	}
};
vector<tr2>tr;
int n,m;
void j2(int p,int pp,int pl,int pr,int y,int k) {
	if(pl==y&&y==pr) {
		tr[p].leaftr[pp].num+=k;
		return ;
	}
	int mid=(pl+pr)>>1;
	if(y<=mid) {
		if(tr[p].leaftr[pp].lson==0) {
			tr[p].leaftr.push_back(tr3());
			tr[p].leaftr[pp].lson=tr[p].leaftr.size()-1;
		}
		tr[p].leaftr[pp].num-=tr[p].leaftr[tr[p].leaftr[pp].lson].num;
		j2(p,tr[p].leaftr[pp].lson,pl,mid,y,k);
		tr[p].leaftr[pp].num+=tr[p].leaftr[tr[p].leaftr[pp].lson].num;
	} else {
		if(tr[p].leaftr[pp].rson==0) {
			tr[p].leaftr.push_back(tr3());
			tr[p].leaftr[pp].rson=tr[p].leaftr.size()-1;
		}
		tr[p].leaftr[pp].num-=tr[p].leaftr[tr[p].leaftr[pp].rson].num;
		j2(p,tr[p].leaftr[pp].rson,mid+1,pr,y,k);
		tr[p].leaftr[pp].num+=tr[p].leaftr[tr[p].leaftr[pp].rson].num;
	}
}
void j(int p,int pl,int pr,int x,int y,int k) {
	j2(p,0,1,m,y,k);
	tr[p].num+=k;
	if(pl==x&&x==pr)
		return ;
	int mid=(pl+pr)>>1;
	if(x<=mid) {
		if(tr[p].lson==0) {
			tr.push_back(tr2());
			tr[p].lson=tr.size()-1;
		}
		tr[p].num-=tr[tr[p].lson].num;
		j(tr[p].lson,pl,mid,x,y,k);
		tr[p].num+=tr[tr[p].lson].num;
	} else {
		if(tr[p].rson==0) {
			tr.push_back(tr2());
			tr[p].rson=tr.size()-1;
		}
		tr[p].num-=tr[tr[p].rson].num;
		j(tr[p].rson,mid+1,pr,x,y,k);
		tr[p].num+=tr[tr[p].rson].num;
	}
}
int get2(int p,int pp,int pl,int pr,int y) {
	if(pr<=y)
		return tr[p].leaftr[pp].num;
	int mid=(pl+pr)>>1;
	int ans=0;
	if(tr[p].leaftr[pp].lson!=0)
		ans+=get2(p,tr[p].leaftr[pp].lson,pl,mid,y);
	if(tr[p].leaftr[pp].rson!=0&&y>mid)
		ans+=get2(p,tr[p].leaftr[pp].rson,mid+1,pr,y);
	return ans;
}
int get(int p,int pl,int pr,int x,int y) {
	if(pr<=x)
		return get2(p,0,1,m,y);
	int mid=(pl+pr)>>1;
	int ans=0;
	if(tr[p].lson!=0)
		ans+=get(tr[p].lson,pl,mid,x,y);
	if(tr[p].rson!=0&&x>mid)
		ans+=get(tr[p].rson,mid+1,pr,x,y);
	return ans;
}
inline int read() {
	int s=0,w=1;
	char ch;
	while((ch=getchar())>'9'||ch<'0')
		if(ch=='-')
			w=-1;
	while(ch>='0'&&ch<='9') {
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*w;
}
int main() {
	tr.push_back(tr2());
	n=read(),m=read();
	for(int i=1; i<=n; i++)
		a[i].x=read(),a[i].y=read(),a[i].z=read();
	sort(a+1,a+n+1);
	int k=0;
	for(int i=1; i<=n; ++i) {
		++k;
		if(a[i].x==a[i+1].x&&a[i].y==a[i+1].y&&a[i].z==a[i+1].z)
			continue;
		j(0,1,m,a[i].y,a[i].z,k);
		ans[get(0,1,m,a[i].y,a[i].z)-1]+=k;
		k=0;
	}
	for(int i=0; i<n; ++i)
		printf("%d\n",ans[i]);
	return 0;
}
2021/5/30 11:55
加载中...