#2585. 「APIO2018」新家
分析：
线段树+二分。
首先看怎样数颜色，正常的时候，离线扫一遍右端点，每次只记录最右边的点，然后查询左端点，这里不太行。这里只需要统计是否全出现过，pre[i]为这个颜色的上一个位置，那么这也就说明了pre[i]+1这段区间没出现过，所以要求[r+1,n]这段区间的最小的pre都要大于等于l。于是这就是线段树区间查询最小值了。
注意的是，每个点的pre有多个，每个叶子节点包含一个set，把所有的值插入进去，取最小值。用两个堆维护也可以，（取最小值，删除一个值）。
然后就可以二分一个长度，然后查询[x-len,x+len]这段区间是否都有所有的颜色就行了。复杂度$O(nlog^2n)$
一个log的做法，二分的过程放到了线段树上。
代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int N = ;
const int INF = 1e9; struct Node{
int opt, x, col, t;
Node() {}
Node(int a,int b,int c,int d) { opt = a, x = b, col = c, t = d; }
bool operator < (const Node &A) const {
return t == A.t ? opt > A.opt : t < A.t; // 如果时间相同，先加入，在询问，再删除
}
}A[N * ];
struct Heap{
priority_queue<int, vector<int>, greater<int> > q1, q2;
int size() { return q1.size() - q2.size(); }
void add(int x) { q1.push(x); }
void del(int x) { q2.push(x); }
int top() {
while (!q2.empty() && q1.top() == q2.top()) q1.pop(), q2.pop();
return q1.top();
}
// multiset<int> s;
// int size() { return s.size(); }
// void add(int x) { s.insert(x); }
// void del(int x) { s.erase(s.find(x)); }
// int top() { return *s.begin(); }
}H[N];
multiset<int> S[N];
int ans[N], Id[N * ], ls[N * ], rs[N * ], Mn[N * ];
int n, k, m, Index_Heap, Index_Tree, Root, Now_Col; void update(int l,int r,int &rt,int p,int u,int v) {
if (!rt) rt = ++Index_Tree;
if (l == r) {
if (!Id[rt]) Id[rt] = ++Index_Heap;
Heap &now = H[Id[rt]];
if (u) now.add(u);
if (v) now.del(v);
Mn[rt] = now.size() ? now.top() : INF;
return ;
}
int mid = (l + r) >> ;
if (p <= mid) update(l, mid, ls[rt], p, u, v);
else update(mid + , r, rs[rt], p, u, v);
Mn[rt] = min(Mn[ls[rt]], Mn[rs[rt]]);
}
void add(const Node &now) {
multiset<int> &s = S[now.col];
multiset<int> :: iterator r = s.upper_bound(now.x), l = r; l--;
update(, INF, Root, *r, now.x, *l);
update(, INF, Root, now.x, *l, );
if (s.size() == ) Now_Col ++;
s.insert(now.x);
}
void del(const Node &now) {
multiset<int> &s = S[now.col];
s.erase(s.find(now.x));
if (s.size() == ) Now_Col --;
multiset<int> :: iterator r = s.upper_bound(now.x), l = r; l--;
update(, INF, Root, *r, *l, now.x);
update(, INF, Root, now.x, , *l);
}
int Ask(int p) {
if (Now_Col != k) return -;
int l = , r = INF, now = Root, ans = INF;
while (l != r) { // 模拟在线段树上走的过程
int mid = (l + r) >> , tmp = min(ans, Mn[rs[now]]);
if (p <= mid && tmp + mid >= p + p) ans = tmp, r = mid, now = ls[now];
else l = mid + , now = rs[now];
}
return l - p;
}
int main() {
n = read(), k = read(), m = read();
Mn[] = INF;
for (int i = ; i <= k; ++i) // 初始往INF处加入k个-INF
S[i].insert(-INF), S[i].insert(INF), update(, INF, Root, INF, -INF, );
int tot = ;
for (int i = ; i <= n; ++i) {
int x = read(), t = read(), a = read(), b = read();
A[++tot] = Node(, x, t, a); A[++tot] = Node(-, x, t, b);
}
for (int i = ; i <= m; ++i) {
int x = read(), t = read();
A[++tot] = Node(, x, i, t);
}
sort(A + , A + tot + );
for (int i = ; i <= tot; ++i) {
if (A[i].opt == ) add(A[i]);
else if (A[i].opt == -) del(A[i]);
else ans[A[i].col] = Ask(A[i].x);
}
for (int i = ; i <= m; ++i) printf("%d\n",ans[i]);
return ;
}