题解 P1533 【可怜的狗狗】

Nemlit

2019-03-12 21:16:34

Solution

## [原文地址](https://www.cnblogs.com/bcoier/p/10519718.html) 首先这道题目,当然可以作为[主席树](https://www.cnblogs.com/bcoier/p/10293521.html)的模板来做,但是这道题目有令一种解法 发现操作允许离线,我们考律莫队 首先建一棵权值线段树,我们可以查询权值线段树里的值的第K大,所以我们可以利用莫队进行删减操作(其实和主席树差不多?)。 PS:由于保证所有数据不重复,离散化的时候就没必要去重了。 ``` #include<bits/stdc++.h> using namespace std; #define il inline #define re register #define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout) #define inf 123456789 il int read() { re int x = 0, f = 1; re char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return x * f; } #define rep(i, s, t) for(re int i = s; i <= t; ++ i) #define drep(i, s, t) for(re int i = t; i >= s; -- i) #define Next(i, u) for(re int i = head[u]; i; i = e[i].next) #define ls k * 2 #define rs k * 2 + 1 #define maxn 300005 struct node{int x, y, k, id;}q[maxn]; struct pax{int id, val;}p[maxn]; int n, m, val[maxn], ans[maxn], bl, l = 1, r, Val[maxn << 2]; il bool cmp1(pax a, pax b){return a.val < b.val;} il bool cmp(node a, node b){return (a.x / bl == b.x / bl) ? (a.y < b.y) : (a.x < b.x);} il void add(int k, int l, int r, int opt, int v) { Val[k] += opt; if(l == r && l == v) return; int mid = (l + r) >> 1; if(v <= mid) add(ls, l, mid, opt, v); else add(rs, mid + 1, r, opt, v); } il int query(int k, int l, int r, int v) { if(l == r) return l; int lmid = Val[ls], mid = (l + r) >> 1; if(v <= lmid) return query(ls, l, mid, v); else return query(rs, mid + 1, r, v - lmid); } il void add(int x){add(1, 1, n, 1, val[x]);} il void del(int x){add(1, 1, n, -1, val[x]);} int main() { file(a); n = read(), m = read(), bl = pow(n, 0.666); rep(i, 1, n) p[i].id = i, p[i].val = read(); rep(i, 1, m) q[i].id = i, q[i].x = read(), q[i].y = read(), q[i].k = read(); sort(p + 1, p + n + 1, cmp1); rep(i, 1, n) val[p[i].id] = i; sort(q + 1, q + m + 1, cmp); rep(i, 1, m) { while(r < q[i].y) add(++ r); while(r > q[i].y) del(r --); while(l < q[i].x) del(l ++); while(l > q[i].x) add(-- l); ans[q[i].id] = p[query(1, 1, n, q[i].k)].val; } rep(i, 1, m) printf("%d\n", ans[i]); return 0; } ```