codeforces #381 div2 E. Alyona and towers (线段树 区间合并)
e:题意：那个数，定义hill为一段连续的区间，满足该区间为严格单峰。现在有若干操作，每个操作是对某段区间的数同时增加一个数，问每次操作后，所有的hill中，宽度最大的（区间长度最大）的是多少。
思路：同时增加一个数很线段树。。。但是要维护什么呢。。。？
_猜测：肯定要维护一个区间中hill的最大宽度..._
但是合并的时候要怎么办呢。。。
考虑两个方向的合并。。。
所以还要维护一个区间中，包含右端点的向左单调减延伸的长度，以及左端点的值。
同理，要维护一个区间中，包含左端点的向右单调增延伸的长度，以及右端点的值。
那么每次pushup的时候，就是两个区间hill的最大值，以及两个方向合并的最大值中取最大。。。
。。。上面是我口胡的。。。
upd:
口胡的还是有点靠谱的（并没有2333，还是漏了情况）
具体题解见代码注释
以及，为了过这道题先过了在岛老师空间题解中提到的两道题目：
hdu 5367题目链接
1/* ***********************************************
2Author :111qqz
3Created Time :2016年11月27日 星期日 22时16分44秒
4File Name :code/cf/#381/E.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=3E5+7;
34int a[N];
35int n,m;
36struct Tree
37{
38 LL lm,rm;//左右端点值。
39 int ans,len,upL,upR,downL,downR,maxL,maxR;
40 /* 分别为
41 * ans:区间最优解
42 * len:区间长度
43 * upL,downL,maxL：包含左端点的递增，递减，山型的长度
44 * upR,downR,maxR: 包含右端点的递增，递减，山型的长度
45 */
46 Tree()
47 {
48 ans = len = upL = upR = downL = downR = maxL = maxR = lm = rm = 0;
49 }
50 Tree( int x)
51 {
52 ans = len = upL = upR = downL = downR = maxL = maxR = 1;
53 lm = rm = x;
54 }
55};
56
57Tree operator + ( Tree x,Tree y) //x为左子树所表示的区间，y为右子树所表示的区间
58{
59 Tree res;
60 if (x.rm>y.lm)
61 {
62 res.ans = max(x.ans,y.ans);
63 res.len = x.len + y.len;//区间长度这个变量也可以不放在线段树的域中，而是每次pushUp和pushdown的时候传参数进去。
64 res.upL = x.upL;
65 res.upR = y.upR;
66 res.downL = x.downL +(x.downL==x.len) * (y.downL);//如果左区间全都递减，那么新区间包含左端点的递减长度可以把右区间包含左端点的递减长度包含进来。
67 res.downR = y.downR + (y.downR==y.len) *(x.downR);//如果右区间全都递减，那么新区间包含右端点的递减长度可以把左区间包含右端点的递减长度包含进来。
68 res.lm = x.lm;
69 res.rm = y.rm; //更新端点值
70 res.ans = max(res.ans,x.maxR+y.downL);//左区间包含右端点的山型可以再接一部分右区间包含左端点的下降序列，仍然是山型。
71 res.maxL = x.maxL + (x.maxL == x.len) *(y.downL);//新区间包含左端点的山形在左区间都是山型的时候可以把右区间包含左端点的下降序列包含进来。
72 res.maxR = y.maxR +(y.downL == y.len) *(x.maxR);//新区间包含右端点的山形 在右区间都是下降的时候可以把左区间包含右端点的山形序列包含进来。
73
74 }
75 else if (x.rm<y.lm)//同上，只是方向相反。
76 {
77 res.ans = max(x.ans,y.ans);
78 res.len = x.len + y.len;
79 res.upL = x.upL +(x.upL == x.len)*(y.upL);
80 res.upR = y.upR +(y.upR == y.len)*(x.upR);
81 res.downL = x.downL;
82 res.downR = y.downR;
83 res.lm = x.lm;
84 res.rm = y.rm;
85 res.ans = max(res.ans,x.upR + y.maxL);
86 res.maxL = x.maxL + (x.upL==x.len)*(y.maxL);
87 res.maxR = y.maxR + (y.maxR==y.len)*(x.upR);
88 }
89 else //不要忘记相等的情况。
90 {
91 res.ans = max(x.ans,y.ans);
92 res.len = x.len + y.len;
93 res.upL = x.upL;
94 res.upR = y.upR;
95 res.downL = x.downL;
96 res.downR = y.downR;
97 res.lm = x.lm;
98 res.rm = y.rm;
99 res.maxL = x.maxL;
100 res.maxR = y.maxR;
101
102 }
103 return res;
104}
105Tree tree[N<<2];
106LL lazy[N<<2];
107void doit(int rt,LL v)
108{
109 lazy[rt]+=v;
110 tree[rt].lm += v;
111 tree[rt].rm += v;
112}
113void PushDown(int rt)
114{
115 if (lazy[rt])
116 {
117 doit(rt<<1,lazy[rt]);
118 doit(rt<<1|1,lazy[rt]);
119 lazy[rt] = 0 ;
120 }
121}
122void build( int l,int r,int rt)
123{
124 // cout<<l<<" "<<r<<" "<<rt<<endl;
125 if (l==r)
126 {
127 tree[rt] = Tree(a[l]);
128 return ;
129 }
130
131 int m = (l+r)>>1;
132 build(lson);
133 build(rson);
134 tree[rt] = tree[rt<<1] + tree[rt<<1|1];
135}
136
137void update(int L,int R,int d,int l,int r,int rt)
138{
139 if (L<=l&&r<=R)
140 {
141 doit(rt,d);
142 return;
143 }
144 PushDown(rt);
145 int m = (l+r)>>1;
146 if (L<=m)
147 update(L,R,d,lson);
148 if (R>=m+1)
149 update(L,R,d,rson);
150 tree[rt] = tree[rt<<1] + tree[rt<<1|1];
151}
152
153int main()
154{
155 #ifndef ONLINE_JUDGE
156 freopen("code/in.txt","r",stdin);
157 #endif
158 cin>>n;
159 for ( int i = 1; i <= n ; i++) scanf("%d",&a[i]);
160 cin>>m;
161 build(1,n,1);
162 while (m--)
163 {
164 int l,r,d;
165 scanf("%d%d%d",&l,&r,&d);
166 update(l,r,d,1,n,1);
167 printf("%d\n",tree[1].ans);
168 }
169
170 #ifndef ONLINE_JUDGE
171 fclose(stdin);
172 #endif
173 return 0;
174}