首页 > 代码库 > 线段树专题
线段树专题
①POJ3667
题目链接:http://poj.org/problem?id=3667
思路:pushup为合并,向上更新。pushdown为向下更新,lazy存放待更新的操作,1为置满,0为无操作,-1为置空。
#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; const int N = 5e4 + 5; struct node { int l,r,lazy,ls,rs,ms; }tree[N<<2]; void pushup(int i) { int mid = (tree[i].l + tree[i].r) >> 1; if(tree[i*2].ls == mid - tree[i].l + 1) tree[i].ls = tree[i*2].ls + tree[i*2 + 1].ls; else tree[i].ls = tree[i*2].ls; if(tree[i*2 + 1].rs == tree[i].r - mid) tree[i].rs = tree[i*2 + 1].rs + tree[i*2].rs; else tree[i].rs = tree[i*2 + 1].rs; tree[i].ms = max(max(tree[i*2].ms,tree[i*2 + 1].ms),tree[i*2].rs + tree[i*2 + 1].ls); } void pushdown(int i) { if(tree[i].lazy) { tree[i*2].lazy = tree[i*2 + 1].lazy = tree[i].lazy; if(tree[i].lazy == 1) { tree[i*2].ls = tree[i*2].rs = tree[i*2].ms = 0; tree[i*2 + 1].ls = tree[i*2 + 1].rs = tree[i*2 + 1].ms = 0; } else { tree[i*2].ls = tree[i*2].rs = tree[i*2].ms = tree[i*2].r - tree[i*2].l + 1; tree[i*2 + 1].ls = tree[i*2 + 1].rs = tree[i*2 + 1].ms = tree[i*2 + 1].r - tree[i*2 + 1].l + 1; } tree[i].lazy = 0; } } void built(int i,int l,int r) { tree[i].l = l; tree[i].r = r; tree[i].lazy = 0; tree[i].ls = tree[i].rs = tree[i].ms = r - l + 1; if(l == r) return; int mid = (l + r) >> 1; built(i*2,l,mid); built(i*2 + 1,mid + 1,r); } void update(int i,int l,int r,int c) { if(tree[i].l >= l && tree[i].r <= r) { tree[i].lazy = c; if(c == 1) tree[i].ls = tree[i].rs = tree[i].ms = 0; else tree[i].ls = tree[i].rs = tree[i].ms = tree[i].r - tree[i].l + 1; return; } if(tree[i].r < l || tree[i].l > r) return; pushdown(i); update(i*2,l,r,c); update(i*2 + 1,l,r,c); pushup(i); } int query(int i,int len) { pushdown(i); if(tree[i].ls >= len) return tree[i].l; if(tree[i*2].ms >= len) return query(i*2,len); if(tree[i*2].rs + tree[i*2 + 1].ls >= len) { int mid = (tree[i].l + tree[i].r) >> 1; return mid - tree[i*2].rs + 1; } return query(i*2 + 1,len); } int main() { int n,m; while(~scanf("%d %d",&n,&m)) { built(1,1,n); while(m--) { int c; scanf("%d",&c); if(c == 1) { int x; scanf("%d",&x); if(tree[1].ms < x) { puts("0"); continue; } int ans = query(1,x); printf("%d\n",ans); update(1,ans,ans + x - 1,1); } else { int x,y; scanf("%d %d",&x,&y); update(1,x,x + y - 1,-1); } } } return 0; }
②POJ3225
题目链接:http://poj.org/problem?id=3225
#include<cstdio> #define le(i) i<<1 #define ri(i) i<<1|1 using namespace std; const int N = 65535 << 1; struct node { int l,r,lazy,cov;//lazy表示操作:2为互换,1为置满,0为置空,-1为无操作。cov表示状态:1为全包含,0为全不包含,-1为其它 }tree[(N<<2)+5]; int s[(N<<1)+5]; void pushup(int i) { if(tree[le(i)].cov == tree[ri(i)].cov) tree[i].cov = tree[le(i)].cov; else tree[i].cov = -1; } void pushdown(int i) { if(tree[i].lazy != -1) { if(tree[le(i)].lazy != -1 && tree[i].lazy == 2) { if(tree[le(i)].lazy == 2) tree[le(i)].lazy = -1; else tree[le(i)].lazy ^= 1; } else tree[le(i)].lazy = tree[i].lazy; if(tree[ri(i)].lazy != -1 && tree[i].lazy == 2) { if(tree[ri(i)].lazy == 2) tree[ri(i)].lazy = -1; else tree[ri(i)].lazy ^= 1; } else tree[ri(i)].lazy = tree[i].lazy; if(tree[i].lazy == 2) { if(tree[le(i)].cov != -1) tree[le(i)].cov ^= 1; if(tree[ri(i)].cov != -1) tree[ri(i)].cov ^= 1; } else tree[le(i)].cov = tree[ri(i)].cov = tree[i].lazy; tree[i].lazy = -1; } } void built(int i,int l,int r) { tree[i].l = l; tree[i].r = r; tree[i].lazy = -1; tree[i].cov = 0; if(l == r) return; int mid = (l + r) >> 1; built(le(i),l,mid); built(ri(i),mid + 1,r); } void update(int i,int l,int r,int op)//op:0为置空,1为置满,2为互换 { if(r < l) return; if(tree[i].l >= l && tree[i].r <= r) { if(tree[i].lazy != -1 && op == 2) { if(tree[i].lazy == 2) tree[i].lazy = -1; else tree[i].lazy ^= 1; } else tree[i].lazy = op; if(op == 2) { if(tree[i].cov != -1) tree[i].cov ^= 1; } else tree[i].cov = op; return; } if(tree[i].l > r|| tree[i].r < l) return; pushdown(i); update(le(i),l,r,op); update(ri(i),l,r,op); pushup(i); } void query(int i) { if(!tree[i].cov) return; if(tree[i].cov == 1) { for(int k = tree[i].l; k <= tree[i].r; k++) s[k] = 1; return; } else { pushdown(i); query(le(i)); query(ri(i)); } } int main() { char c,l0,r0; int l,r; built(1,0,N); while(scanf(" %c %c%d,%d %c",&c,&l0,&l,&r,&r0) != EOF) { if(l0 == ‘(‘) l = l<<1|1; else l <<= 1; if(r0 == ‘)‘) r = (r<<1) - 1; else r <<= 1; if(c == ‘U‘) update(1,l,r,1); else if(c == ‘I‘) { update(1,0,l-1,0); update(1,r+1,N,0); } else if(c == ‘D‘) update(1,l,r,0); else if(c == ‘C‘) { update(1,0,l-1,0); update(1,r+1,N,0); update(1,l,r,2); } else update(1,l,r,2); } query(1); int a = -1,flag = 0; for(int i = 0; i <= N + 1; i++) { if(s[i] && a == -1) a = i,flag = 1; if(!s[i] && a != -1) { if(a&1) printf("(%d,",a>>1); else printf("[%d,",a>>1); if(i&1) printf("%d] ",i>>1); else printf("%d) ",i>>1); a = -1; } } if(!flag) printf("empty set"); printf("\n"); return 0; }
③POJ5023
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5023
由于颜色只有30种,所以可以用位存储,网上看到的好神奇,我却只能想到set
#include<bits/stdc++.h> #define le i<<1 #define ri i<<1|1 using namespace std; const int N = 1e6 + 5; int ans; struct node { int l,r,lazy,color; }tree[N<<2]; void pushup(int i) { tree[i].color = tree[le].color | tree[ri].color; } void pushdown(int i) { if(tree[i].lazy) { tree[le].lazy = tree[ri].lazy = tree[i].lazy; tree[le].color = tree[ri].color = 1<<tree[i].lazy; tree[i].lazy = 0; } } void built(int i,int l,int r) { tree[i].l = l; tree[i].r = r; tree[i].lazy = 0; tree[i].color = 4; if(l == r) return; int mid = (l + r) >> 1; built(le,l,mid); built(ri,mid + 1,r); } void update(int i,int l,int r,int c) { if(tree[i].l >= l && tree[i].r <= r) { tree[i].lazy = c; tree[i].color = 1<<c; return; } if(tree[i].l > r || tree[i].r < l) return; pushdown(i); update(le,l,r,c); update(ri,l,r,c); pushup(i); } void query(int i,int l,int r) { if(tree[i].l >= l && tree[i].r <= r) { ans |= tree[i].color; return; } if(tree[i].l > r || tree[i].r < l) return; pushdown(i); query(le,l,r); query(ri,l,r); } int main() { int n,m,c,l,r; char com; while(scanf("%d %d",&n,&m)) { if(!n && !m) break; built(1,1,n); while(m--) { scanf(" %c",&com); if(com == ‘P‘) { scanf("%d %d %d",&l,&r,&c); update(1,l,r,c); } else { scanf("%d %d",&l,&r); query(1,l,r); int flag = 0; for(int i = 1; i <= 30; i++) { ans >>= 1; if(ans & 1) { if(!flag) printf("%d",i), flag = 1; else printf(" %d",i); } } puts(""); } ans = 0; } } return 0; }
④HDU4578
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4578
思路:对于操作1、2,设k为增加倍数,b为增加数量,初始状态k = 1,b = 0
有递推公式sum1 = ∑(kx + b) = k*sum1 + b*len
sum2 = ∑(kx + b)2 = ∑(k2x2 + 2kxb + b2) = k2 * sum2 + 2*k*sum1*b + b2 * len
sum3 = ∑(kx + b)3 = ∑(k3x3 + 3k2x2b + 3kxb2 + b3) = k3 * sum3 + 3 * k2 * sum2 * b + 3 * k * sum1 * b2 + b3 * len
对于操作3,会覆盖之前的操作,之前的操作应清零
该死的宏定义
#include<bits/stdc++.h> #define N 100005 #define M 10007 #define le i<<1 #define ri i<<1|1 using namespace std; struct node { int l,r,lazy1,lazy2,lazy3,sum1,sum2,sum3; int len() { return (r - l + 1) % M; } }tree[N<<2]; void add_mul(int i,int k,int b) { int s1 = tree[i].sum1 % M; int s2 = tree[i].sum2 % M; int s3 = tree[i].sum3 % M; int len = tree[i].len() % M; tree[i].lazy1 = (k % M * tree[i].lazy1 % M + b % M) % M; tree[i].lazy2 = k % M * tree[i].lazy2 % M; tree[i].sum1 = (k % M * s1 % M + b % M * len % M) % M; tree[i].sum2 = (k % M * k % M * s2 % M + 2 * k % M * s1 % M * b % M + b % M * b % M * len % M) % M; tree[i].sum3 = (k % M * k % M * k % M * s3 % M + 3 * k % M * k % M * s2 % M * b % M + 3 * k % M * s1 % M * b % M * b % M + b % M * b % M * b % M * len % M) % M; } void equ(int i,int c) { tree[i].lazy1 = 0; tree[i].lazy2 = 1; tree[i].lazy3 = c; tree[i].sum1 = c * tree[i].len() % M; tree[i].sum2 = c * c % M * tree[i].len() % M; tree[i].sum3 = c * c % M * c % M * tree[i].len() % M; } void pushup(int i) { tree[i].sum1 = (tree[le].sum1 + tree[ri].sum1) % M; tree[i].sum2 = (tree[le].sum2 + tree[ri].sum2) % M; tree[i].sum3 = (tree[le].sum3 + tree[ri].sum3) % M; } void pushdown(int i) { if(tree[i].lazy3) { equ(le,tree[i].lazy3); equ(ri,tree[i].lazy3); tree[i].lazy3 = 0; } if(tree[i].lazy1 != 0 || tree[i].lazy2 != 1) { add_mul(le,tree[i].lazy2,tree[i].lazy1); add_mul(ri,tree[i].lazy2,tree[i].lazy1); tree[i].lazy1 = 0; tree[i].lazy2 = 1; } } void built(int i,int l,int r) { tree[i].l = l; tree[i].r = r; tree[i].lazy1 = 0; tree[i].lazy2 = 1; tree[i].lazy3 = 0; tree[i].sum1 = tree[i].sum2 = tree[i].sum3 = 0; if(l == r) return; int mid = (l + r) >> 1; built(le,l,mid); built(ri,mid + 1,r); } void update(int i,int l,int r,int op,int c) { if(tree[i].l >= l && tree[i].r <= r) { if(op == 1) add_mul(i,1,c); else if(op == 2) add_mul(i,c,0); else equ(i,c); return; } if(tree[i].l > r || tree[i].r < l) return; pushdown(i); update(le,l,r,op,c); update(ri,l,r,op,c); pushup(i); } int query(int i,int l,int r,int c) { if(tree[i].l >= l && tree[i].r <= r) { if(c == 1) return tree[i].sum1 % M; if(c == 2) return tree[i].sum2 % M; if(c == 3) return tree[i].sum3 % M; } if(tree[i].l > r || tree[i].r < l) return 0; pushdown(i); return (query(le,l,r,c) + query(ri,l,r,c)) % M; } int main() { int n,m; while(scanf("%d %d",&n,&m)) { if(n == 0 && m == 0) break; built(1,1,n); while(m--) { int op,x,y,c; scanf("%d %d %d %d",&op,&x,&y,&c); if(op == 4) printf("%d\n",query(1,x,y,c) % M); else update(1,x,y,op,c); } } return 0; }
⑥HDU3397
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3397
#include<bits/stdc++.h> #define lson i<<1 #define rson i<<1|1 using namespace std; const int N = 1e5 + 5; int str[N]; struct node { int l,r; int lazy; int num1; int ls1,rs1,ms1; int ls0,rs0,ms0; int len() { return r - l + 1; } }tree[N<<2]; void change(int i,int op) { if(op == 2) { swap(tree[i].ls0,tree[i].ls1); swap(tree[i].rs0,tree[i].rs1); swap(tree[i].ms0,tree[i].ms1); tree[i].lazy = 1 - tree[i].lazy; tree[i].num1 = tree[i].len() - tree[i].num1; } else if(op == 1) { tree[i].lazy = 1; tree[i].ls1 = tree[i].rs1 = tree[i].ms1 = tree[i].num1 = tree[i].len(); tree[i].ls0 = tree[i].rs0 = tree[i].ms0 = 0; } else { tree[i].lazy = 0; tree[i].ls0 = tree[i].rs0 = tree[i].ms0 = tree[i].len(); tree[i].ls1 = tree[i].rs1 = tree[i].ms1 = tree[i].num1 = 0; } } void pushup(int i) { if(tree[lson].ls1 == tree[lson].len()) tree[i].ls1 = tree[lson].ls1 + tree[rson].ls1; else tree[i].ls1 = tree[lson].ls1; if(tree[rson].rs1 == tree[rson].len()) tree[i].rs1 = tree[rson].rs1 + tree[lson].rs1; else tree[i].rs1 = tree[rson].rs1; if(tree[lson].ls0 == tree[lson].len()) tree[i].ls0 = tree[lson].ls0 + tree[rson].ls0; else tree[i].ls0 = tree[lson].ls0; if(tree[rson].rs0 == tree[rson].len()) tree[i].rs0 = tree[rson].rs0 + tree[lson].rs0; else tree[i].rs0 = tree[rson].rs0; tree[i].ms1 = max(max(tree[lson].ms1,tree[rson].ms1),tree[lson].rs1 + tree[rson].ls1); tree[i].ms0 = max(max(tree[lson].ms0,tree[rson].ms0),tree[lson].rs0 + tree[rson].ls0); tree[i].num1 = tree[lson].num1 + tree[rson].num1; } void pushdown(int i) { if(tree[i].lazy != -1) { change(lson,tree[i].lazy); change(rson,tree[i].lazy); tree[i].lazy = -1; } } void built(int i,int l,int r) { tree[i].l = l; tree[i].r = r; tree[i].lazy = -1; if(l == r) { tree[i].num1 = str[l]; tree[i].ls1 = tree[i].rs1 = tree[i].ms1 = str[l]; tree[i].ls0 = tree[i].rs0 = tree[i].ms0 = str[l]^1; return; } int mid = (l + r) >> 1; built(lson,l,mid); built(rson,mid+1,r); pushup(i); } void update(int i,int l,int r,int op) { if(tree[i].l >= l && tree[i].r <= r) { change(i,op); return; } if(tree[i].l > r || tree[i].r < l) return; pushdown(i); update(lson,l,r,op); update(rson,l,r,op); pushup(i); } int query(int i,int l,int r,int op) { if(tree[i].l >= l && tree[i].r <= r) { if(op == 3) return tree[i].num1; else return tree[i].ms1; } if(tree[i].l > r || tree[i].r < l) return 0; pushdown(i); if(op == 3) return query(lson,l,r,op) + query(rson,l,r,op); else { int res1 = min(tree[lson].rs1,tree[lson].r - l + 1) + min(tree[rson].ls1,r - tree[rson].l + 1); int res2 = max(query(lson,l,r,op),query(rson,l,r,op)); return max(res1,res2); } } int main() { int T; scanf("%d",&T); while(T--) { int n,m; scanf("%d %d",&n,&m); for(int i = 0; i < n; i++) scanf("%d",str+i); built(1,0,n-1); while(m--) { int op,a,b; scanf("%d %d %d",&op,&a,&b); if(op <= 2) update(1,a,b,op); else printf("%d\n",query(1,a,b,op)); } } return 0; }
⑦HDU3016(DAG最长路DP + 线段树区间更新)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3016
题意:本来看错了,以为板上都可以跳。其实只能在板的两端垂直下落。
//不得不承认专项练习还是有个弊端,就是知道它归类于线段树就会拼命往线段树想,要是直接上手的话我肯定想不到。
思路:downl,downr分别表示从该板左右两端跳会落到哪块板子上(id),这样就可以利用线段树建立出一个DAG。然后就是经典的最长路DP。
#include<bits/stdc++.h> #define lson i<<1 #define rson i<<1|1 using namespace std; const int N = 1e5 + 5; const int inf = 0x3f3f3f3f; int dp[N]; struct Board { int l,r; int h,val; int downl,downr; bool operator < (Board t) { return h < t.h; } }board[N]; struct node { int l,r; int cov; }tree[N<<2]; void pushup(int i) { if(tree[lson].cov == tree[rson].cov) tree[i].cov = tree[lson].cov; else tree[i].cov = -1; } void pushdown(int i) { if(tree[i].cov != -1) { tree[lson].cov = tree[rson].cov = tree[i].cov; tree[i].cov = -1; } } void built(int i,int l,int r) { tree[i].l = l; tree[i].r = r; tree[i].cov = 0; if(l == r) return; int mid = (l + r) >> 1; built(lson,l,mid); built(rson,mid+1,r); } void update(int i,int l,int r,int id) { if(tree[i].l >= l && tree[i].r <= r) { tree[i].cov = id; return; } if(tree[i].l > r || tree[i].r < l) return; pushdown(i); update(lson,l,r,id); update(rson,l,r,id); pushup(i); } int query(int i,int c) { if(tree[i].cov != -1) return tree[i].cov; int mid = (tree[i].l + tree[i].r) >> 1; if(c <= mid) return query(lson,c); else return query(rson,c); } int main() { int n; while(~scanf("%d",&n)) { for(int i = 1; i <= n; i++) scanf("%d %d %d %d",&board[i].h,&board[i].l,&board[i].r,&board[i].val); sort(board + 1,board + n + 1); built(1,1,100000); for(int i = 1; i <= n; i++) { board[i].downl = query(1,board[i].l); board[i].downr = query(1,board[i].r); update(1,board[i].l,board[i].r,i); } memset(dp,-inf,sizeof(dp)); dp[n] = 100 + board[n].val; for(int i = n; i >= 1; i--) { if(dp[i] < 0) dp[i] = -inf; dp[board[i].downl] = max(dp[board[i].downl], dp[i] + board[board[i].downl].val); dp[board[i].downr] = max(dp[board[i].downr], dp[i] + board[board[i].downr].val); } if(dp[0] <= 0) puts("-1"); else printf("%d\n",dp[0]); } return 0; }
⑧POJ3577
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3577
#include<bits/stdc++.h> #define lson i<<1 #define rson i<<1|1 using namespace std; const int N = 1e6 + 5; bool yes[100005]; struct node { int l,r; int lazy,maxm; }tree[N<<2]; void pushdown(int i) { if(tree[i].lazy) { tree[lson].lazy += tree[i].lazy; tree[rson].lazy += tree[i].lazy; tree[lson].maxm += tree[i].lazy; tree[rson].maxm += tree[i].lazy; tree[i].lazy = 0; } } void built(int i,int l,int r) { tree[i].l = l; tree[i].r = r; tree[i].lazy = tree[i].maxm = 0; if(l == r) return; int mid = (l + r) >> 1; built(lson,l,mid); built(rson,mid+1,r); } void update(int i,int l,int r) { if(tree[i].l >= l && tree[i].r <= r) { tree[i].lazy++; tree[i].maxm++; return; } if(tree[i].l > r || tree[i].r < l) return; pushdown(i); update(lson,l,r); update(rson,l,r); tree[i].maxm = max(tree[lson].maxm,tree[rson].maxm); } int query(int i,int l,int r) { if(tree[i].l >= l && tree[i].r <= r) return tree[i].maxm; if(tree[i].l > r || tree[i].r < l) return 0; pushdown(i); return max(query(lson,l,r),query(rson,l,r)); } int main() { int T,cas = 1,k,Q,a,b; scanf("%d",&T); while(T--) { memset(yes,0,sizeof(yes)); scanf("%d %d",&k,&Q); built(1,1,1000000); for(int i = 1; i <= Q; i++) { scanf("%d %d",&a,&b); if(query(1,a,b-1) < k) { yes[i] = 1; update(1,a,b-1); } } printf("Case %d:\n",cas++); for(int i = 1; i <= Q; i++) { if(yes[i]) printf("%d ",i); } printf("\n\n"); } return 0; }
⑨HDU5316(单点更新,区间合并)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5316
题意:给出一个长度为n的序列,有两种操作,op = 0时求出区间[a,b]中奇偶相间(不含空)的子序列的和的最大值,op = 1时把a改成b
思路:oo表示该节点区间[L,R]上以奇开头奇结尾的子序列的和的最大值,oe,eo,ee同理......
自己之前的查询部分写的有点赘,TLE了,网上看了别人的写了下,发现之前的几题也可以简化下代码量的。
#include<bits/stdc++.h> #define lson i<<1 #define rson i<<1|1 using namespace std; typedef long long ll; const int N = 1e5 + 5; const ll inf = 1e18; ll MAX(ll a,ll b,ll c,ll d) { return max(max(a,b),max(c,d)); } struct node { ll oo,oe,eo,ee; node() {} node(ll oo,ll oe,ll eo, ll ee):oo(oo),oe(oe),eo(eo),ee(ee) {} }tree[N<<2]; node pushup(node a,node b) { node res; res.oo = MAX(a.oo, b.oo, a.oo + b.eo, a.oe + b.oo); res.oe = MAX(a.oe, b.oe, a.oo + b.ee, a.oe + b.oe); res.eo = MAX(a.eo, b.eo, a.eo + b.eo, a.ee + b.oo); res.ee = MAX(a.ee, b.ee, a.eo + b.ee, a.ee + b.oe); return res; } void built(int i,int L,int R) { if(L == R) { if(L & 1) scanf("%lld",&tree[i].oo), tree[i].oe = tree[i].eo = tree[i].ee = -inf; else scanf("%lld",&tree[i].ee), tree[i].oo = tree[i].oe = tree[i].eo = -inf; return; } int mid = (L + R) >> 1; built(lson,L,mid); built(rson,mid+1,R); tree[i] = pushup(tree[lson],tree[rson]); } void update(int i,int L,int R,int pos,ll val) { if(L == R) { if(L & 1) tree[i].oo = val; else tree[i].ee = val; return; } int mid = (L + R) >> 1; if(pos <= mid) update(lson,L,mid,pos,val); else update(rson,mid+1,R,pos,val); tree[i] = pushup(tree[lson],tree[rson]); } node query(int i,int L,int R,int l,int r) { if(L >= l && R <= r) return tree[i]; if(L > r || R < l) return node(-inf,-inf,-inf,-inf); int mid = (L + R) >> 1; return pushup(query(lson,L,mid,l,r),query(rson,mid+1,R,l,r)); } int main() { int T; scanf("%d",&T); while(T--) { int n,m; scanf("%d %d",&n,&m); built(1,1,n); while(m--) { int op,a,b; scanf("%d %d %d",&op,&a,&b); if(op) update(1,1,n,a,b); else { node ans = query(1,1,n,a,b); printf("%lld\n",MAX(ans.oo,ans.oe,ans.eo,ans.ee)); } } } return 0; }
线段树专题