[UESTC]Another LCIS[线段树][区间合并][成段修改]
终于体会了什么是WA至死.....orz
14WA in 3Days
题意:
给出n个数, a 区间同时加上d, q 询问区间LCIS.
思路:
成段修改还是用标记.
区间合并除了PushUp需要判断相接, query也需要. 而且有两种实现:
一是涉及哪个儿子就query, 一直取最大(此代码),二是若只涉及一个儿子, 返回query那个儿子; 否则两边&中间取最大. 有点小差别~
本来我想原数列直接保存就行, 因为每次只修改区间的端点, 而对于每一个标记, 可以维持儿子端点只被修改一次(中间的重复可以判断). 但是一直WA...目前还没想通是哪错了><
AC的方案是树中增加左右端点, 这样就可以严格分层修改, 不会有隐患.
query中lmax写成rmax....此等细部暗箭难防啊.......只能苦练火眼金睛以及严谨的编码能力....
#include <cstdio> #include <algorithm> using namespace std; #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 const int MAXN = 111111; int mmax[MAXN<<2],lmax[MAXN<<2],rmax[MAXN<<2],add[MAXN<<2],lv[MAXN<<2],rv[MAXN<<2]; int T, L, R, V, cas, N, Q; char op[5]; void PushUp(int w, int rt) { lmax[rt] = lmax[rt<<1], rmax[rt] = rmax[rt<<1|1]; lv[rt] = lv[rt<<1], rv[rt] = rv[rt<<1|1]; mmax[rt] = max(mmax[rt<<1], mmax[rt<<1|1]); if(rv[rt<<1]<lv[rt<<1|1]) { if(lmax[rt<<1]==w-(w>>1)) lmax[rt] += lmax[rt<<1|1]; if(rmax[rt<<1|1]==w>>1) rmax[rt] += rmax[rt<<1]; mmax[rt] = max(mmax[rt], rmax[rt<<1]+lmax[rt<<1|1]); } } void build(int l, int r, int rt) { add[rt] = 0; if(l==r) { scanf("%d",&lv[rt]); rv[rt] = lv[rt]; mmax[rt] = lmax[rt] = rmax[rt] = 1; return; } int m = (l+r)>>1; build(lson); build(rson); PushUp(r-l+1,rt); } void PushDown(int rt) {//直接在那上面改大概是有悖线段树的思想吧> < if(add[rt]) { add[rt<<1] += add[rt]; add[rt<<1|1] += add[rt]; lv[rt<<1] += add[rt], lv[rt<<1|1] += add[rt]; rv[rt<<1] += add[rt], rv[rt<<1|1] += add[rt]; add[rt] = 0; } } void update(int L, int R, int V, int l, int r, int rt) { if(L<=l && r<=R) { add[rt] += V; lv[rt] += V; rv[rt] += V; return; } PushDown(rt); int m = (l+r)>>1; if(L<=m) update(L, R, V, lson); if(m<R) update(L, R, V, rson); PushUp(r-l+1,rt); } int query(int L, int R, int l, int r, int rt) { if(L<=l && r<=R) { return mmax[rt]; } PushDown(rt); int m = (l+r)>>1; int ans = 0; if(L<=m) ans = max(ans, query(L,R,lson)); if(R>m) ans = max(ans, query(L,R,rson)); if(rv[rt<<1]<lv[rt<<1|1]) { ans = max(ans, min(R, m+lmax[rt<<1|1]) - max(L, m-rmax[rt<<1]+1) + 1); } return ans; } int main() { scanf("%d",&T); cas = 0; while(cas++<T) { printf("Case #%d:\n",cas); scanf("%d %d",&N, &Q); build(1, N, 1); while(Q--) { scanf("%s",op); if(op[0]=='a') { scanf("%d %d %d",&L,&R,&V); update(L, R, V, 1, N, 1); } else { scanf("%d %d",&L,&R); printf("%d\n",query(L, R, 1, N, 1)); } } } return 0; }