codeforces #381 div2 E. Alyona and towers (线段树 区间合并)
e:题意：那个数，定义hill为一段连续的区间，满足该区间为严格单峰。现在有若干操作，每个操作是对某段区间的数同时增加一个数，问每次操作后，所有的hill中，宽度最大的（区间长度最大）的是多少。
思路：同时增加一个数很线段树。。。但是要维护什么呢。。。？
_猜测：肯定要维护一个区间中hill的最大宽度..._
但是合并的时候要怎么办呢。。。
考虑两个方向的合并。。。
所以还要维护一个区间中，包含右端点的向左单调减延伸的长度，以及左端点的值。
同理，要维护一个区间中，包含左端点的向右单调增延伸的长度，以及右端点的值。
那么每次pushup的时候，就是两个区间hill的最大值，以及两个方向合并的最大值中取最大。。。
。。。上面是我口胡的。。。
upd:
口胡的还是有点靠谱的（并没有2333，还是漏了情况）
具体题解见代码注释
以及，为了过这道题先过了在岛老师空间题解中提到的两道题目：
hdu 5367题目链接
/* ***********************************************
Author :111qqz
Created Time :2016年11月27日 星期日 22时16分44秒
File Name :code/cf/#381/E.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=3E5+7;
7int a[N];
8int n,m;
9struct Tree
10{
11 LL lm,rm;//左右端点值。
12 int ans,len,upL,upR,downL,downR,maxL,maxR;
13 /* 分别为
14 * ans:区间最优解
15 * len:区间长度
16 * upL,downL,maxL：包含左端点的递增，递减，山型的长度
17 * upR,downR,maxR: 包含右端点的递增，递减，山型的长度
18 */
19 Tree()
20 {
21 ans = len = upL = upR = downL = downR = maxL = maxR = lm = rm = 0;
22 }
23 Tree( int x)
24 {
25 ans = len = upL = upR = downL = downR = maxL = maxR = 1;
26 lm = rm = x;
27 }
28};
1Tree operator + ( Tree x,Tree y) //x为左子树所表示的区间，y为右子树所表示的区间
2{
3 Tree res;
4 if (x.rm>y.lm)
5 {
6 res.ans = max(x.ans,y.ans);
7 res.len = x.len + y.len;//区间长度这个变量也可以不放在线段树的域中，而是每次pushUp和pushdown的时候传参数进去。
8 res.upL = x.upL;
9 res.upR = y.upR;
10 res.downL = x.downL +(x.downL==x.len) * (y.downL);//如果左区间全都递减，那么新区间包含左端点的递减长度可以把右区间包含左端点的递减长度包含进来。
11 res.downR = y.downR + (y.downR==y.len) *(x.downR);//如果右区间全都递减，那么新区间包含右端点的递减长度可以把左区间包含右端点的递减长度包含进来。
12 res.lm = x.lm;
13 res.rm = y.rm; //更新端点值
14 res.ans = max(res.ans,x.maxR+y.downL);//左区间包含右端点的山型可以再接一部分右区间包含左端点的下降序列，仍然是山型。
15 res.maxL = x.maxL + (x.maxL == x.len) *(y.downL);//新区间包含左端点的山形在左区间都是山型的时候可以把右区间包含左端点的下降序列包含进来。
16 res.maxR = y.maxR +(y.downL == y.len) *(x.maxR);//新区间包含右端点的山形 在右区间都是下降的时候可以把左区间包含右端点的山形序列包含进来。
1 }
2 else if (x.rm<y.lm)//同上，只是方向相反。
3 {
4 res.ans = max(x.ans,y.ans);
5 res.len = x.len + y.len;
6 res.upL = x.upL +(x.upL == x.len)*(y.upL);
7 res.upR = y.upR +(y.upR == y.len)*(x.upR);
8 res.downL = x.downL;
9 res.downR = y.downR;
10 res.lm = x.lm;
11 res.rm = y.rm;
12 res.ans = max(res.ans,x.upR + y.maxL);
13 res.maxL = x.maxL + (x.upL==x.len)*(y.maxL);
14 res.maxR = y.maxR + (y.maxR==y.len)*(x.upR);
15 }
16 else //不要忘记相等的情况。
17 {
18 res.ans = max(x.ans,y.ans);
19 res.len = x.len + y.len;
20 res.upL = x.upL;
21 res.upR = y.upR;
22 res.downL = x.downL;
23 res.downR = y.downR;
24 res.lm = x.lm;
25 res.rm = y.rm;
26 res.maxL = x.maxL;
27 res.maxR = y.maxR;
1 }
2 return res;
3}
4Tree tree[N<<2];
5LL lazy[N<<2];
6void doit(int rt,LL v)
7{
8 lazy[rt]+=v;
9 tree[rt].lm += v;
10 tree[rt].rm += v;
11}
12void PushDown(int rt)
13{
14 if (lazy[rt])
15 {
16 doit(rt<<1,lazy[rt]);
17 doit(rt<<1|1,lazy[rt]);
18 lazy[rt] = 0 ;
19 }
20}
21void build( int l,int r,int rt)
22{
23 // cout<<l<<" "<<r<<" "<<rt<<endl;
24 if (l==r)
25 {
26 tree[rt] = Tree(a[l]);
27 return ;
28 }
1 int m = (l+r)>>1;
2 build(lson);
3 build(rson);
4 tree[rt] = tree[rt<<1] + tree[rt<<1|1];
5}
1void update(int L,int R,int d,int l,int r,int rt)
2{
3 if (L<=l&&r<=R)
4 {
5 doit(rt,d);
6 return;
7 }
8 PushDown(rt);
9 int m = (l+r)>>1;
10 if (L<=m)
11 update(L,R,d,lson);
12 if (R>=m+1)
13 update(L,R,d,rson);
14 tree[rt] = tree[rt<<1] + tree[rt<<1|1];
15}
1int main()
2{
3 #ifndef ONLINE_JUDGE
4 freopen("code/in.txt","r",stdin);
5 #endif
6 cin>>n;
7 for ( int i = 1; i <= n ; i++) scanf("%d",&a[i]);
8 cin>>m;
9 build(1,n,1);
10 while (m--)
11 {
12 int l,r,d;
13 scanf("%d%d%d",&l,&r,&d);
14 update(l,r,d,1,n,1);
15 printf("%d\n",tree[1].ans);
16 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}