题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=1540
哈哈，终于过了卡了很久的线段树。每个节点维护左边的最长，右边的最长和当前节点往下的最值。
更新每个节点的左右最值的时候要判断一下这个点的左右儿子的区间里有没有切断的点，如果没有那么就将整条的长度更新上去，否则就直接更新为左儿子（右儿子）的左最值（右最值）。以及剪枝，当当前节点最大值为0或和它的节点数相同的时候，则直接可以返回最值。
1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <cstring> 5 #include <climits> 6 #include <complex> 7 #include <fstream> 8 #include <cassert> 9 #include <cstdio> 10 #include <bitset> 11 #include <vector> 12 #include <deque> 13 #include <queue> 14 #include <stack> 15 #include <ctime> 16 #include <set> 17 #include <map> 18 #include <cmath> 19 20 using namespace std; 21 #define fr first 22 #define sc second 23 #define cl clear 24 #define BUG puts("here!!!") 25 #define W(a) while(a--) 26 #define pb(a) push_back(a) 27 #define Rint(a) scanf("%d", &a) 28 #define Rll(a) scanf("%lld", &a) 29 #define Rs(a) scanf("%s", a) 30 #define Cin(a) cin >> a 31 #define FRead() freopen("in", "r", stdin) 32 #define FWrite() freopen("out", "w", stdout) 33 #define Rep(i, len) for(int i = 0; i < (len); i++) 34 #define For(i, a, len) for(int i = (a); i < (len); i++) 35 #define Cls(a) memset((a), 0, sizeof(a)) 36 #define Clr(a, p) memset((a), (p), sizeof(a)) 37 #define Full(a) memset((a), 0x7f7f7f, sizeof(a)) 38 #define lrt rt << 1 39 #define rrt rt << 1 | 1 40 #define pi 3.14159265359 41 #define RT return 42 #define lowbit(p) p & (-p) 43 #define onenum(p) __builtin_popcount(p) 44 typedef long long LL; 45 typedef long double LD; 46 typedef unsigned long long ULL; 47 typedef pair<int, int> pii; 48 typedef pair<string, int> psi; 49 typedef pair<LL, LL> pll; 50 typedef map<string, int> msi; 51 typedef vector<int> vi; 52 typedef vector<LL> vl; 53 typedef vector<vl> vvl; 54 typedef vector<bool> vb; 55 56 const int maxn = 50500; 57 typedef struct Node { 58 int left, max, right; 59 int l; 60 int r; 61 }Node; 62 Node seg[maxn<<2]; 63 int n, m, p; 64 char q[3]; 65 stack<int> last; 66 67 void build(int l, int r, int rt) { 68 seg[rt].l = l; seg[rt].r = r; 69 seg[rt].left = r - l + 1; 70 seg[rt].right = r - l + 1; 71 seg[rt].max = r - l + 1; 72 if(l == r) return; 73 int mid = (l + r) >> 1; 74 build(l, mid, lrt); 75 build(mid+1, r, rrt); 76 } 77 78 void update(int l, int r, int rt, int v, int p) { 79 if(l == r) { 80 seg[rt].left = v; 81 seg[rt].right = v; 82 seg[rt].max = v; 83 return; 84 } 85 int mid = (l + r) >> 1; 86 if(p <= mid) update(l, mid, lrt, v, p); 87 else update(mid+1, r, rrt, v, p); 88 89 seg[rt].max=max(max(seg[lrt].max,seg[rrt].max),seg[lrt].right+seg[rrt].left); 90 if(seg[lrt].left==(seg[lrt].r-seg[lrt].l+1)) seg[rt].left = seg[lrt].max + seg[rrt].left; 91 else seg[rt].left = seg[lrt].left; 92 if(seg[rrt].right==(seg[rrt].r-seg[rrt].l+1)) seg[rt].right = seg[rrt].max + seg[lrt].right; 93 else seg[rt].right=seg[rrt].right; 94 } 95 96 int query(int l, int r, int rt, int p) { 97 if(seg[rt].max==0||(seg[rt].max==(seg[rt].r-seg[rt].l+1))) 98 return seg[rt].max; 99 if(l == r) 100 return seg[rt].max; 101 int mid = (l + r) >> 1; 102 if(p <= mid) { 103 if(p >= seg[lrt].r - seg[lrt].right + 1) return query(l, mid, lrt, p) + query(mid+1, r, rrt, mid+1); 104 else return query(l, mid, lrt, p); 105 } 106 else { 107 if(p<=seg[rrt].l+seg[rrt].left-1) return query(mid+1, r, rrt, p) + query(l, mid, lrt, mid); 108 else return query(mid+1, r, rrt, p); 109 } 110 } 111 112 int main() { 113 // FRead(); 114 while(~Rint(n) && ~Rint(m)) { 115 while(!last.empty()) last.pop(); 116 build(1, n, 1); 117 Rep(i, m) { 118 Rs(q); 119 if(q[0] == 'D') { 120 Rint(p); 121 last.push(p); 122 update(1, n, 1, 0, p); 123 } 124 if(q[0] == 'Q') { 125 Rint(p); 126 printf("%d ", query(1, n, 1, p)); 127 } 128 if(q[0] == 'R') { 129 p = last.top(); 130 last.pop(); 131 update(1, n, 1, 1, p); 132 } 133 } 134 } 135 RT 0; 136 }