P4632 [APIO2018] 新家

思路

首先有一个比较典的转化，因为本题中，有坐标和时间两种限制，于是考虑离线下来，按照时间依次进行操作。

我们可以考虑二分答案 $len$ 则 check 函数就是判断 $[x - len,x + len]$ 区间中是否所有 $k$ 中店铺都出现过。

有一个比较巧妙的方法，记录每一种店铺上次出现的位置 $pre_i$。

这个如果在 $i > x + len$ 且满足 $pre_i < x - len$，则这种情况一定不合法。原因比较简单，如果这种店铺上一次出现的位置小于 $x - len$，说明在 $[x - len,x + len]$ 中没有出现。

但是单单是这个条件是不够的，因为有可能有一些类型的店铺并没有在大于 $x + len$ 的区间中出现。那么考虑对于每一种店铺初始状态时添加两个哨兵 $\pm\infty$。

这样下来，如果有种类型的店铺没有出现过将会由 $+\infty$ 的哨兵，返回其前驱，减少了大量的分讨。

那么我们只需要快速查询大于 $x + len$ 的前驱最小值，这显然是可以通过线段树 $\Theta(\log n)$ 查询的。那么总时间复杂度是 $\Theta(n \log^2 n)$ 的，比较紧张，但是将二分直接转到线段树上二分是 $\Theta(n \log n)$ 的了。

Code

#include <bits/stdc++.h>
#define re register

using namespace std;

const int N = 1e6 + 10,M = 3e5 + 10,inf = 1e9 + 10;
int n,m,q,rt,num;
int ans[N];
multiset<int> pre[N];

struct Query{
    int op,x,tim,ty;

    bool friend operator <(const Query &a,const Query &b){
        if (a.tim != b.tim) return a.tim < b.tim;
        return a.op < b.op;
    }
};
vector<Query> Q;

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

struct seg{
    #define ls(u) (tr[u].l)
    #define rs(u) (tr[u].r)
    #define st(u) (tr[u].st)

    int idx;

    struct node{
        int l,r,Min;
        multiset<int> st;
    }tr[M * 30];

    inline void pushup(int u){
        tr[u].Min = min(tr[ls(u)].Min,tr[rs(u)].Min);
    }

    inline void insert(int &u,int l,int r,int x,int k,int falg){
        if (!u) u = ++idx;
        if (l == r){
            if (falg == 1) st(u).insert(k);
            else st(u).erase(st(u).find(k));
            if (st(u).empty()) tr[u].Min = inf;
            else tr[u].Min = (*st(u).begin());
            return;
        }
        int mid = l + r >> 1;
        if (x <= mid) insert(ls(u),l,mid,x,k,falg);
        else insert(rs(u),mid + 1,r,x,k,falg);
        pushup(u);
    }

    inline int query(int x){
        if (num < m) return -1;
        int u = rt,l = 1,r = inf,lst = inf;
        // 由于当 u 向左递归时右端点会向左移动，原本能取到的最小值可能取不到了，因此用 lst 记录一下
        while (l < r){
            int mid = l + r >> 1;
            int Min = min(lst,tr[rs(u)].Min);
            if (mid < x || Min < 2 * x - mid) u = rs(u),l = mid + 1;
            else lst = Min,u = ls(u),r = mid;
        }
        return l - x;
    }

    #undef ls
    #undef rs
    #undef st
}T;

int main(){
    T.tr[0].Min = inf;
    n = read(),m = read(),q = read();
    for (re int i = 1;i <= m;i++){
        pre[i].insert(-inf); pre[i].insert(inf);
        T.insert(rt,1,inf,inf,-inf,1);
    }
    for (re int i = 1;i <= n;i++){
        int x,ty,l,r;
        x = read(),ty = read(),l = read(),r = read();
        Q.push_back({1,x,l,ty}); Q.push_back({2,x,r + 1,ty});
    }
    for (re int i = 1;i <= q;i++){
        int x,tim;
        x = read(),tim = read();
        Q.push_back({3,x,tim,i});
    }
    sort(Q.begin(),Q.end());
    for (auto p:Q){
        if (p.op == 1){
            auto jt = pre[p.ty].lower_bound(p.x); auto it = prev(jt);
            T.insert(rt,1,inf,p.x,*it,1); T.insert(rt,1,inf,*jt,*it,2); T.insert(rt,1,inf,*jt,p.x,1);
            if (pre[p.ty].size() == 2) num++;
            pre[p.ty].insert(p.x);
        }
        else if (p.op == 2){
            auto jt = pre[p.ty].lower_bound(p.x); auto it = prev(jt); jt = next(jt);
            T.insert(rt,1,inf,*jt,p.x,2); T.insert(rt,1,inf,p.x,*it,2); T.insert(rt,1,inf,*jt,*it,1);
            pre[p.ty].erase(pre[p.ty].find(p.x));
            if (pre[p.ty].size() == 2) num--;
        }
        else ans[p.ty] = T.query(p.x);
    }
    for (re int i = 1;i <= q;i++) printf("%d\n",ans[i]);
    return 0;
}