題意：輸入一個t，表示有t組測試數(shù)據(jù)；
????????? 接下來一行，輸入兩個數(shù)，k，m，其中k表示這個輛車最多可以坐這么多人,m表示有m次詢問能否上車；
????????? 每一次詢問，輸入兩個數(shù)a,b，表示該乘客能否在a站臺上車，b站臺下車，乘車區(qū)間為（a,b--），先后次序；
????????? 即我每次詢問，你就判斷在a站臺處將會有多少人還在車上，小于k則表示能夠上車，更新數(shù)據(jù)，反之不能上車；
解題思路：這道題很明顯就是線段樹的區(qū)間更新，即判斷線段的重疊次數(shù)。
按照劉汝佳書上寫的代碼WA了，不知道為什么。。。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;const int maxn = 1e6+5;
int add[maxn<<2],Max[maxn<<2],l,r,_max;
int ans[maxn];void maintain(int o,int L,int R)
{int lc = o*2,rc = o*2+1;Max[o] = 0;if(R > L){Max[o] = max(Max[lc],Max[rc]);}Max[o] += add[o];
}void update(int o,int L,int R,int v)
{int lc = o*2, rc = o*2+1;if(l <= L && R <= r){add[o] += v;}else{int M = (L + R) >> 1;if(M >= l) update(lc,L,M,v);if(r > M) update(rc,M+1,R,v);}maintain(o,L,R);
}void query(int o,int L,int R,int addv)
{int lc = o*2, rc = o*2+1;if(l <= L && R <= r){_max = max(_max,Max[o] + addv);}else{int M = (L + R) >> 1;if(l <= M) query(lc,L,M,addv+add[lc]);if(r > M) query(rc,M+1,R,addv+add[rc]);}
}int main()
{int t,cas = 1,len;scanf("%d",&t);while(t--){memset(add,0,sizeof(add));memset(Max,0,sizeof(Max));len = 0;int k,q;scanf("%d%d",&k,&q);for(int i = 1; i <= q; i++){scanf("%d%d",&l,&r);r--;_max = 0;query(1,1,1000000,0);if(_max < k){update(1,1,1000000,1);ans[len++] = i;}}printf("Case %d:\n",cas++);for(int i = 0; i < len; i++)printf("%d ",ans[i]);printf("\n\n");}return 0;
}
看了別人的代碼，采用了一種lazy思想，也就是用一層更新一層，如果我在某一層能夠找到符合要求的區(qū)間，那么就不更新它的子節(jié)點了，等到我需要它的子節(jié)點時，再把子節(jié)點更新了。。。總之是這樣的一種思想，結(jié)合代碼多思考下。。。
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1000005;
int ans[N];
struct node
{int l,r,v,lazy;
}node[N<<2]; // 線段樹的空間大概是數(shù)組空間的4倍；
void build(int l,int r,int numb) // 線段樹的建立；
{node[numb].l=l;node[numb].r=r;node[numb].v=0;node[numb].lazy=0; // 用了lazy思想，提高了效率；if(l==r) return;int mid=(l+r)>>1;build(l,mid,numb<<1);build(mid+1,r,numb<<1|1);
}
void PushUp(int numb) // 往上往父節(jié)點方向更新數(shù)據(jù)；但是這里不是左右兒子的和，而是最大值，因為是站臺人數(shù)；
{node[numb].v=max(node[numb<<1].v,node[numb<<1|1].v);
}
void PushDown(int numb) // 向下往左右兒子方向更新數(shù)據(jù)；
{node[numb<<1].lazy+=node[numb].lazy;node[numb<<1|1].lazy+=node[numb].lazy;node[numb<<1].v+=node[numb].lazy;node[numb<<1|1].v+=node[numb].lazy;node[numb].lazy=0; // 更新完了要清零；
}
void Insert(int l,int r,int numb) // 插入更新數(shù)據(jù)；
{if(node[numb].l>=l&&node[numb].r<=r) // 如果區(qū)間完全重合，則不需要再往下更新了，先保存起來，可以節(jié)約很多的時間（lazy思想）{node[numb].v+=1;node[numb].lazy+=1;return;}if(node[numb].lazy) PushDown(numb); // 因為沒有找到完全重合的區(qū)間，所以要先更新下一層區(qū)間；int mid=(node[numb].r+node[numb].l)>>1;if(l>mid) Insert(l,r,numb<<1|1);else if(r<=mid) Insert(l,r,numb<<1);else{Insert(l,mid,numb<<1);Insert(mid+1,r,numb<<1|1);}PushUp(numb); // 最后還得往上返回，更新父節(jié)點區(qū)間；
}
int query(int l,int r,int numb) // 查詢區(qū)間l到r；
{if(node[numb].l>=l&&node[numb].r<=r){return node[numb].v;}if(node[numb].lazy) PushDown(numb); // 道理同48行；int mid=(node[numb].r+node[numb].l)>>1;if(l>mid) return query(l,r,numb<<1|1);else if(r<=mid) return query(l,r,numb<<1);else{return max(query(l,mid,numb<<1),query(mid+1,r,numb<<1|1)); // 道理同28行；}
}
int main()
{int t,Case=1,len=0,k,m,a,b;scanf("%d",&t);while(t--){len=0;memset(ans,0,sizeof(ans));scanf("%d%d",&k,&m);build(1,1000000,1);for(int i=0;i<m;i++){scanf("%d%d",&a,&b);b--; // 這里有一個問題，就是乘客從a上車，b下車，所以乘客在車上的區(qū)間為（a,b--）;if(query(a,b,1)<k){ // 表示可以上車；ans[len++]=i+1;Insert(a,b,1);}}printf("Case %d:\n",Case++);for(int i=0; i<len; i++) printf("%d ",ans[i]);printf("\n\n");}return 0;
}
與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖
總結(jié)
以上是生活随笔為你收集整理的hdu 3577（线段树区间更新）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
