蒟蒻的代码#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;
}