首页 > 代码库 > 简单线段树中的一系列题目
简单线段树中的一系列题目
1.HDU 1166 http://acm.hdu.edu.cn/showproblem.php?pid=1166
题目大意：
了解地方的兵营人数，每次询问告知区间内的总人数，其中会有兵营人数变更的更新操作
这里要用到求和的query：
int query(int x,int y)
{
int i=D+x-1,j=D+y+1,ans=0;
for(;i^j^1;i>>=1,j>>=1){
if(~i&1) ans+=tree[i^1];
if(j&1) ans+=tree[j^1];
}
return ans;
}
代码如下：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 using namespace std; 6 7 #define N 50005 8 9 int a[N],tree[200010];10 int D;11 string s;12 13 void update(int x)14 {15 for(int i=x;i^1;i>>=1){16 tree[i>>1]=tree[i]+tree[i^1];17 }18 }19 20 int query(int x,int y)21 {22 int i=D+x-1,j=D+y+1,ans=0;23 for(;i^j^1;i>>=1,j>>=1){24 if(~i&1) ans+=tree[i^1];25 if(j&1) ans+=tree[j^1];26 }27 return ans;28 }29 int main()30 {31 int T,n,c,d;32 cin>>T;33 for(int i=1;i<=T;i++){34 D=1;35 memset(tree,0,sizeof(tree));36 scanf("%d",&n);37 for(int j=1;j<=n;j++) scanf("%d",&a[j]);38 while(D<n+2) D<<=1;39 for(int j=1;j<=n;j++) tree[D+j]=a[j];40 for(int j=D-1;j>=1;j--) tree[j]=tree[j<<1]+tree[j<<1|1];41 printf("Case %d:\n",i);42 while(cin>>s){43 if(s=="End") break;44 45 else if(s=="Add"){46 scanf("%d%d",&c,&d);47 tree[D+c]+=d;48 update(D+c);49 }50 else if(s=="Sub"){51 scanf("%d%d",&c,&d);52 tree[D+c]-=d;53 update(D+c);54 }55 else if(s=="Query"){56 scanf("%d%d",&c,&d);57 printf("%d\n",query(c,d));58 }59 }60 }61 return 0;62 }
2.HDU 1754 http://acm.hdu.edu.cn/showproblem.php?pid=1754
题目大意：
老师想要知道某段学生区间的最高分，中间涉及学生成绩的更新操作。
这里用到的是求最大值的query：
int query(int x,int y)
{
int i=D+x-1,j=D+y+1,ans=-1;
for(;i^j^1;i>>=1,j>>=1){
if(~i&1) ans=max(ans,tree[i^1]);
if(j&1) ans=max(ans,tree[j^1]);
}
return ans;
}
总代码如下：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define N 200010int a[N],tree[4*N],D;void init(){ D=1; memset(tree,-1,sizeof(tree));}void treeBuild(){ for(int i=D-1;i>=1;i--) tree[i]=max(tree[i<<1],tree[(i<<1)^1]);}void update(int i){ for(;i^1;i>>=1){ tree[i>>1]=max(tree[i],tree[i^1]); }}int query(int x,int y){ int i=D+x-1,j=D+y+1,ans=-1; for(;i^j^1;i>>=1,j>>=1){ if(~i&1) ans=max(ans,tree[i^1]); if(j&1) ans=max(ans,tree[j^1]); } return ans;}int main(){ int n,m,x,y; char c; while(scanf("%d%d",&n,&m)!=EOF){ init(); while(D<n+2) D<<=1; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); tree[D+i]=a[i]; } treeBuild(); for(int i=1;i<=m;i++) { cin>>c; if(c==‘U‘){ scanf("%d%d",&x,&y); tree[D+x]=y,update(D+x); } else if(c==‘Q‘){ scanf("%d%d",&x,&y); printf("%d\n",query(x,y)); } } } return 0;}
3.HDU 2795 http://acm.hdu.edu.cn/showproblem.php?pid=2795
题目大意：
不断将广告靠上，再靠左贴，问能够贴到的行数
这里我们在线段树上存储的是行的位置，用w[]数组存储每行还能存多少长度的广告
这里虽说高度能达到10^9，但是我们在规划线段树的长度时并不需要那么长，因为n最大为200000，我们规划线段树的底层取到的是min（n,h)；
所以整棵树最大达到4*n即可
这里不断将能够达到最大值的位置放在树顶，
判断时不断往下，因为要贴广告时尽可能朝上，所以如果满足往左走，不满足往右走
query
int query(int k)
{
int t=1;
if(w[tree[t]]<k) return -1; while(t<D){ if(w[tree[t<<1]]>=k) t<<=1;
else t=t<<1|1;
}
return t-D;
}
总代码如下：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define N 200010int w[N],tree[4*N],D,h,m,n,x,Min;void update(int i){ for(;i^1;i>>=1) tree[i>>1]=w[tree[i]]>w[tree[i^1]]?tree[i]:tree[i^1];}int query(int k){ int t=1; if(w[tree[t]]<k) return -1; while(t<D){ if(w[tree[t<<1]]>=k) t<<=1; else t=t<<1|1; } return t-D;}int main(){ while(scanf("%d%d%d",&h,&m,&n)!=EOF){ Min=min(h,n); memset(tree,0,sizeof(tree)); w[0]=0; for(D=1;D<Min+2;D<<=1); for(int i=1;i<=Min;i++) w[i]=m,tree[D+i]=i; for(int i=D-1;i>=1;i--) tree[i]=w[tree[i<<1]]>w[tree[i<<1|1]]?tree[i<<1]:tree[i<<1|1]; for(int i=1;i<=n;i++){ scanf("%d",&x); int t=query(x); printf("%d\n",t); w[t]-=x,update(D+t); } } return 0;}