洛谷 P1533 可怜的狗狗
Description
小卡家有N只狗，由于品种、年龄不同，每一只狗都有一个不同的漂亮值。漂亮值与漂亮的程度成反比（漂亮值越低越漂亮），吃饭时，狗狗们会按顺序站成一排等着主人给食物。
可是嘉嘉真的很懒，他才不肯喂这么多狗呢，这多浪费时间啊，于是他每次就只给第i只到第j只狗中第k漂亮的狗狗喂食（好狠心的人啊）。而且为了保证某一只狗狗不会被喂太多次，他喂的每个区间（i,j）不互相包含。
Input
第一行输入两个数n，m，你可以假设n<300001 并且 m<50001；m表示他喂了m次。
第二行n个整数，表示第i只狗的漂亮值为ai。
接下来m行，每行3个整数i,j,k表示这次喂食喂第i到第j只狗中第k漂亮的狗的漂亮值。
Output
- M行，每行一个整数，表示每一次喂的那只狗漂亮值为多少。
Sample Input
7 21 5 2 6 3 7 41 5 32 7 1
Sample Output
3
2
题解：
- 平衡树。
- 首先一说这题解法很多，莫队、主席树、划分树、线段树、平衡树。
- 这题用平衡树还是比较巧妙的。观察到题目中有这么一个性质：每个区间（i,j）不互相包含。这就说明，原本下列的3种情况：（/为占位符）
//第一种
………..
///…………
//第二种
………..
///……
//第三种
………..
// ………
- 只会变成下列两种
//第一种
………..
///…………
//第二种
………..
/ ………
- 那么先离线把区间保存下来，按左端点从小到大排序。如果与上一个区间有重叠部分：就删掉上一个区间中与当前区间不重叠的部分，再加上当前新的部分。如果与上一个区间没有重叠部分，就删掉上一个区间，添加当前区间。这样操作就可以得到当前区间。
- 有了这样的性质，每个位置的元素至多被删除/添加一次，复杂度就是O(nlogn)，完全可以接受。
#include#include #include #define N 300005#define M 50005#define inf 0x7fffffffusing namespace std;struct T {int l, r, val, dat, cnt, size;} t[N];struct B {int l, r, k, id;} b[M];int n, m, root, tot;int a[N], ans[M];int read(){ int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();} return x *= f;}bool cmp(B x, B y){ if(x.l == y.l) return x.r < y.r; return x.l < y.l;}void up(int p) {t[p].size = t[t[p].l].size + t[t[p].r].size + t[p].cnt;}int New(int val){ t[++tot].val = val, t[tot].dat = rand(); t[tot].size = t[tot].cnt = 1; return tot;}void zig(int &y){ int x = t[y].l; t[y].l = t[x].r, t[x].r = y, y = x; up(t[y].r), up(y);}void zag(int &x){ int y = t[x].r; t[x].r = t[y].l, t[y].l = x, x = y; up(t[x].l), up(x);}void insert(int &p, int val){ if(!p) {p = New(val); return;} if(val == t[p].val) {t[p].cnt++, up(p); return;} if(val < t[p].val) { insert(t[p].l, val); if(t[t[p].l].dat > t[p].dat) zig(p); } else { insert(t[p].r, val); if(t[t[p].r].dat > t[p].dat) zag(p); } up(p);}void erase(int &p, int val){ if(!p) return; if(val == t[p].val) { if(t[p].cnt > 1) {t[p].cnt--, up(p); return;} if(t[p].l || t[p].r) { if(!t[p].r || t[t[p].l].dat > t[t[p].r].dat) zig(p), erase(t[p].r, val); else zag(p), erase(t[p].l, val); up(p); } else p = 0; return; } val < t[p].val ? erase(t[p].l, val) : erase(t[p].r, val); up(p);}int valOfRank(int p, int rank){ if(!p) return inf; if(t[t[p].l].size >= rank) return valOfRank(t[p].l, rank); if(t[t[p].l].size + t[p].cnt >= rank) return t[p].val; return valOfRank(t[p].r, rank - t[t[p].l].size - t[p].cnt);}int main(){ New(inf), New(-inf), root = 1, t[1].l = 2, up(1); cin >> n >> m; for(int i = 1; i <= n; i++) a[i] = read(); for(int i = 1; i <= m; i++) { b[i].l = read(), b[i].r = read(); b[i].k = read(), b[i].id = i; } sort(b + 1, b + 1 + m, cmp); for(int i = 1; i <= m; i++) { if(b[i - 1].r >= b[i].l) { for(int j = b[i - 1].l; j < b[i].l; j++) erase(root, a[j]); for(int j = b[i - 1].r + 1; j <= b[i].r; j++) insert(root, a[j]); } else { for(int j = b[i - 1].l; j <= b[i - 1].r; j++) erase(root, a[j]); for(int j = b[i].l; j <= b[i].r; j++) insert(root, a[j]); } ans[b[i].id] = valOfRank(root, b[i].k + 1); } for(int i = 1; i <= m; i++) printf("%d\n", ans[i]); return 0;}