线段树+Treap, 基本思路同ZOJ2112(区间kth): http://www.cnblogs.com/usingnamespace/p/5152220.html
维护x在区间[s, t]的前驱只要利用线段树将该区间分为线段树上一些节点代表的区间, 在每个区间中求x的前驱取其中的
最大值
同理后继只需在[s, t]划分出的每个区间中求后继然后取最小值
代码如下(写法拙劣, 最开始少写了个else, TLE了, 最后过了但还是跑了10108 ms, 指针写法快一点吧)
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> using namespace std; typedef const int& ci; const int maxn = 3000007, inf = 1e9; int read() { int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();} return x * f; } int n, m, Nm, Pre, Suf, arr[maxn]; int root[maxn], sz, size[maxn], rnd[maxn], val[maxn], lc[maxn], rc[maxn], cnt[maxn]; void update(ci k) { size[k] = size[lc[k]] + size[rc[k]] + cnt[k]; } void r_rot(int &k) { int t = lc[k]; lc[k] = rc[t]; rc[t] = k; size[t] = size[k]; update(k); k = t; } void l_rot(int &k) { int t = rc[k]; rc[k] = lc[t]; lc[t] = k; size[t] = size[k]; update(k); k = t; } void Insert(int &k, ci x) { if(k == 0) { size[k = ++sz] = cnt[k] = 1; val[k] = x; rnd[k] = rand(); lc[k] = rc[k] = 0; return; } size[k]++; if(x == val[k]) {cnt[k]++; return;} if(x < val[k]) { Insert(lc[k], x); if(rnd[lc[k]] < rnd[k]) r_rot(k); } else { Insert(rc[k], x); if(rnd[rc[k]] < rnd[k]) l_rot(k); } } void Delete(int &k , ci x) { if(k == 0) return; if(x == val[k]) { if(cnt[k] > 1) {cnt[k]--, size[k]--; return;} if(lc[k] * rc[k] == 0) k = lc[k] + rc[k]; else if(rnd[lc[k]] < rnd[rc[k]]) r_rot(k), Delete(k, x); else l_rot(k), Delete(k, x); } else if(x < val[k]) size[k]--, Delete(lc[k], x); else size[k]--, Delete(rc[k], x); } //求不大于num的数的个数 void Find(ci k, ci num) { if(!k) return; if(num >= val[k]) { Nm += size[lc[k]] + cnt[k]; Find(rc[k], num); } else Find(lc[k], num); } void pre(ci k, ci x) { if(!k) return; if(x > val[k]) { Pre = max(Pre, val[k]); pre(rc[k], x); } else pre(lc[k], x); } void suf(ci k, ci x) { if(!k) return; if(x < val[k]) { Suf = min(Suf, val[k]); suf(lc[k], x); } else suf(rc[k], x); } void insert(ci k, ci l, ci r, ci v, ci pos) { Insert(root[k], v); if(l == r) return; int mid = (l + r) >> 1; if(pos <= mid) insert(k << 1, l, mid, v, pos); else insert(k << 1 | 1, mid + 1, r, v, pos); } void modify(ci k, ci l, ci r, ci v, ci pos) { Delete(root[k], arr[pos]); Insert(root[k], v); if(l == r) return; int mid = (l + r) >> 1; if(pos <= mid) modify(k << 1, l, mid, v, pos); else modify(k << 1 | 1, mid + 1, r, v, pos); } //区间内排名 void Rank(ci k, ci l, ci r, ci s, ci t, ci x) { if(l == s && t == r) {Find(root[k], x); return;} int mid = (l + r) >> 1; if(t <= mid) {Rank(k << 1, l, mid, s, t, x); return;} if(s > mid) {Rank(k << 1 | 1, mid + 1, r, s, t, x); return;} Rank(k << 1, l, mid, s, mid, x); Rank(k << 1 | 1, mid + 1, r, mid + 1, t, x); } //区间内前驱 void Prev(ci k, ci l, ci r, ci s, ci t, ci x) { if(l == s && t == r) {pre(root[k], x); return;} int mid = (l + r) >> 1; if(t <= mid) {Prev(k << 1, l, mid, s, t, x); return;} if(s > mid) {Prev(k << 1 | 1, mid + 1, r, s, t, x); return;} Prev(k << 1, l, mid, s, mid, x); Prev(k << 1 | 1, mid + 1, r, mid + 1, t, x); } //区间内后继 void Suff(ci k, ci l, ci r, ci s, ci t, ci x) { if(l == s && t == r) {suf(root[k], x); return;} int mid = (l + r) >> 1; if(t <= mid) {Suff(k << 1, l, mid, s, t, x); return;} if(s > mid) {Suff(k << 1 | 1, mid + 1, r, s, t, x); return;} Suff(k << 1, l, mid, s, mid, x); Suff(k << 1 | 1, mid + 1, r, mid + 1, t, x); } int main() { n = read(); m = read(); for(int i = 1; i <= n; i++) { arr[i] = read(); insert(1, 1, n, arr[i], i); } for(int i = 1; i <= m; i++) { int opt, x, y, z, l, r; opt = read(); switch(opt) { case 1: x = read(); y = read(); z = read(); Nm = 0; Rank(1, 1, n, x, y, z - 1); printf("%d ", Nm + 1); break; case 2: x = read(); y = read(); z = read(); l = 0, r = 100000000; while(l <= r) { int mid = (l + r) >> 1; Nm = 0; Rank(1, 1, n, x, y, mid); if(Nm >= z) r = mid - 1; else l = mid + 1; } printf("%d ", l); break; case 3: x = read(); y = read(); modify(1, 1, n, y, x); arr[x] = y; break; case 4: x = read(); y = read(); z = read(); Pre = 0; Prev(1, 1, n, x, y, z); printf("%d ", Pre); break; case 5: x = read(); y = read(); z = read(); Suf = inf; Suff(1, 1, n, x, y, z); printf("%d ", Suf); break; } } return 0; }