[线段树套单调栈] 2019-2020 ICPC Asia Hong Kong Regional Contest H.[Hold the Line]

线段树套单调栈

2019-2020 ICPC Asia Hong Kong Regional Contest H.​​Hold the Line​​

题目大意

你已经建造了一条由编号从到的战壕组成的防线，每条战壕最初都是空的。士兵们正在等待你的命令，每个士兵都有一个喜欢的射击高度。

随着战斗的进行，以下两个事件可能会发生。

• 一个拥有首选射击高度的士兵被派去驻守一个空的战壕。
• 一个有高度的敌人被发现，只有驻守在编号在和之间的战壕里的士兵可以射杀这个敌人。为了提高命中率，从而节省子弹，有必要选择一个首选射击高度尽可能接近敌人高度的士兵来射击敌人。你需要知道所选士兵的首选射击高度和敌人的高度之间的差异。

题目思路

非常妙的思路

分别将修改操作和询问操作离线，然后分别按照右端点排序。

然后以高度为下标建立权值线段树，然后将“最接近”转化为两次线段树上二分：求左侧最右和右侧最左，然后取差值最小值即可。

考虑如何检查合法性：由于在权值线段树上丢失了区间信息，因此二分时要检查合法性：我们对每个节点记录两个值：位置和时间戳。

那么对于任意两个节点状态，当时间戳且，那么第一个节点就可以被后者覆盖。因此对每个节点维护一个随递增且随递减的单调栈。检查合法性时在单调栈上二分查询是否存在且的节点即可。

注意此时查询的是最近的操作，而不再是具体的节点。比较抽象，但是很牛逼…

Code

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e6 + 10, INF = 1e17;
// int ans[N];

namespace ffastIO {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}

using ffastIO::read;

#define pii pair<int, int>
#define mkp make_pair
#define fir first
#define sec second

struct chang{ int h, id; };
struct query{ int l, h, id; };

vector<int> dh;
vector<query> que[N];
vector<chang> chg[N];

namespace SegTree{
    #define ls rt << 1
    #define rs rt << 1 | 1
    #define lson ls, l,
    #define rson rs, mid + 1,

    vector<pii> tree[N << 2]; 

    void build(int rt, int l, int r){
        tree[rt].clear();
        if(l == r) return;
        int mid = l + r >> 1;
        build(lson), build(rson);    
    }

    void update(int rt, int l, int r, int h, int pos, int val){
        while(tree[rt].size() && tree[rt].back().sec > val) tree[rt].pop_back();
        tree[rt].emplace_back(mkp(pos, val));
        if(l == r) return;
        int mid = l + r >> 1;
        if(mid >= h) update(lson, h, pos, val);
        else update(rson, h, pos, val);
    }

    bool check(int rt, int val, int pos){
        auto fnd = pii{val, 0};
        auto it = lower_bound(tree[rt].begin(), tree[rt].end(), fnd);
        if(it != tree[rt].end()) return (*it).second < pos;
        else return false;
    }

    int queryl(int rt, int l ,int r, int L, int R, int val, int pos){
        if(l > R || r < L) return INF;
        if(l == r) return check(rt, val, pos) ? l : INF * 2;
        if(l >= L && r <= R && !check(rt, val, pos)) return INF * 2; 
        int mid = l + r >> 1, res = INF * 2;
        if(res >= INF) res = min(res, queryl(lson, L, R, val, pos));
        if(res >= INF) res = min(res, queryl(rson, L, R, val, pos));
        return res;
    }
    
    int queryr(int rt, int l ,int r, int L, int R, int val, int pos){
        if(l > R || r < L) return -1;
        if(l == r) return check(rt, val, pos) ? l : -1;
        if(l >= L && r <= R && !check(rt, val, pos)) return -1; 
        int mid = l + r >> 1, res = -1;
        if(res < 0) res = max(res, queryr(rson, L, R, val, pos));
        if(res < 0) res = max(res, queryr(lson, L, R, val, pos));
        return res;
    }
}

#define SEGRG 1, 0, siz - 1

inline void solve(){
    dh.clear();
    int n = read(), m = read();
    for(int i = 1; i <= n; i++) chg[i].clear(), que[i].clear();
    for(int i = 1; i <= m; i++){
        int op = read();
        if(op == 0){
            int x = read(), h = read();
            chg[x].emplace_back(chang{h, i});
            dh.emplace_back(h);
        } else {
            int l = read(), r = read(), h = read();
            que[r].emplace_back(query{l, h, i});
            dh.emplace_back(h);
        }
    }
    sort(dh.begin(), dh.end());
    dh.erase(unique(dh.begin(), dh.end()), dh.end());
    auto get = [&](int x){ return lower_bound(dh.begin() , dh.end(), x) - dh.begin(); };
    int siz = dh.size();
    SegTree::build(SEGRG);
    vector<pii> ans;
    for(int i = 1; i <= n; i++){
        for(auto &[qh, id] : chg[i]){
            int h = get(qh);
            SegTree::update(SEGRG, h, i, id);
        }
        for(auto &[l, qh, id] : que[i]){
            int h = get(qh);
            int lans = SegTree::queryr(SEGRG, 0, h, l, id);
            int rans = SegTree::queryl(SEGRG, h + 1, siz - 1, l, id);
            int res = INF * 2;
            if(lans >= 0) res = min(res, dh[h] - dh[lans]);
            if(rans < INF) res = min(res, dh[rans] - dh[h]);
            if(res >= INF) res = -1;
            ans.emplace_back(mkp(id, res)); 
        }
    }
    sort(ans.begin(), ans.end());
    for(auto &[id, res] : ans) printf("%d\n", res);
}

signed main(){
    // ios_base::sync_with_stdio(false), cin.tie(0);
    int t = read();
    while(t--) solve();
    return 0;
}