[Bzoj1171] 大sz的游戏

不怎么接触的标记永久化.

problem

  • N 个点, 另有一个参数 L
    每个点有一对参数 [l_ i , r _i ]

  • 如果点对 (i, j) 满足 0 ≤ j − i ≤ L,且 [l_ i , r_ i ][l _j , r_ j ] 有交集

    则从 ji 连一条有向边.

求每个点到 1 的最短路( N ≤ 5 × 10^5).

sol

不难想出一个n^2dp.

从最麻烦的入手, 考虑将判断线段交作为突破口.

  • 暴力: 将[l_i,r_i]的答案塞入线段树中所有满足对应区间是[l_i,r_i]子集的节点.

这样一来, 只要求\log n个节点中, 满足\text{dis}\leq L的答案min 就好了.

注意到输入的距离是严格递增的:

这启示我们在线段树每个节点维护一个单调队列.

这样一来\text{dis}的问题就解决了.

但是还有不足的是塞入的复杂度太高了.

  • 考虑线段树标记永久化.

维护2种单调队列: a,b

modify

  1. l=ql \text{ and } r=qr

    将该点塞入a

  2. 否则塞入b中.

query

  1. l=ql \text{ and } r=qr

    询问ba

  2. 否则询问a

不难发现会不重不漏枚举到所有有交的点.

Code

吐槽: 没有bzoj真难受.

#pragma GCC optimize(2)
#include 
using namespace std;
const int N = 2.5e5 + 50;

int n, L, ans, node, f[N], d[N], x[N], y[N];
list a[N * 2], b[N * 2];
vector g;

# define ls rt << 1
# define rs ls | 1

void query(int rt, int l, int r, int ql, int qr) {
    list &g = a[rt];
    while(!g.empty() && d[node] - d[g.front()] > L)
        g.pop_front();
    if(!g.empty()) ans = min(ans, f[g.front()] + 1);
    if(l == ql && r == qr) {
        list &g = b[rt];
        while(!g.empty() && d[node] - d[g.front()] > L)
            g.pop_front();
        if(!g.empty()) ans = min(ans, f[g.front()] + 1);
    }
    if(l == ql && r == qr) return ;
    int mid = l + r >> 1;
    if(qr <= mid) query(ls, l, mid, ql, qr);
    else if(mid + 1 <= ql) query(rs, mid + 1, r, ql, qr);
    else query(ls, l, mid, ql, mid), query(rs, mid + 1, r, mid + 1, qr);
}
void ins(int rt, int l, int r, int ql, int qr) {
    list &g = (l == ql && r == qr) ? a[rt] : b[rt];
    while(!g.empty() && f[g.back()] >= ans)
        g.pop_back();
    g.push_back(node);
    if(l == ql && r == qr) return ;
    int mid = l + r >> 1;
    if(qr <= mid) ins(ls, l, mid, ql, qr);
    else if(mid + 1 <= ql) ins(rs, mid + 1, r, ql, qr);
    else ins(ls, l, mid, ql, mid), ins(rs, mid + 1, r, mid + 1, qr);
}

int main() {
    scanf("%d%d", &n, &L);
    d[1] = 0;
    x[1] = -2e9, g.push_back(-2e9);
    y[1] = 2e9, g.push_back(2e9);
    for(int i = 2; i <= n; ++i) {
        scanf("%d%d%d", x + i, y + i, d + i);
        g.push_back(x[i]);
        g.push_back(y[i]);
    }
    sort(g.begin(), g.end());
    g.erase(unique(g.begin(), g.end()), g.end());
    for(int i = 1; i <= n; ++i) {
        ans = (i == 1) ? 0 : 1e9;
        x[i] = lower_bound(g.begin(), g.end(), x[i]) - g.begin() + 1;
        y[i] = lower_bound(g.begin(), g.end(), y[i]) - g.begin() + 1;
        node = i;
        query(1, 1, g.size(), x[i], y[i]);
        if(ans < 1e9) ins(1, 1, g.size(), x[i], y[i]);
        if(i > 1) printf("%d\n", f[i] = ans == 1e9 ? -1 : ans);
    }
    return 0;
}