洛谷P4632 [APIO2018] New Home 新家(动态开节点线段树 二分答案 扫描线 set)
题意
sol
这题没有想象中的那么难,但也绝对不简单。
首先把所有的询问离线,按照出现的顺序。维护时间轴来处理每个询问
对于每个询问\((x_i, y_i)\),可以二分答案\(mid\)。
问题转化为对于所有\(a_i \leqslant y_i \leqslant b_i\)的商店,\((x - mid, x + mid)\)内是否所有类型的商店都出现过
若都出现过,减小\(mid\),否则增大\(mid\)
现在有两个问题:
如何维护当前可行的所有商店,以及我们需要的信息
如何判断\((x - mid, x + mid)\)内是否所有类型的商店都出现过
显然问题1依赖于问题2
对于第二个问题,一种方法是直接树套树区间数颜色,另一个巧妙的方法是定义\(pre_i\)表示和\(i\)号位置类型相同的商店中,\(x\)坐标小于\(i\)的第一个位置
若\(mid\)是合法的,一定存在一个位置\(p \in (x + mid + 1, n)\)满足\(pre_p < x - mid\)
那么直接用线段树维护\(pre\)的最小值即可。
线段树应该动态开点,当然你也可以头铁写离散化然后就需要考虑各种边界问题。。
问题1实际上我们只需要维护好\(pre\)即可
一个显然的想法是直接开\(30w\)个set维护每个类型
加入 / 删除的时候只会影响到\(3\)个位置
时间复杂度:\(o(nlog^2n)\),单次询问的复杂度为\(o(logn)\)
需要注意一个细节,由于是在线段树上二分,所以二分的边界应该与线段树相同
#include<bits/stdc++.h> #define mit multiset<int>::iterator using namespace std; const int maxn = 3e5 + 10, l = 1e9, lim = (1 << 22) + 1; inline int read() { char c = getchar(); int x = 0, f = 1; 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; } int n, k, q, cnt, rt, ans[maxn]; multiset<int> op[maxn];//val of each type multiset<int> s[lim];// int mn[lim], ls[lim], rs[lim]; struct query { int ti, opt, x;// time type pos bool operator < (const query &rhs) const { return ti == rhs.ti ? opt < rhs.opt : ti < rhs.ti; } }q[maxn * 3 + 10]; int tot = 0; void erase(multiset<int> &s, int &val) { mit t = s.find(val); if(t != s.end()) s.erase(t); } void update(int k) { mn[k] = min(mn[ls[k]], mn[rs[k]]); } void insert(int &k, int l, int r, int x, int new, int old) { if(!k) k = ++tot; if(l == r) { if(new) s[k].insert(new); if(old) erase(s[k], old); mn[k] = (s[k].empty() ? l : *s[k].begin()); return ; } int mid = l + r >> 1; if(x <= mid) insert(ls[k], l, mid, x, new, old); else insert(rs[k], mid + 1, r, x, new, old); update(k); } int query(int x) { int l = 0, r = l, mid, now = rt, lim = l, ans; while(l < r) { int mid = l + r >> 1, mn = min(mn[rs[now]], lim); if((x > mid) || (mid - x < x - mn)) l = mid + 1, now = rs[now], ans = mid; else r = mid, now = ls[now], lim = mn; } return l - x; } n = read(); k = read(); q = read(); mn[0] = l; for(int i = 1; i <= n; i++) { int x = read(), t = read(), a = read(), b = read(); q[++cnt] = (query) {a, t, x}; q[++cnt] = (query) {b + 1, -t, x}; } for(int i = 1; i <= q; i++) { int x = read(), y = read(); q[++cnt] = (query) {y, n + i, x}; } sort(q + 1, q + cnt + 1); int now = 0;// now type num for(int i = 1; i <= k; i++) op[i].insert(l), op[i].insert(-l), insert(rt, 0, l, l, -l, 0); for(int i = 1; i <= cnt; i++) { int ty = q[i].opt; if(ty > n) ans[ty - n] = now < k ? - 1 : query(q[i].x); else if(ty > 0) { // add mit t = op[ty].upper_bound(q[i].x), r = t--; insert(rt, 0, l, *r, q[i].x, *t); insert(rt, 0, l, q[i].x, *t, 0); if(op[ty].size() == 2) now++; op[ty].insert(q[i].x); } else { ty = -ty; mit t = op[ty].upper_bound(q[i].x), r = t--; t--; insert(rt, 0, l, *r, *t, q[i].x); insert(rt, 0, l, q[i].x, 0, *t); erase(op[ty], q[i].x); if(op[ty].size() == 2) now--; } } for(int i = 1; i <= q; i++) printf("%d\n", ans[i]); return 0; }
上一篇: 2018-10-23 23:29:54 clanguage
下一篇: 洛谷P2312 解方程(暴力)