线段树或者树状数组，我一开始拿每个点被染的次数建树，结果超时0.04STAT，后来参照大牛的题解，按照每个区间被经过的次数记数，AC。
#include<stdio.h>
typedef struct treetype
{
long l,r,count;
}treetype;
treetype tree[100000];
long n,i,a,b,max,x;
long ans[100000];
long v[20000];
void maketree(long i,long l,long r)
{
long mid;
if (l==r)
{
tree[i].l=tree[i].r=l;
tree[i].count=0;
return;
}
mid=(l+r)/2;
tree[i].l=l;
tree[i].r=r;
tree[i].count=0;
maketree(i*2,l,mid);
maketree(i*2+1,mid+1,r);
}
void insert(long i,long a,long b,long z)
{
long l,r,mid;
l=tree[i].l;r=tree[i].r;
if (z!=-1)
tree[i].count=z;
if (l==a && r==b)
{
if (tree[i].count!=-1)
{
if (x==a)
ans[tree[i].count]++;
tree[i].count+=1;
return;
}
}
mid=(l+r)/2;z=tree[i].count;
if (b<=mid)
{
insert(i*2,a,b,z);
if (z!=-1)
tree[i*2+1].count=z;
}
else if (a>mid)
{
insert(i*2+1,a,b,z);
if (z!=-1)
tree[i*2].count=z;
}
else
{
insert(i*2,a,mid,z);
insert(i*2+1,mid+1,b,z);
}
if (tree[i*2].count==-1 || tree[i*2+1].count==-1)
tree[i].count=-1;
else if (tree[i*2].count==tree[i*2+1].count)
tree[i].count=tree[i*2].count;
else
tree[i].count=-1;
}
int main()
{
scanf("%ld",&n);
for (i=1;i<=n;i++)
{
scanf("%ld %ld",&v[i],&b);
if (max<v[i])
max=v[i];
}
maketree(1,0,max);
for (i=1;i<=n;i++)
{
x=v[i];
insert(1,v[i],max,tree[1].count);
}
for (i=0;i<=n-1;i++)
printf("%ld\n",ans[i]);
}
posted on 2011-07-05 22:51
梦转千寻 阅读(157)
评论(0) 编辑 收藏 引用