BZOJ 3110 很早就想写的试炼场题。 不会整体二分啊呜呜呜,只能写写树套树。 有一个trick就是外层使用一个权值线段树,把位置作为下标的线段树放在内层,这样子的话我们在查询$k$大的时候就可以直接在外层线段树上一边走一边二分。 注意我们查询的是第$k$大不是第$k$小,所以我们在走的时候要观察右子树的权值和$k$的关系。 内层可以动态开点防mle,注意在打标记下传的时候要先给左右儿子赋值。 挺卡常的。 时间复杂度$O(nlog^2n)$。 Code: #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int N = 5e4 5; int n, qn, mn, tot = 0; ll val[N]; struct Querys { int type, l, r; ll k; } q[N]; template <typename T> inline void read(T &X) { X = 0; char ch = 0; T op = 1; for(; ch > '9'|| ch < '0'; ch = getchar()) if(ch == '-') op = -1; for(; ch >= '0' && ch <= '9'; ch = getchar()) X = (X << 3) (X << 1) ch - 48; X *= op; } namespace SegT { struct Node { int lc, rc, tag; ll sum; } s[N * 400]; int root[N << 2], nodeCnt = 0; #define lc(p) s[p].lc #define rc(p) s[p].rc #define sum(p) s[p].sum #define tag(p) s[p].tag #define mid ((l r) >> 1) inline void up(int p) { if(!p) return; sum(p) = sum(lc(p)) sum(rc(p)); } inline void down(int p, int l, int r) { if(!tag(p)) return; if(!lc(p)) lc(p) = nodeCnt; if(!rc(p)) rc(p) = nodeCnt; sum(lc(p)) = 1LL * tag(p) * (mid - l 1), tag(lc(p)) = tag(p); sum(rc(p)) = 1LL * tag(p) * (r - mid), tag(rc(p)) = tag(p); tag(p) = 0; } void ins(int &p, int l, int r, int x, int y) { if(!p) p = nodeCnt; if(x <= l && y >= r) { tag(p); sum(p) = 1LL * (r - l 1); return; } down(p, l, r); if(x <= mid) ins(lc(p), l, mid, x, y); if(y > mid) ins(rc(p), mid 1, r, x, y); up(p); } ll getSum(int p, int l, int r, int x, int y) { if(!p) return 0LL; if(x <= l && y >= r) return sum(p); down(p, l, r); ll res = 0LL; if(x <= mid) res = getSum(lc(p), l, mid, x, y); if(y > mid) res = getSum(rc(p), mid 1, r, x, y); return res; } void modify(int p, int l, int r, int x, int y, int v) { ins(root[p], 1, n, x, y); if(l == r) return; if(v <= mid) modify(p << 1, l, mid, x, y, v); else modify(p << 1 | 1, mid 1, r, x, y, v); } int query(int p, int l, int r, int x, int y, ll k) { if(l == r) return l; ll now = getSum(root[p << 1 | 1], 1, n, x, y); if(now >= k) return query(p << 1 | 1, mid 1, r, x, y, k); else return query(p << 1, l, mid, x, y, k - now); } } using namespace SegT; int main() { read(n), read(qn); for(int i = 1; i <= qn; i ) { read(q[i].type), read(q[i].l), read(q[i].r), read(q[i].k); if(q[i].type == 1) val[ tot] = q[i].k; } sort(val 1, val tot 1); tot = unique(val 1, val 1 tot) - val - 1; mn = tot; for(int i = 1; i <= qn; i ) { if(q[i].type == 1) { int v = lower_bound(val 1, val 1 tot, q[i].k) - val; modify(1, 1, mn, q[i].l, q[i].r, v); } else printf("%lld\n", val[query(1, 1, mn, q[i].l, q[i].r, q[i].k)]); } return 0; }View Code ? 来源:http://www./content-4-30001.html |
|