当前位置：首页 > 范文大全 > 实用文>HDU 3911 Black And White（线段树区间合并）

HDU 3911 Black And White（线段树区间合并）

2022-12-28 07:54:45 收藏本文下载本文

“蟹粉酥”通过精心收集，向本站投稿了10篇HDU 3911 Black And White（线段树区间合并），下面是小编给大家整理后的HDU 3911 Black And White（线段树区间合并），欢迎大家借鉴与参考，希望对大家有所帮助。

篇1：HDU 3911 Black And White（线段树区间合并）

Problem DescriptionThere are a bunch of stones on the beach; Stone color is white or black. Little Sheep has a magic brush, she can change the color of a continuous stone, black to white, white to black. Little Sheep like black very much, so she want to know the longest period of consecutive black stones in a range [i, j].

Input There are multiple cases, the first line of each case is an integer n(1<= n<= 10^5), followed by n integer 1 or 0(1 indicates black stone and 0 indicates white stone), then is an integer M(1<=M<=10^5) followed by M operations formatted as x i j(x = 0 or 1) , x=1 means change the color of stones in range[i,j], and x=0 means ask the longest period of consecutive black stones in range[i,j]

OutputWhen x=0 output a number means the longest length of black stones in range [i,j].

Sample Input

41 0 1 050 1 41 2 30 1 41 3 30 4 4

Sample Output

120

线段树区间合并：对于每个区间[l,r]所对应的rs,我们给出6个量:lmax_1:左起的1的最大前缀,lmax_0:左起的0的最大前缀；rmax_1:右起的1的最大后缀rmax_0:右起的0的最大后缀;max_1：区间的1的最大连续值，max_0：区间的0的最大连续值我们的任务就是不断地更新求值，

#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;#define REPF( i , a , b ) for ( int i = a ; i<= b ; ++ i )#define REP( i , n ) for ( int i = 0 ; i< n ; ++ i )#define CLEAR( a , x ) memset ( a , x , sizeof a )typedef long long LL;typedef pairpil;const int mod = 1000000007;const int maxn=1e5+10;int lmax_1[maxn<<2],rmax_1[maxn<<2];int lmax_0[maxn<<2],rmax_0[maxn<<2];int max_1[maxn<<2],max_0[maxn<<2];int col[maxn<<2];int n,m,os;void pushup(int rs,int m){ lmax_1[rs]=lmax_1[rs<<1];//处理左边一类前缀 lmax_0[rs]=lmax_0[rs<<1]; if(lmax_1[rs<<1]==m-(m>>1)) lmax_1[rs]+=lmax_1[rs<<1|1]; if(lmax_0[rs<<1]==m-(m>>1)) lmax_0[rs]+=lmax_0[rs<<1|1]; rmax_1[rs]=rmax_1[rs<<1|1];//处理右边一类后缀 rmax_0[rs]=rmax_0[rs<<1|1]; if(rmax_1[rs<<1|1]==(m>>1)) rmax_1[rs]+=rmax_1[rs<<1]; if(rmax_0[rs<<1|1]==(m>>1)) rmax_0[rs]+=rmax_0[rs<<1]; max_1[rs]=max(max_1[rs<<1],max_1[rs<<1|1]);//处理整个区间的值 max_1[rs]=max(max_1[rs],rmax_1[rs<<1]+lmax_1[rs<<1|1]); max_0[rs]=max(max_0[rs<<1],max_0[rs<<1|1]); max_0[rs]=max(max_0[rs],rmax_0[rs<<1]+lmax_0[rs<<1|1]);}void work(int rs){ swap(lmax_1[rs],lmax_0[rs]); swap(rmax_1[rs],rmax_0[rs]); swap(max_1[rs],max_0[rs]);}void push_down(int rs){ if(col[rs]) { col[rs<<1]^=1;col[rs<<1|1]^=1; col[rs]=0;work(rs<<1);work(rs<<1|1); }}void build(int rs,int l,int r){ col[rs]=0; if(l==r) { scanf(“%d”,&os); if(os==1) {lmax_1[rs]=rmax_1[rs]=max_1[rs]=1;lmax_0[rs]=rmax_0[rs]=max_0[rs]=0; } else {lmax_1[rs]=rmax_1[rs]=max_1[rs]=0;lmax_0[rs]=rmax_0[rs]=max_0[rs]=1; } return ; } int mid=(l+r)>>1; build(rs<<1,l,mid); build(rs<<1|1,mid+1,r); pushup(rs,r-l+1);}void update(int x,int y,int l,int r,int rs){ if(l>=x&&r<=y) { col[rs]^=1; work(rs);//交换值 return ; } push_down(rs); int mid=(l+r)>>1; if(x<=mid) update(x,y,l,mid,rs<<1); if(y>mid) update(x,y,mid+1,r,rs<<1|1); pushup(rs,r-l+1);}int query(int x,int y,int l,int r,int rs){ if(l>=x&&r<=y) return max_1[rs]; push_down(rs); int mid=(l+r)>>1; if(x>mid) return query(x,y,mid+1,r,rs<<1|1); if(y<=mid) return query(x,y,l,mid,rs<<1); int t1=query(x,y,l,mid,rs<<1); int t2=query(x,y,mid+1,r,rs<<1|1); int r1=min(mid-x+1,rmax_1[rs<<1]);//以mid为分割点 int r2=min(y-mid,lmax_1[rs<<1|1]); int res=max(max(t1,t2),r1+r2); return res;}int main{ int op,x,y; while(~scanf(“%d”,&n)) { build(1,1,n); scanf(“%d”,&m); while(m--) { scanf(“%d%d%d”,&op,&x,&y); if(op==1) update(x,y,1,n,1); else printf(“%d\n”,query(x,y,1,n,1)); } } return 0;}

篇2：线段树区间更新 HDU 3911

Black And White

Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 3811 Accepted Submission(s): 1129

OutputWhen x=0 output a number means the longest length of black stones in range [i,j].

Sample Input

41 0 1 050 1 41 2 30 1 41 3 30 4 4

Sample Output

120

Source Multi-University Training Contest 8 - Host by HUST 裸裸的区间更新，注意点已在代码中写出

#include#include#include#include#include#include #includeusing namespace std;#define MAXN 100000 + 1000struct node{ int lsum0,rsum0,msum0,lsum1,rsum1,msum1; int ck; int l,r; int mid(){ return (l+r)>>1; }}tree[MAXN<<2];int a[MAXN];void PushUp(int rt){ int ll = tree[rt<<1].r-tree[rt<<1].l+1;//左子树区间的长度 int rr = tree[rt<<1|1].r-tree[rt<<1|1].l+1;//右子树区间的长度 tree[rt].lsum1 = tree[rt<<1].lsum1; if(tree[rt<<1].lsum1 == ll){ tree[rt].lsum1 = tree[rt].lsum1+tree[rt<<1|1].lsum1; } tree[rt].rsum1 = tree[rt<<1|1].rsum1; if(tree[rt<<1|1].rsum1 == rr){ tree[rt].rsum1 = tree[rt].rsum1+tree[rt<<1].rsum1; } tree[rt].lsum0 = tree[rt<<1].lsum0; if(tree[rt<<1].lsum0 == ll){ tree[rt].lsum0+=tree[rt<<1|1].lsum0; } tree[rt].rsum0 = tree[rt<<1|1].rsum0; if(tree[rt<<1|1].rsum0 == rr){ tree[rt].rsum0+=tree[rt<<1].rsum0; } tree[rt].msum0=max(max(tree[rt<<1].msum0,tree[rt<<1|1].msum0),tree[rt<<1].rsum0+tree[rt<<1|1].lsum0); tree[rt].msum1 = max(max(tree[rt<<1].msum1,tree[rt<<1|1].msum1),tree[rt<<1].rsum1+tree[rt<<1|1].lsum1);}void PushDown(int rt){ if(tree[rt].ck == 1){ tree[rt<<1].ck ^= 1;//现在左子树父亲节点的所有01都需要交换，所以左子树也是需要交换，那么左子树的左右子树也是需要交换，如果原来左子树就要交换 tree[rt<<1|1].ck ^= 1;//，那么交换了两次就相当于不需要交换，这样异或之后就可以不需要交换 tree[rt].ck = 0; swap(tree[rt<<1].lsum0,tree[rt<<1].lsum1); swap(tree[rt<<1].rsum0,tree[rt<<1].rsum1); swap(tree[rt<<1].msum0,tree[rt<<1].msum1); swap(tree[rt<<1|1].lsum0,tree[rt<<1|1].lsum1); swap(tree[rt<<1|1].rsum0,tree[rt<<1|1].rsum1); swap(tree[rt<<1|1].msum0,tree[rt<<1|1].msum1); }}void build(int l,int r,int rt){ tree[rt].l = l; tree[rt].r = r; tree[rt].ck = 0;//开始的时候都不转换 if(l == r){ if(a[l] == 0){tree[rt].lsum0=tree[rt].rsum0=tree[rt].msum0=1;tree[rt].lsum1=tree[rt].rsum1=tree[rt].msum1=0; } else{tree[rt].lsum1=tree[rt].rsum1=tree[rt].msum1=1;tree[rt].lsum0=tree[rt].rsum0=tree[rt].msum0=0; } return ; } //int m = (l+r)>>1; int m = tree[rt].mid(); build(l,m,rt<<1); build(m+1,r,rt<<1|1); PushUp(rt);}void update(int l,int r,int rt){ if(l<=tree[rt].l && tree[rt].r<=r){ tree[rt].ck ^= 1; swap(tree[rt].lsum0,tree[rt].lsum1); swap(tree[rt].rsum0,tree[rt].rsum1); swap(tree[rt].msum0,tree[rt].msum1); return ; } PushDown(rt); int m = tree[rt].mid(); if(r<= m){ update(l,r,rt<<1); } else if(l >m){ update(l,r,rt<<1|1); } else{ update(l,m,rt<<1); update(m+1,r,rt<<1|1); } PushUp(rt);}int query(int l,int r,int rt){ if(l<=tree[rt].l && tree[rt].r<=r){ return tree[rt].msum1; } PushDown(rt); int m = tree[rt].mid(); if(r<= m){ return query(l,r,rt<<1); } else if(l >m){ return query(l,r,rt<<1|1); } else{ int lr = query(l,m,rt<<1); int rr = query(m+1,r,rt<<1|1); int a = tree[rt<<1].rsum1;//左子树最长的连续的1 if(a >tree[rt<<1].r-l+1){//后面的那个是最大范围a = tree[rt<<1].r-l+1; } int b = tree[rt<<1|1].lsum1; if(b >r-tree[rt<<1|1].l+1){b = r-tree[rt<<1|1].l+1; } return max(max(lr,rr),a+b); }}int main(){ int i; int n,m,op,aa,b; while(~scanf(“%d”,&n)){ for(i=1;i<=n;i++){scanf(“%d”,&a[i]); } build(1,n,1); scanf(“%d”,&m); while(m--){scanf(“%d%d%d”,&op,&aa,&b);if(op == 0){ int ans = query(aa,b,1); printf(“%d\n”,ans);}else{ update(aa,b,1);} } } return 0;}

篇3：HDU 1754 I Hate It （线段树区间最值）

I Hate It

Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 43296 Accepted Submission(s): 17071

Problem Description 很多学校流行一种比较的习惯，老师们很喜欢询问，从某某到某某当中，分数最高的是多少。

这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

Input 本题目包含多组测试，请处理到文件结束。

在每个测试的第一行，有两个正整数 N 和 M ( 0<=00,0<5000 br=“”>学生ID编号分别从1编到N。

第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。

接下来有M行。每一行有一个字符 C (只取'Q'或'U') ，和两个正整数A，B。

当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。

当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。

Output 对于每一次询问操作，在一行里面输出最高成绩。

Sample Input

5 61 2 3 4 5Q 1 5U 3 6Q 3 4Q 4 5U 2 9Q 1 5

Sample Output

5659HintHuge input,the C function scanf will work better than cin

Author linle

Source 省赛集训队练习赛（6）_linle专场

这会儿在看线段树，做个题试试

线段树功能:update:单点替换 query:区间最值

AC代码：

#include#include#include using namespace std;const int maxn = 200005;int MAX[maxn<<2];void pushup(int rt) { MAX[rt] = max(MAX[rt << 1], MAX[rt << 1 | 1]);}void build(int l, int r, int rt) { if(l == r) { scanf(“%d”, &MAX[rt]); return ; } int m = (l + r) >>1; build(l, m, rt << 1); build(m + 1, r, rt << 1 | 1); pushup(rt);}void update(int p, int sc, int l, int r, int rt) { if(l == r) { MAX[rt] = sc; return; } int m = (l + r) >>1; if(p <= m) update(p, sc, l, m, rt << 1); else update(p, sc, m + 1, r, rt << 1 | 1); pushup(rt);}int query(int L, int R, int l, int r, int rt) { if(L <= l && r <= R) { return MAX[rt]; } int m = (l + r) >>1; int ret = 0; if(L <= m) ret = max(ret, query(L, R, l, m, rt << 1)); if(R >m) ret = max(ret, query(L, R, m + 1, r, rt << 1 | 1)); return ret;}int main() { int n, m; while(scanf(“%d %d”, &n, &m) != EOF) { build(1, n, 1); while(m--) { char ord[5]; int a, b; scanf(“%s %d %d”, ord, &a, &b); if(ord[0] == 'Q') printf(“%d\n”, query(a, b, 1, n, 1)); else update(a, b, 1, n, 1); } } return 0;}<=200000,0<5000>

篇4：线段树单点更新查询区间最大值 hdu 2795 Billboar

题意：

有一块h*w（1<=h,w<=10^9）的公告牌，需要在上面放n(n<=200000)个1*w[i]的公告，每个公告优先选可以放置的地方中最上的那行，同一行选最左的地方，依次输出每个公告放置在哪行，如果不能放置，输出-1，

可以把公告牌看作长为h的线段，构建一个线段树，每个节点存储区间的最大值，初始最大值为公告牌的宽度w。如果某区间的最大值大于当前公告的宽度，就可以放在该区间，由于公告优先放在上面，所以选区间的时候也应该先判断左边的区间可不可以，当在某个点放上公告后，该点的最大值应减去该公告的宽度。如果整个区间的最大值小于当前公告的宽度，就说明不能放置。

代码：

#include#include#include#include#include#include#include #include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;#define PB push_back#define MP make_pair#define REP(i,x,n) for(int i=x;i<(n);++i)#define FOR(i,l,h) for(int i=(l);i<=(h);++i)#define FORD(i,h,l) for(int i=(h);i>=(l);--i)#define SZ(X) ((int)(X).size())#define ALL(X) (X).begin(), (X).end()#define RI(X) scanf(“%d”, &(X))#define RII(X, Y) scanf(“%d%d”, &(X), &(Y))#define RIII(X, Y, Z) scanf(“%d%d%d”, &(X), &(Y), &(Z))#define DRI(X) int (X); scanf(“%d”, &X)#define DRII(X, Y) int X, Y; scanf(“%d%d”, &X, &Y)#define DRIII(X, Y, Z) int X, Y, Z; scanf(“%d%d%d”, &X, &Y, &Z)#define OI(X) printf(“%d”,X);#define RS(X) scanf(“%s”, (X))#define MS0(X) memset((X), 0, sizeof((X)))#define MS1(X) memset((X), -1, sizeof((X)))#define LEN(X) strlen(X)#define F first#define S second#define Swap(a, b) (a ^= b, b ^= a, a ^= b)#define Dpoint strcut node{int x,y}#define cmpd int cmp(const int &a,const int &b){return a>b;} /*#ifdef HOME freopen(“in.txt”,“r”,stdin); #endif*/const int MOD = 1e9+7;typedef vectorVI;typedef vectorVS;typedef vectorVD;typedef long long LL;typedef pairPII;//#define HOMEint Scan(){ int res = 0, ch, flag = 0; if((ch = getchar()) == '-') //判断正负 flag = 1; else if(ch >= '0' && ch <= '9') //得到完整的数 res = ch - '0'; while((ch = getchar()) >= '0' && ch <= '9' ) res = res * 10 + ch - '0'; return flag ? -res : res;}/*----------------PLEASE-----DO-----NOT-----HACK-----ME--------------------*/int h,w,n;int Max[800000+10];void pushup(int rt){ Max[rt]=max(Max[rt<<1],Max[(rt<<1)+1]);}void build(int l,int r,int rt){Max[rt]=w;if(l==r) return;int m=(l+r)>>1;build(l,m,rt<<1);build(m+1,r,(rt<<1)+1);}int query(int l,int r,int rt,int w){if(l==r){ Max[rt]-=w; return l;}int m=(l+r)>>1;int ans;if(Max[rt<<1]>=w) ans=query(l,m,rt<<1,w);else ans=query(m+1,r,(rt<<1)+1,w); pushup(rt); return ans;}int main(){ while(RIII(h,w,n)!=EOF){if(h>n)h=n; build(1,h,1);for(int i=0;i

篇5：树状数组和线段树

一、树状数组

在解题过程中，我们有时需要维护一个数组的前缀和 S[i]=A[1]+A[2]+...+A[i] ，但是不难发现，如果我们修改了任意一个 A[i],S[i] 、S[i+1]...S[n] 都会发生变化。可以说，每次修改 A[i] 后，调整前缀和 S[] 在最坏情况下会需要 O(n) 的时间。当 n 非常大时，程序会运行得非常缓慢。因此，这里我们引入“树状数组”，它的修改与求和都是 O(logn) 的，效率非常高。

实现：

对于正整数x，定义lowbit（x）为x的二进制表达式中最右边的1所对应的值。

Lowbit(x)=x and -x对于节点i，如果它是左子节点，其父节点为i+lowbit(i)；

构造一个辅助数组C，其中Ci=Ai-lowbit(i)+1+Ai-lowbit(i)+2+…+Ai即C的每个元素都是A数组中的一段连续和。具体是每个灰色节点i都属于一个以它自身结尾的水平长条，这个长条中的数之和就是Ci。如C12=A9+A10+A11+A12=C10+A11+A12

如何更新C数组中的元素：如果修改了一个Ai，需要更新C数组中的哪些元素呢？从Ci开始往右走，边走边“往上爬”（不一定沿着树中的边爬），沿途修改所有结点对应的Ci即可。预处理时先把C数组清空，然后执行n次add操作。总时间为O（nlogn）

如何计算前缀和Si：顺着结点i往左走，边走边“往上爬”（不一定沿着树中的边爬），把沿途经过的Ci累加起来就可以了。对于query（L,R）=SR-SL-1。

代码：

var

b,c,f:array [0..100000] of longint;

ff,a:Array [0..100000] of boolean;

i,j,m,n,x,y,ans,l,r,tmp:longint;

s:string;

function dfs(x:longint):longint;

begin

if x<=1 then

exit;

c[f[x]]:=c[f[x]]+c[x];

dfs(f[x]);

end;

procedure dfs1(x:longint);

begin

dec(c[x]);

if x<=1 then

exit;

dfs1(f[x]);

end;

procedure dfs2(x:longint);

begin

inc(c[x]);

if x<=1 then

exit;

dfs2(f[x]);

end;

begin

readln(n);

fillchar(ff,sizeof(ff),true);

for i:=1 to n-1 do

begin

readln(x,y);

f[y]:=x;

inc(b[x]);

end;

for i:=1 to n do

c[i]:=1;

for i:=1 to n do

begin

if b[i]=0 then

dfs(i);

end;

readln(m);

for i:=1 to m do

begin

x:=0;

readln(s);

if s[1]='Q' then

begin

for j:=3 to length(s) do

x:=x*10+ord(s[j])-ord('0');

writeln(c[x]);

end;

if s[1]='C' then

begin

for j:=3 to length(s) do

x:=x*10+ord(s[j])-ord('0');

if ff[x] then

dfs1(x) else

dfs2(x);

ff[x]:=not ff[x];

end;

End.

二、线段树

1,.线段树的结构:

区间：用一对数a和b表示一个前闭后开的区间[a,b)。（可以自己修改）结点T(a,b)：表示该结点维护了原数列中区间[a,b)的信息，其中a和b为整数且a1，那么T(a,(a+b)/2)为T(a,b)的左孩子结点，T((a+b)/2,b)为T(a,b)的右孩子

叶结点：如果对于结点T(a,b)，有b-a=1，那么该结点就是叶结点线段树结构是递归定义的。

2.线段树的性质:

结点数：假设该线段树处理的数列长度为n，即根结点的区间为[1,n+1)，那么总结点个数不超过2*n个。深度：线段树可以近似看做一棵满二叉树，所以深度不超过log（2*n）线段分解数量级：线段树把区间上的任意一条长度为L的线段都分成了不超过2logL条线段，这使得大多数查询能够在O（logn）的时间内解决。

线段树的存储：

1、链表存储

2、数组模拟链表

3、堆结构存储

应用：

忠诚（loyal）

【问题描述】

老管家是一个聪明能干的人，

他为财主工作了整整，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。

在询问过程中账本的内容可能会被修改

【输入格式】

输入中第一行有两个数m,n表示有m(m<=100000)笔账,n表示有n个问题，n<=100000。

接下来每行为3个数字，第一个p为数字1或数字2，第二个数为x，第三个数为y

当p=1 则查询x,y区间

当p=2 则改变第x个数为y

【输出格式】

输出文件中为每个问题的答案。具体查看样例。

【输入样例】

10 3

1 2 3 4 5 6 7 8 9 10

1 2 7

2 2 0

1 1 10

【输出样例】

2 0

代码：

type

point=^node;

node=record

left,right:longint;

lp,rp:point;

sum:longint;

end;

var

p:array [1..100000] of node;

i,j,m,n,x,y,k:longint;

a:array [1..100000] of longint;

root:point;

procedure creat(p:point;l,r:longint);

begin

p^.left:=l; p^.right:=r; p^.sum:=maxlongint;

if l+1=r then

begin

p^.lp:=nil;

p^.rp:=nil;

end

else

begin

new(p^.lp); creat(p^.lp,l,(l+r) div 2);

new(p^.rp); creat(p^.rp,(l+r) div 2,r);

end;

function min(x,y:longint):longint;

begin

if x

exit(x);

exit(y);

end;

procedure update(p:point;x,delta:longint);

begin

if p^.left+1=p^.right then

begin

p^.sum:=delta;

end

else

begin

if x<(p^.left+p^.right) div 2 then

update(p^.lp,x,delta);

if x>=(p^.left+p^.right) div 2 then

update(p^.rp,x,delta);

p^.sum:=min(p^.lp^.sum,p^.rp^.sum);

end;

function query(p:point;l,r:longint):longint;

var

ans:longint;

begin

if (l<=p^.left) and (p^.right<=r) then

exit(p^.sum);

ans:=maxlongint;

if l<(p^.left+p^.right) div 2 then

ans:=min(ans,query(p^.lp,l,r));

if r>(p^.left+p^.right) div 2 then

ans:=min(ans,query(p^.rp,l,r));

exit(ans);

end;

begin

readln(n,m);

for i:=1 to n do

read(a[i]);

new(root);

creat(root,1,n+1);

for i:=1 to n do

update(root,i,a[i]);

for i:=1 to m do

begin

readln(k,x,y);

if k=2 then

update(root,x,y);

if k=1 then

write(query(root,x,y+1),' ');

end;

writeln;

End.

篇6：nyist 737 区间DP石子合并 dfs

#include

using namespace std;

#define inf 233333333

int n,a[205],sum[205];

int dp[205][205];

int dfs(int i, int j){ //返回合并[i,j]的最小值

if(dp[i][j] < inf)return dp[i][j];

if( i >= j) return dp[i][j] = 0;

if(i+1 == j) return dp[i][j] = a[i] + a[j];

for(int p=i; p<=n;i++)scanf(%d,&a[i]);“ int=”pre=“ return=”“>

篇7：HDOJ 题目1754 I Hate It（线段树单点更新，求区间最大值）

I Hate It

Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 44713 Accepted Submission(s): 17548

Problem Description 很多学校流行一种比较的习惯，老师们很喜欢询问，从某某到某某当中，分数最高的是多少。

这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

Input 本题目包含多组测试，请处理到文件结束。

在每个测试的第一行，有两个正整数 N 和 M ( 0<=00,0<5000 br=”“>学生ID编号分别从1编到N。

第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。

接下来有M行。每一行有一个字符 C (只取'Q'或'U') ，和两个正整数A，B。

当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。

当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。

Output 对于每一次询问操作，在一行里面输出最高成绩。

Sample Input

5 61 2 3 4 5Q 1 5U 3 6Q 3 4Q 4 5U 2 9Q 1 5

Sample Output

5659HintHuge input,the C function scanf will work better than cin

Author linle

Source 省赛集训队练习赛（6）_linle专场

Recommend lcy | We have carefully selected several similar problems for you: 1698 1542 2795 1540 1255 为毛函数调用比宏定义还快，写成宏定义就超时，写成函数就过了 ac代码

#include#include//#define max(a,b) (a>b?a:b)int node[200020<<2];int max(int a,int b){ if(a>b) return a; return b;}void pushup(int tr){ node[tr]=max(node[tr<<1],node[tr<<1|1]);}void build_tr(int l,int r,int tr){ if(l==r) { scanf(”%d“,&node[tr]); return; } int mid=(l+r)>>1; build_tr(l,mid,tr<<1); build_tr(mid+1,r,tr<<1|1); pushup(tr);}void update(int num,int add,int l,int r,int tr){ if(l==r) { node[tr]=add; return; } int mid=(l+r)>>1; if(num>mid) update(num,add,mid+1,r,tr<<1|1); else update(num,add,l,mid,tr<<1); pushup(tr);}int query(int x,int y,int l,int r,int tr){ int ans=0; if(x<=l&&y>=r) return node[tr]; int mid=(l+r)>>1; if(x<=mid) ans=max(ans,query(x,y,l,mid,tr<<1)); if(y>mid) ans=max(ans,query(x,y,mid+1,r,tr<<1|1)); return ans;}int main(){ int n,m; while(scanf(”%d%d“,&n,&m)!=EOF) { build_tr(1,n,1); char s[2]; int a,b; while(m--) { scanf(”%s%d%d“,s,&a,&b); if(s[0]=='U') { update(a,b,1,n,1); } else printf(”%d\n“,query(a,b,1,n,1)); } }}

<=200000,0<5000>

篇8：hdu1754 I hate it （线段树）

I Hate It

Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 55291 Accepted Submission(s): 21599

Problem Description 很多学校流行一种比较的习惯，老师们很喜欢询问，从某某到某某当中，分数最高的是多少。

这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

Input 本题目包含多组测试，请处理到文件结束。

在每个测试的第一行，有两个正整数 N 和 M ( 0<=200000,0<5000 br=”“>学生ID编号分别从1编到N。

第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。

接下来有M行。每一行有一个字符 C (只取'Q'或'U') ，和两个正整数A，B。

当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。

当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。

Output 对于每一次询问操作，在一行里面输出最高成绩。

Sample Input

5 61 2 3 4 5Q 1 5U 3 6Q 3 4Q 4 5U 2 9Q 1 5

Sample Output

5659HintHuge input,the C function scanf() will work better than cin

Author linle

分析：线段树入门基础题，每次更新结点存储该以结点为根的子树中最大值。

#include#include#include#include#include#include#include#include#include#include using namespace std;const double eps = 1e-6;const double pi = acos(-1.0);const int INF = 0x3f3f3f3f;const int MOD = 1000000007;#define ll long long#define CL(a,b) memset(a,b,sizeof(a))#define MAXN 800010struct node{ int a,b,r;}t[MAXN];int n,m,ans;void build(int x, int y, int num){ t[num].a = x; t[num].b = y; t[num].r = 0; if(x == y) return ; int mid = (x+y)/2; build(x, mid, num*2); build(mid+1, y, num*2+1);}void update(int x, int y, int num){ if (t[num].a == t[num].b && t[num].b == x) { t[num].r = y; return ; } int mid = (t[num].a+t[num].b)/2; if(x >mid) update(x, y, num*2+1); else update(x, y, num*2); t[num].r = max(t[num*2].r, t[num*2+1].r);}void query(int x, int y, int num){ if(t[num].a == x && t[num].b == y) { ans = max(ans, t[num].r); return ; } int mid = (t[num].a+t[num].b)/2; if(x >= mid+1) query(x, y, num*2+1); else if(y <= mid) query(x, y, num*2); else { query(x, mid, num*2); query(mid+1, y, num*2+1); }}int main(){ char ch; int x,y,k; while(scanf(”%d%d“,&n,&m)==2) { build(1, n, 1); for(int i=1; i<=n; i++) {scanf(”%d“,&k);update(i, k, 1); } while(m--) {getchar();scanf(”%c%d%d“,&ch,&x,&y);if(ch == 'U'){ update(x, y, 1);}else if(ch == 'Q'){ ans = -99999; query(x, y, 1); printf(”%d\n“,ans);} } } return 0;}

<=200000,0<5000>

篇9：HDU 2795 Billboard（简单线段树）

Billboard

Time Limit: 0/8000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 12812 Accepted Submission(s): 5578

Problem Description At the entrance to the university, there is a huge rectangular billboard of size h*w (h is its height and w is its width). The board is the place where all possible announcements are posted: nearest programming competitions, changes in the dining room menu, and other important information.

On September 1, the billboard was empty. One by one, the announcements started being put on the billboard.

Each announcement is a stripe of paper of unit height. More specifically, the i-th announcement is a rectangle of size 1 * wi.

When someone puts a new announcement on the billboard, she would always choose the topmost possible position for the announcement. Among all possible topmost positions she would always choose the leftmost one.

If there is no valid location for a new announcement, it is not put on the billboard (that's why some programming contests have no participants from this university).

Given the sizes of the billboard and the announcements, your task is to find the numbers of rows in which the announcements are placed.

Input There are multiple cases (no more than 40 cases).

The first line of the input file contains three integer numbers, h, w, and n (1 <= h,w <= 10^9; 1 <= n <= 200,000) - the dimensions of the billboard and the number of announcements.

Each of the next n lines contains an integer number wi (1 <= wi <= 10^9) - the width of i-th announcement.

Output For each announcement (in the order they are given in the input file) output one number - the number of the row in which this announcement is placed. Rows are numbered from 1 to h, starting with the top row. If an announcement can't be put on the billboard, output ”-1“ for this announcement.

Sample Input

3 5 524333

Sample Output

1213-1

Author hhanger@zju

Source HDOJ Summer Exercise（5）

Recommend lcy | We have carefully selected several similar problems for you: 1698 1542 1828 1540 2871

题意：有一个h*w的木板，要在上面贴广告，有一个要求就是尽可能的贴在上面，如果不能就尽可能的贴在左面，（这样可以使得贴的广告数目最多吧），每个广告都是1*wi，这就说明每一个广告只能占据一行，可以使用线段树进行维护，每次都进行比较，如果最上面剩下的宽度大于或等于广告的宽就减去广告在木板该行的宽度，

HDU 2795 Billboard（简单线段树）

，

如果能想起来这种方法就很简单，如果想不出来都不知道怎么做...

#include#include#include#include#include#include#includeusing namespace std;const int maxn = 200001;struct node{ int l; int r; int cnt;}q[maxn<<4];int h,w,n;void build(int l,int r,int rt){ q[rt].l = l; q[rt].r = r; q[rt].cnt = 0; if(q[rt].l == q[rt].r) { q[rt].cnt = w; return ; } int mid = (l+r)>>1; build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); q[rt].cnt = max(q[rt<<1].cnt,q[rt<<1|1].cnt);}int qurry(int k,int l,int r,int rt){ if(q[rt].l == q[rt].r) { q[rt].cnt -= k; return q[rt].l; } int mid = (l+r)>>1; int ans = 0; if(q[rt<<1].cnt>=k) { ans = qurry(k,l,mid,rt<<1); } else { ans = qurry(k,mid+1,r,rt<<1|1); } q[rt].cnt = max(q[rt<<1].cnt,q[rt<<1|1].cnt); return ans;}int main{ while(scanf(”%d%d%d“,&h,&w,&n)!=EOF) { if(h>n) {h = n; } build(1,h,1); while(n--) {int m;scanf(”%d“,&m);if(m>q[1].cnt){ printf(”-1\n“);}else{ int ans = qurry(m,1,h,1); printf(”%d\n“,ans);} } } return 0;}

篇10：hdu1166 敌兵布阵（线段树）

敌兵布阵

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 64143 Accepted Submission(s): 27036

Problem Description C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了，A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手,但这些都逃不过C国的监视。

中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动，而Derek每次询问的段都不一样，所以Tidy不得不每次都一个一个营地的去数，很快就精疲力尽了，Derek对Tidy的计算速度越来越不满:”你个死肥仔，算得这么慢，我炒你鱿鱼!”Tidy想：“你自己来算算看，这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下，Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说：“死肥仔，叫你平时做多点acm题和看多点算法书，现在尝到苦果了吧!”Tidy说：“我知错了。。。”但Windbreaker已经挂掉电话了。Tidy很苦恼，这么算他真的会崩溃的，聪明的读者，你能写个程序帮他完成这项工作吗？不过如果你的程序效率不够高的话，Tidy还是会受到Derek的责骂的.

Input 第一行一个整数T，表示有T组数据。

每组数据第一行一个正整数N（N<=50000）,表示敌人有N个工兵营地，接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人（1<=ai<=50）。

接下来每行有一条命令，命令有4种形式：

(1) Add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30）

(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人（j不超过30）;

(3)Query i j ,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数;

(4)End 表示结束，这条命令在每组数据最后出现;

每组数据最多有40000条命令

Output 对第i组数据,首先输出“Case i:”和回车,

对于每个Query询问，输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。

Sample Input

1101 2 3 4 5 6 7 8 9 10Query 1 3Add 3 6Query 2 7Sub 10 2Add 6 3Query 3 10End

Sample Output

Case 1:63359

Author Windbreaker

分析：最基础的线段树入门题，属于模板题，每次更新节点就行了。

#include#include#include#include#include#include#include#include#include#include using namespace std;const double eps = 1e-6;const double pi = acos(-1.0);const int INF = 0x3f3f3f3f;const int MOD = 1000000007;#define ll long long#define CL(a,b) memset(a,b,sizeof(a))#define MAXN 100010struct node{ int a,b,sum;}t[400010];int ans, r[500010];void build(int x, int y, int num){ t[num].a = x; t[num].b = y; if(x == y) t[num].sum = r[y]; else { int mid = (x+y)/2; build(x, mid, num*2); build(mid+1, y, num*2+1); t[num].sum = t[num*2].sum + t[num*2+1].sum; }}void add(int x, int y, int num){ if(t[num].a == x && t[num].b == x) { t[num].sum += y; return ; } int mid = (t[num].a+t[num].b)/2; if(x >mid) add(x, y, num*2+1); else add(x, y, num*2); t[num].sum = t[num*2].sum + t[num*2+1].sum;}void sub(int x, int y, int num){ if(t[num].a == x && t[num].b == x) { t[num].sum -= y; return ; } int mid = (t[num].a+t[num].b)/2; if(x >mid) sub(x, y, num*2+1); else sub(x, y, num*2); t[num].sum = t[num*2].sum + t[num*2+1].sum;}void query(int x, int y, int num){ if(t[num].a == x && t[num].b == y) { ans += t[num].sum; return ; } int mid = (t[num].a+t[num].b)/2; if(y <= mid) query(x, y, num*2); else if(x >= mid+1) query(x, y, num*2+1); else { query(x, mid, num*2); query(mid+1, y, num*2+1); }}int main(){ int T,n; char str[6]; scanf(“%d”,&T); for(int cas=1; cas<=T; cas++) { int x,y; scanf(“%d”,&n); r[0] = 0; for(int i=1; i<=n; i++)scanf(“%d”,&r[i]); build(1, n, 1); printf(“Case %d:\n”,cas); while(scanf(“%s”,str)==1) {//scanf(“%d%d”,&x,&y);if(strcmp(str, “End”)==0) break;else if(strcmp(str, “Add”)==0){ scanf(“%d%d”,&x,&y); add(x, y, 1);}else if(strcmp(str, “Sub”)==0){ scanf(“%d%d”,&x,&y); sub(x, y, 1);}else if(strcmp(str, “Query”)==0){ scanf(“%d%d”,&x,&y); ans = 0; query(x, y, 1); printf(“%d\n”,ans);} } } return 0;}

【HDU 3911 Black And White（线段树区间合并）】相关文章：

1.Codefoeces 387E George and Cards 贪心+线段树