Color the ball
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 12209 Accepted Submission(s): 6094
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
Author 8600
本題既可以用樹狀數組也可用線段樹
注意一點就是:本題涉及到區間的更行,不同于點的更新
用線段樹寫(整段區間的更新,不同于點的更行,是以用結構體比較簡單)
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define MAX 100000
#define mid ((tree[v].L+tree[v].R)>>1)
#define lson l,mid,v<<1//對左孩子進行操作
#define rson mid+1,r,v<<1|1//對右孩子進行操作
struct node
{
int L;//左結點
int R;//右結點
int V;//結點的序号
}tree[4*MAX];
void build(int l,int r,int v)//建一顆樹
{
if(l==r)//遞歸出口
{
tree[v].L=l;
tree[v].R=r;
tree[v].V=0;
return;
}
tree[v].L=l;
tree[v].R=r;
tree[v].V=0;
build(lson);//從左孩子區間建樹
build(rson);//從右孩子區間建樹
}
void update(int l,int r,int v)
{
if(tree[v].L==l&&tree[v].R==r)//遞歸出口 找到區間[L=l,R=r]
{
tree[v].V++;
return ;
}
if(tree[v].L==tree[v].R)//遞歸出口 沒有找到區間[L=R]=>[.]類似一個點
return ;
if(r<=mid)//更新左孩子區間 [L,[l,r],mid,R]
update(l,r,2*v);
else if(mid<l)//更新右孩子區間 [L,mid,[l,r],R]
update(l,r,2*v+1);
else// [L,[l,mid,r],R]
{
update(lson);//[L,[l,...mid]]
update(rson);//[[mid+1,...,r],R]
}
}
int query(int l,int r,int v)
{
if(tree[v].L==l&&tree[v].R==r)//遞歸出口 找到區間[L=l,R=r]
return tree[v].V;
if(tree[v].L==tree[v].R)//遞歸出口 沒有找到區間[L=R]=>[.]類似一個點
return 0;
if(r<=mid)//查找左孩子區間 [L,[l,r],mid,R]
return query(l,r,2*v)+tree[v].V;
else if(l>mid)//查找右孩子區間 [L,mid,[l,r],R]
return query(l,r,2*v+1)+tree[v].V;
else// [L,[l,mid,r],R]
return query(lson)+query(rson)+tree[v].V; //[L,[l,..,mid]]+[[mid+1,r],R];
}
int main()
{
int n;
while(scanf("%d",&n),n)
{
build(1,n,1);
for(int i=1;i<=n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
update(a,b,1);//每個氣球塗一次
}
for(int i=1;i<n;i++)//每個氣球塗一次
printf("%d ",query(i,i,1));
printf("%d\n",query(n,n,1));
}
return 0;
}
這個題也可用樹狀數組來解決:
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int M=100001;
int tree[M];
int n;
int lowbit(int x)//計算2^K;
{
return x&(-x);
}
void update(int i,int x)//更新第i個結點的值
{
while(i>0)
{
tree[i]+=x;
i-=lowbit(i);
}
}
int query(int i)//向上統計[i,n]區間被染色的次數
{
int ans=0;
while(i<=n)
{
ans+=tree[i];
i+=lowbit(i);
}
return ans;
}
int main()
{
while(scanf("%d",&n),n)
{
memset(tree,0,sizeof(tree));//不能少
int i,a,b;
for(i=1;i<=n;++i)
{
scanf("%d%d",&a,&b);
update(b,1);//将b以下的區間+1;
update(a-1,-1);//将a以下的區間-1;
}
printf("%d",query(1));
for(i=2;i<=n;++i)
printf(" %d",query(i));
printf("\n");
}
return 0;
}