「APIO2018新家」
题目描述
五福街是一条笔直的道路，这条道路可以看成一个数轴，街上每个建筑物的坐标都可以用一个整数来表示。小明是一位时光旅行者，他知道在这条街上，在过去现在和未来共有 \(n\)个商店出现。第 \(i\) 个商店可以使用四个整数 \(x_i, t_i, a_i, b_i\) 描述，它们分别表示：商店的坐标、商店的类型、商店开业的年份、商店关闭的年份。
小明希望通过时光旅行，选择一个合适的时间，住在五福街上的某个地方。他给出了一份他可能选择的列表，上面包括了 \(q\) 个询问，每个询问用二元组（坐标，时间）表示。第 \(i\) 对二元组用两个整数 \(l_i, y_i\) 描述，分别表示选择的地点 \(l_i\) 和年份 \(y_i\)。
现在，他想计算出在这些时间和地点居住的生活质量。他定义居住的不方便指数为：在居住的年份，离居住点最远的商店类型到居住点的距离。类型 \(t\) 的商店到居住点的距离定义为：在指定的年份，类型 \(t\) 的所有营业的商店中，到居住点距离最近的一家到居住点的距离。我们说编号为 \(i\) 的商店在第 \(y\) 年在营业当且仅当 \(a_i \leq y \leq b_i\) 。注意，在某些年份中，可能在五福街上并非所有 \(k\) 种类型的商店都有至少一家在营业。在这种情况下，不方便指数定义为 \(−1\)。你的任务是帮助小明求出每对（坐标，时间）二元组居住的不方便指数。
解题思路 :
终于做贺完了2018的APIO纪念一下=w=
这个题好厉害啊，想了好久还是只会 \(nlog^3n\) ，于是就看了 kczno1的题解 ，然而还是细节好多。
考虑要使得区间中不同元素的个数等于元素种类数，容易想到通过记录每个位置的前驱将问题转化为数点。这样二分答案以后就可以通过求一个区间前驱 \(\min\) 来判断了，复杂度 \(O(nlog^2n)\)。
\(O(nlogn)\) 的做法点开链接就可以看到了，具体实现还要用一个multiset维护前驱，一个multiset维护每个叶子节点的极值，找到最远的出现第二次的元素后答案就是到左右两边的较短距离。
/*program by mangoyang*/
#include<bits/stdc++.h>
#define inf ((int)(1e9))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
int f = 0, ch = 0; x = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
if(f) x = -x;
}
const int N = 1000005;
multiset<int> s[N];
int Ans[N], d[N], pre[N], bef[N], len, cnt, tot, n, k, m;
namespace Seg{
#define lson (u << 1)
#define rson (u << 1 | 1)
multiset<int> p[N]; int mn[N<<2];
inline void modify(int u, int l, int r, int pos, int x){
if(l == r){
if(x > 0) p[l].insert(x - 1);
else p[l].erase(p[l].find(-1 - x));
mn[u] = p[l].empty() ? inf : bef[*(p[l].begin())];
return;
}
int mid = l + r >> 1;
if(pos <= mid) modify(lson, l, mid, pos, x);
else modify(rson, mid + 1, r, pos, x);
mn[u] = min(mn[lson], mn[rson]);
}
inline int solve(int u, int l, int r, int x, int now){
if(l == r) return min(bef[l] - x, x - min(now, mn[u]));
int mid = l + r >> 1;
if(x > bef[mid])
return solve(rson, mid + 1, r, x, now);
int tmp = min(mn[rson], now);
if(tmp + bef[mid] + 1 <= 2 * x)
return solve(rson, mid + 1, r, x, now);
return solve(lson, l, mid, x, tmp);
}
inline void build(int u, int l, int r){
if(l == r){
p[l].insert(len+1);
if(l == len + 1)
for(int i = 1; i <= k; i++) p[l].insert(0);
mn[u] = bef[*(p[l].begin())];
return;
}
int mid = l + r >> 1;
build(lson, l, mid), build(rson, mid + 1, r);
mn[u] = min(mn[lson], mn[rson]);
}
}
struct Node{ int op, t, x, y; } q[N];
inline bool cmp(const Node &A, const Node &B){
return (A.t == B.t) ? (A.op < B.op) : (A.t < B.t);
}
inline void add(int pos, int x){
static multiset<int>::iterator it;
it = s[x].lower_bound(pos);
if(it != s[x].end()){
Seg::modify(1, 1, len + 1, *it, it == s[x].begin() ? -1 : (--it, -(*it++) - 1));
Seg::modify(1, 1, len + 1, *it, (pos + 1));
}
int tmp = (it == s[x].begin()) ? 1 : (*(--it) + 1);
Seg::modify(1, 1, len + 1, pos, tmp);
if(s[x].size() == 1) tot++;
s[x].insert(pos);
}
inline void del(int pos, int x){
static set<int>::iterator it;
it = s[x].lower_bound(pos);
if(it == s[x].begin()) Seg::modify(1, 1, len + 1, pos, -1);
else Seg::modify(1, 1, len + 1, pos, -(*(--it) + 1));
s[x].erase(s[x].find(pos));
it = s[x].lower_bound(pos);
if(it != s[x].end()){
Seg::modify(1, 1, len + 1, *it, -pos - 1);
Seg::modify(1, 1, len + 1, *it, it == s[x].begin() ? 1 : (--it, (*it++) + 1));
}
if(s[x].size() == 1) tot--;
}
int main(){
read(n), read(k), read(m);
for(int i = 1, x, t, a, b; i <= n; i++){
read(x), read(t), read(a), read(b);
q[++cnt] = (Node){2, a, x, t};
q[++cnt] = (Node){1, b + 1, x, t};
d[++len] = x;
}
for(int i = 1, x, y; i <= m; i++){
read(x), read(y);
q[++cnt] = (Node){3, y, x, i};
d[++len] = x;
}
sort(d + 1, d + len + 1);
len = unique(d + 1, d + len + 1) - d - 1;
bef[len+1] = inf, bef[0] = -inf;
sort(q + 1, q + cnt + 1, cmp);
for(int i = 1; i <= cnt; i++){
int tmp = lower_bound(d + 1, d + len + 1, q[i].x) - d;
bef[tmp] = q[i].x, q[i].x = tmp;
}
Seg::build(1, 1, len + 1);
for(int i = 1; i <= k; i++) s[i].insert(len+1);
for(int i = 1; i <= cnt; i++){
if(q[i].op == 2) add(q[i].x, q[i].y);
if(q[i].op == 1) del(q[i].x, q[i].y);
if(q[i].op == 3){
if(tot < k) Ans[q[i].y] = -1;
else Ans[q[i].y] = Seg::solve(1, 1, len + 1, bef[q[i].x], inf);
}
}
for(int i = 1; i <= m; i++) printf("%d\n", Ans[i]);
return 0;
}