HDU 1556 Color the ball(线段树区间更新)

Color the ball

我真的该认真的复习一下以前没懂的知识了,今天看了一下线段树,以前只会用模板,现在看懂了之后,发现还有这么多巧妙的地方,好厉害啊 所以就应该尽量搞懂 弄明白每个知识点

【题目链接】Color the ball

【题目类型】线段树区间更新

&题意:

N个气球排成一排,从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了,你能帮他算出每个气球被涂过几次颜色吗?

&题解:

线段树区间更新模板题

【时间复杂度】\(O(nlogn)\)

&代码:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
int N;
int seg[maxn<<2];
int add[maxn<<2]; //在build 和 updata时需要向上更新
//query时不需要
inline void puup(int no)
{
seg[no]+=seg[no<<1]+seg[no<<1|1];
} //这题不需要建树 因为都是0
void build(int no,int b,int e)
{
if (b==e){
seg[no]=0;
return ;
}
int m=b+e>>1;
build(no<<1,b,m);
build(no<<1|1,m+1,e);
puup(no);
} //query 和 updata时都要向下更新
void pudown(int no,int len)
{
if (add[no]){
//注意都是 +=
add[no<<1]+=add[no];
add[no<<1|1]+=add[no];
//这seg节点里存的是与add相乘
seg[no<<1]+=add[no]*(len-len/2);
//左儿子存多的 右儿子存少的 可以自己弄一个奇数区间试一下
seg[no<<1|1]+=add[no]*(len/2);
add[no]=0;
}
} int query(int no,int b,int e,int l,int r)
{
//第一种情况 在[l,r]中间
if (l<=b&&e<=r){
return seg[no];
}
int m=b+e>>1;
pudown(no,e-b+1);
ll re=0;
//第二种情况 在疯狂的两个区间中
if (l<=m)
re+=query(no<<1,b,m,l,r);
if (m<r)
re+=query(no<<1|1,m+1,e,l,r);
return re;
} void updata(int no,int b,int e,int l,int r,int xx)
{
//第一种情况 在[l,r]中间
if (l<=b&&e<=r){
add[no]+=xx;
seg[no]+=e-b+1;
return ;
}
pudown(no,e-b+1);
int m=b+e>>1;
//第二种情况 在疯狂的两个区间中
if (l<=m)
updata(no<<1,b,m,l,r,xx);
if (m<r)
updata(no<<1|1,m+1,e,l,r,xx);
puup(no);
} int main()
{
while(cin>>N){
if (N==0) break;
//别忘初始化
memset(seg,0,sizeof(seg));
memset(add,0,sizeof(add));
// build(1,1,N);
for(int i=0;i<N;i++){
int u,v;
cin>>u>>v;
updata(1,1,N,u,v,1);
}
for(int i=1;i<=N;i++){
printf("%d%c",query(1,1,N,i,i),i==N?'\n':' ');
}
}
return 0;
}
上一篇:Find Median from Data Stream


下一篇:[转]ORACLE分区表的使用和管理