Color the ball
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 13501 Accepted Submission(s): 6783
Problem Description N個氣球排成一排,從左到右依次編号為1,2,3....N.每次給定2個整數a b(a <= b),lele便為騎上他的“小飛鴿"牌電動車從氣球a開始到氣球b依次給每個氣球塗一次顔色。但是N次以後lele已經忘記了第I個氣球已經塗過幾次顔色了,你能幫他算出每個氣球被塗過幾次顔色嗎?
Input 每個測試執行個體第一行為一個整數N,(N <= 100000).接下來的N行,每行包括2個整數a b(1 <= a <= b <= N)。
當N = 0,輸入結束。
Output 每個測試執行個體輸出一行,包括N個整數,第I個數代表第I個氣球總共被塗色的次數。
Sample Input
3
1 1
2 2
3 3
3
1 1
1 2
1 3
0
Sample Output
1 1 1
3 2 1
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 100010
using namespace std;
struct zz
{
int l;
int r;
int c;
}q[N<<2];
int col[N];
void build(int gen,int l,int r)
{
q[gen].l=l;
q[gen].r=r;
q[gen].c=0;
if(l==r)
return ;
int mid=(l+r)/2;
build(gen<<1,l,mid);
build(gen<<1|1,mid+1,r);
}
void update(int gen,int l,int r)
{
if(q[gen].l==l&&r==q[gen].r)
{
q[gen].c++;
return ;
}
int mid=(q[gen].l+q[gen].r)/2;
if(r<=mid)
update(gen<<1,l,r);
else if(l>mid)
update(gen<<1|1,l,r);
else
{
update(gen<<1,l,mid);
update(gen<<1|1,mid+1,r);
}
}
int query(int gen,int l,int r)
{
if(q[gen].l==l&&q[gen].r==r)
return q[gen].c;
if(q[gen].l==q[gen].r)
return 0;
int mid=(q[gen].l+q[gen].r)/2;
if(r<=mid)
return query(gen<<1,l,r)+q[gen].c;
else if(l>mid)
return query(gen<<1|1,l,r)+q[gen].c;
else
return query(gen<<1,l,mid)+query(gen<<1|1,mid+1,r)+q[gen].c;
}
int main()
{
int n,i;
int x,y;
while(scanf("%d",&n),n)
{
build(1,1,n);
for(i=1;i<=n;i++)
{
scanf("%d %d",&x,&y);
update(1,x,y);
}
for(i=1;i<n;i++)
printf("%d ",query(1,i,i));
printf("%d\n",query(1,n,n));
}
return 0;
}
//隊友寫的:加了個數組,更好了解。 #include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 100010
#define INF 0x3f3f3f3f
using namespace std;
int a[N];
struct zz
{
int l;
int r;
int m;
}q[N<<2];
void build(int gen,int l,int r)
{
q[gen].l=l;
q[gen].r=r;
q[gen].m=0;
if(l==r)
return ;
int mid=(l+r)/2;
build(gen<<1,l,mid);
build(gen<<1|1,mid+1,r);
}
void update(int gen,int l,int r)
{
if(q[gen].l==l&&q[gen].r==r)
{
q[gen].m++;
return ;
}
int mid=(q[gen].l+q[gen].r)/2;
if(r<=mid)
update(gen<<1,l,r);
else if(l>mid)
update(gen<<1|1,l,r);
else
{
update(gen<<1,l,mid);
update(gen<<1|1,mid+1,r);
}
}
void query(int gen)
{
if(q[gen].m)
{
for(int i=q[gen].l;i<=q[gen].r;i++)
a[i]+=q[gen].m;
}
if(q[gen].l==q[gen].r)
return ;
query(gen<<1);
query(gen<<1|1);
}
int main()
{
int n,i;
int x,y,z;
while(scanf("%d",&n),n)
{
build(1,1,n);
memset(a,0,sizeof(a));
for(i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
update(1,x,y);
}
query(1);
printf("%d",a[1]);
for(i=2;i<=n;i++)
printf(" %d",a[i]);
printf("\n");
}
return 0;
}
//樹狀數組 #include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 100010
using namespace std;
int q[N];
int n;
int lowbit(int x)
{
return x&-x;
}
void update(int i,int x)
{
while(i>0)
{
q[i]+=x;
i-=lowbit(i);
}
}
int query(int i)//向上統計[i,n]區間被染色的次數
{
int ans=0;
while(i<=n)
{
ans+=q[i];
i+=lowbit(i);
}
return ans;
}
int main()
{
while(scanf("%d",&n),n)
{
memset(q,0,sizeof(q));
int x,y,i;
for(i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
update(y,1);//将y以下的區間+1
update(x-1,-1);//将x以下的區間-1
}
printf("%d",query(1));
for(i=2;i<=n;i++)
printf(" %d",query(i));
printf("\n");
}
return 0;
}