题目概述

Hold the Line

解题报告

直接线段树套set是过不了的，我们需要一个小常数的做法。

考虑离线，这样第 $i$ 次事件插入 $x$ 位置时，就可以认为是 $i$ 时刻 $x$ 才出现，记录 $t_x=i$ 。第 $i$ 次事件区间查询时，其实就是找 $H$ 左右两边最近的在 $[L,R]$ 中时刻小于 $i$ 的 $x$ 位置。

如果不存在 $H$ 左右两边最近的这个条件，实际上就是一个单调栈问题。即，下标 $j<i$ 并且 $t_j\ge t_i$ 的 $j$ 是不优秀的，可以删除，这样就得到了一个单调栈，处理完前 $R$ 个下标，就可以在单调栈上二分查询找到 $[L,R]$ 的答案，这样常数是很小的。

结合一下 $H$ ，我们就可以得到一个值域线段树套单调栈，然后在线段树上二分的做法。位置从左到右考虑，加入第 $i$ 个位置时，在所有包含 $h_x$ 的线段树节点的单调栈中放入 $t_x$ ，并查询所有 $[L,i]$ ，查询方法就是在值域线段树上二分，并在对应节点的单调栈中二分查询。

示例程序

#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=500000,maxm=1000000,maxt=maxn<<2;

int te,n,m,c[maxn+5],res,ans[maxm+5];
int tp[maxm+5],L[maxm+5],R[maxm+5],H[maxn+5];
int ID[maxn+5];vector<int> e[maxn+5];
vector< pair<int,int> > stk[maxt+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[1<<16],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,1<<16,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
struct fastO{
    int si;char buf[1<<16];
    fastO() {si=0;}
    void putc(char ch){
        if (si==(1<<16)) fwrite(buf,1,si,stdout),si=0;
        buf[si++]=ch;
    }
    ~fastO() {fwrite(buf,1,si,stdout);}
}fo;
#define putc fo.putc
template<typename T> void writei(T x,char ch='\n'){
    static int len=0,buf[100];
    if (x<0) putc('-'),x=-x;
    do buf[len++]=x%10,x/=10; while (x);
    while (len) putc(buf[--len]+48);
    if (ch) putc(ch);
}
int Find(int x){
    int L=1,R=c[0];
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        c[mid]<=x?L=mid+1:R=mid-1;
    return R;
}
void Build(int l,int r,int p=1){
    stk[p].clear();
    if (l==r) return;
    int mid=l+(r-l>>1);
    Build(l,mid,p<<1);Build(mid+1,r,p<<1|1);
}
void Push(vector< pair<int,int> > &stk,pair<int,int> k){
    while (!stk.empty() && stk.back().sc>=k.sc) stk.pop_back();
    stk.push_back(k);
}
void Insert(int pos,pair<int,int> k,int l=1,int r=c[0],int p=1){
    Push(stk[p],k);
    if (l==r) return;
    int mid=l+(r-l>>1);
    pos<=mid?Insert(pos,k,l,mid,p<<1):Insert(pos,k,mid+1,r,p<<1|1);
}
bool check(vector< pair<int,int> > &stk,pair<int,int> k){
    if (stk.empty()) return false;
    if (k.fr>stk.back().fr) return false;
    int L=0,R=stk.size()-1;
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        k.fr<=stk[mid].fr?R=mid-1:L=mid+1;
    return stk[L].sc<k.sc;
}
void FindR(int L,int R,pair<int,int> k,int l=1,int r=c[0],int p=1){
    if (res) return;
    if (L==l && r==R){
        if (!check(stk[p],k)) return;
        if (l==r) {res=c[l];return;}
        int mid=l+(r-l>>1);
        check(stk[p<<1|1],k)?FindR(mid+1,R,k,mid+1,r,p<<1|1):FindR(L,mid,k,l,mid,p<<1);
        return;
    }
    int mid=l+(r-l>>1);
    if (R<=mid) FindR(L,R,k,l,mid,p<<1); else if (L>mid) FindR(L,R,k,mid+1,r,p<<1|1); else {
        FindR(mid+1,R,k,mid+1,r,p<<1|1);
        if (res) return;
        FindR(L,mid,k,l,mid,p<<1);
    }
}
void FindL(int L,int R,pair<int,int> k,int l=1,int r=c[0],int p=1){
    if (res) return;
    if (L==l && r==R){
        if (!check(stk[p],k)) return;
        if (l==r) {res=c[l];return;}
        int mid=l+(r-l>>1);
        check(stk[p<<1],k)?FindL(L,mid,k,l,mid,p<<1):FindL(mid+1,R,k,mid+1,r,p<<1|1);
        return;
    }
    int mid=l+(r-l>>1);
    if (R<=mid) FindL(L,R,k,l,mid,p<<1); else if (L>mid) FindL(L,R,k,mid+1,r,p<<1|1); else {
        FindL(L,mid,k,l,mid,p<<1);
        if (res) return;
        FindL(mid+1,R,k,mid+1,r,p<<1|1);
    }
}
int main(){
    for (readi(te);te;te--){
        readi(n);readi(m);c[0]=0;
        for (int i=1;i<=n;i++) e[i].clear(),ID[i]=0;
        for (int i=1;i<=m;i++){
            readi(tp[i]);
            if (tp[i]==1) readi(L[i]),readi(R[i]),readi(H[i]),e[R[i]].push_back(i);
            else readi(L[i]),readi(H[i]),ID[L[i]]=i,c[++c[0]]=H[i];
        }
        if (!c[0]){
            for (int i=1;i<=m;i++) if (tp[i]==1) writei(-1);
            continue;
        }
        sort(c+1,c+1+c[0]);c[0]=unique(c+1,c+1+c[0])-(c+1);
        Build(1,c[0]);
        for (int i=1;i<=n;i++){
            if (ID[i]) Insert(Find(H[ID[i]]),mp(i,ID[i]));
            for (auto q:e[i]){
                ans[q]=2e9;
                int pos=Find(H[q]);
                if (pos){
                    res=0;FindR(1,pos,mp(L[q],q));
                    if (res) ans[q]=min(ans[q],H[q]-res);
                }
                if (pos<c[0]){
                    res=0;FindL(pos+1,c[0],mp(L[q],q));
                    if (res) ans[q]=min(ans[q],res-H[q]);
                }
            }
        }
        for (int i=1;i<=m;i++) if (tp[i]==1) writei(ans[i]==2e9?-1:ans[i]);
    }
    return 0;
}