瑶瑶想要玩滑梯
Time Limit: 10000/5000MS (Java/Others)Memory Limit: 512000/256000KB (Java/Others)SubmitProblem Description
众所周知，瑶瑶（tsyao）是个贪玩的萌妹子，特别喜欢闹腾，恰好今天是一个风和日丽的日子，瑶瑶嚷着让姐姐带她去去公园玩滑梯，可是公园的滑梯比较独特，由单位积木搭成，积木是排成一排搭好，每列有xi个积木，共n列。小明能够对积木进行m次操作：
1.U L R yi ： 将[L,R]列的积木高度全都改为yi
2.Q L R ： 查询[L,R]列最长连续上升的列长度(LCIS)
知道[L,R]列最长连续上升的列长度过后，瑶瑶就可以开开心心地玩滑梯啦！
Ps：连续上升的列长度指对于一段合法区间,都有
。
话说积木是平的，瑶瑶是怎么从高处滑到低处的呢？？作为姐姐也不知道，很想知道吧？你去问她吧。。
Input
第一行 两个整数n，m；
第二行 n个整数，分别为[1,n]区间每列积木个数；
接下来m行为m个操作
Output
输出x行，每行为每次操作2的查询结果。
Sample Input
5 42 1 2 3 1Q 1 4Q 2 5U 2 4 3Q 1 5Sample Output
332Hint
对于 100%的数据，有1 ≤ n ≤ 10^5 , 1 ≤ m ≤ 10^5 , 1 ≤ xi ≤ 10^8。
单组输入，共10组数据。
第一种操作是常规的区间修改。
第二种操作求区间的LCIS, 显然有三种情况，完全来自左孩子，完全来自右孩子，或者由左孩子和右孩子共同组成。
最体的实现可以参考下面代码。
Accepted Code:
1 /************************************************************************* 2 > File Name: 1101.cpp 3 > Author: Stomach_ache 4 > Mail: sudaweitong@gmail.com 5 > Created Time: 2014年08月02日 星期六 13时32分34秒 6 > Propose: 7 ************************************************************************/ 8 //线段树 9 #include10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 using namespace std; 17 18 #define lson(x) (x<<1) 19 #define rson(x) ((x<<1)|1) 20 const int maxn = 100002; 21 int a[maxn]; 22 struct node { 23 int l, r; //结点区间范围 24 //maxo维护区间LCIS长度 25 //maxl维护从区间最左开始的上升子序列长度(最左必取) 26 //maxr维护以区间最右为止的上升子序列长度(最右必取) 27 int maxo, maxl, maxr; 28 //区间最左端和最右端的值 29 int numl, numr; 30 //区间是否完全相同, 也就是LCIS长度为１ 31 bool s; 32 void set(int ll, int rr) { 33 l = ll; r = rr; s = false; 34 } 35 }Tr[maxn<<2]; 36 37 void pushup(int o) { 38 Tr[o].maxo = max(Tr[lson(o)].maxo, Tr[rson(o)].maxo); 39 Tr[o].maxl = Tr[lson(o)].maxl; 40 Tr[o].maxr = Tr[rson(o)].maxr; 41 Tr[o].numl = Tr[lson(o)].numl; 42 Tr[o].numr = Tr[rson(o)].numr; 43 //是否可合并左孩子和右孩子 44 if (Tr[lson(o)].numr < Tr[rson(o)].numl) { 45 Tr[o].maxo = max(Tr[o].maxo, Tr[lson(o)].maxr+Tr[rson(o)].maxl); 46 //是否可更新maxl 47 if (Tr[o].maxl == Tr[lson(o)].r-Tr[lson(o)].l+1) { 48 Tr[o].maxl += Tr[rson(o)].maxl; 49 } 50 //是否可更新maxr 51 if (Tr[o].maxr == Tr[rson(o)].r-Tr[rson(o)].l+1) { 52 Tr[o].maxr += Tr[lson(o)].maxr; 53 } 54 } 55 } 56 57 void build(int o, int l, int r) { 58 Tr[o].set(l, r); 59 if (l == r) { 60 Tr[o].maxo = Tr[o].maxr = Tr[o].maxl = 1; 61 Tr[o].numl = Tr[o].numr = a[l]; 62 Tr[o].s = true; 63 return ; 64 } 65 int mid = (l + r) / 2; 66 build(lson(o), l, mid); 67 build(rson(o), mid+1, r); 68 pushup(o); 69 } 70 71 void pushdown(int o) { 72 if (Tr[o].s) { 73 Tr[o].s = false; 74 Tr[lson(o)].maxo = Tr[lson(o)].maxl = Tr[lson(o)].maxr = 1; 75 Tr[lson(o)].numl = Tr[lson(o)].numr = Tr[o].numl; 76 Tr[rson(o)].maxo = Tr[rson(o)].maxl = Tr[rson(o)].maxr = 1; 77 Tr[rson(o)].numl = Tr[rson(o)].numr = Tr[o].numl; 78 Tr[lson(o)].s = Tr[rson(o)].s = true; 79 } 80 } 81 82 void update(int o, int l, int r, int x) { 83 if (Tr[o].l >= l && Tr[o].r <= r) { 84 Tr[o].maxo = Tr[o].maxl = Tr[o].maxr = 1; 85 Tr[o].numl = Tr[o].numr = x; 86 Tr[o].s = true; 87 return ; 88 } 89 pushdown(o); 90 int mid = Tr[lson(o)].r; 91 if (l <= mid) update(lson(o), l, r, x); 92 if (r > mid) update(rson(o), l, r, x); 93 pushup(o); 94 } 95 96 int query(int o, int l, int r) { 97 if (Tr[o].l >= l && Tr[o].r <= r) { 98 return Tr[o].maxo; 99 }100 pushdown(o);101 int mid = Tr[lson(o)].r;102 //三种可能构成最优解的情况103 int ansl(0), ansr(0), anso(0);104 if (l <= mid) ansl = query(lson(o), l, r);105 if (r > mid) ansr = query(rson(o), l, r);106 if (l <= mid && r > mid) {107 if (Tr[lson(o)].numr < Tr[rson(o)].numl) {108 anso = Tr[lson(o)].maxr + Tr[rson(o)].maxl;109 }110 }111 return max(anso, max(ansl, ansr));112 }113 114 int main(void) {115 int n, m;116 scanf("%d %d", &n, &m);117 for (int i = 1; i <= n; i++) scanf("%d", a + i);118 build(1, 1, n);119 120 while (m--) {121 char t[10];122 //注意输入123 scanf("%s", t);124 if (t[0] == 'U') {125 int l, r, x;126 scanf("%d %d %d", &l, &r, &x);127 update(1, l, r, x);128 } else {129 int l, r;130 scanf("%d %d", &l, &r);131 printf("%d\n", query(1, l, r));132 }133 }134 135 return 0;136 }