题解：P11210 『STA - R8』强制在线动态二维数点

· · 题解

奶龙。

什么时候支配对板子也 ad-hoc 了。

题意转化足够清楚，不再赘述。

放松条件，考虑支配区间：

将区间按照 l_i 升序排序，则 r_i 为 \operatorname{sufmin}\{r_i\}。

对于一次询问 (L,R)：

所以首先找到 l 下标，维护一下区间 \min\{r_i\}，然后可以线段树二分找到最后的 \operatorname{sufmin}\{r_p\}\le R，接下来 [l,p] 内的支配线段都是可能的答案。

不需要考虑不支配的，直接区间 \min\{r_i-l_i\} 即可。

维护两颗线段树还是太难绷了，直接一颗二分一下就好了。

所有维护都是简易的。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
const int M=2e6+5;
const int inf=1e8+7;
multiset<int>S[N];
namespace sgt{
#define ls (o<<1)
#define rs (ls|1)
#define mid ((l+r)>>1)
    int L[M],R[M];
    int mnr[M],mn1[M];
    void pushup(int o){
        mnr[o]=min(mnr[ls],mnr[rs]);
        mn1[o]=min(mn1[ls],mn1[rs]);
    }
    void build(int o,int l,int r){
        L[o]=l,R[o]=r;
        if(l==r){
            mnr[o]=*S[l].begin(),mn1[o]=(*S[l].begin())-l;
            return;
        }
        build(ls,l,mid),build(rs,mid+1,r);
        pushup(o);
    }
    void update(int o,int pos){
        int l=L[o],r=R[o];
        if(l==r){
            mnr[o]=*S[l].begin(),mn1[o]=(*S[l].begin())-l;
            return;
        }
        update(pos<=mid?ls:rs,pos);
        pushup(o);
    }
    int find(int lim){//最后的 sufmin(r<=lim) 的点
        int o=1,l,r,res=0;
        while(1){
            l=L[o],r=R[o];
            if(mnr[o]>lim)break;
            if(l==r){res=l;break;}
            o=(mnr[rs]<=lim?rs:ls);
        }
        return res;
    }
    int qrymn(int o,int lt,int rt){
        int l=L[o],r=R[o];
        if(l>=lt&&r<=rt)return mn1[o];
        int res=inf;
        if(lt<=mid)res=min(res,qrymn(ls,lt,rt));
        if(rt> mid)res=min(res,qrymn(rs,lt,rt));
        return res;
    }
#undef ls
#undef rs
#undef mid
}
int Qry(int L,int R){
    int l=L,r=sgt::find(R);
    if(l>r)return 0;
    int res=sgt::qrymn(1,l,r);
    return (res==inf?0:res);
}
int xs[N],ys[N];
int n,q;
void init(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
        S[i].clear(),S[i].insert(i+inf);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&ys[i],&xs[i]);
        S[xs[i]].insert(ys[i]);
    }
    sgt::build(1,1,n);

}
void work(){
    int Ans=0;
    int x,y,i;
    char ops;scanf("\n");
    while(q--){
        scanf("%c",&ops);
        if(ops=='U'){
            scanf("%d%d%d\n",&i,&y,&x);
            i^=Ans,x^=Ans,y^=Ans;
            S[xs[i]].erase(S[xs[i]].find(ys[i]));
            sgt::update(1,xs[i]);
            xs[i]=x,ys[i]=y;
            S[xs[i]].insert(ys[i]);
            sgt::update(1,xs[i]);
        }
        if(ops=='Q'){
            scanf("%d%d\n",&x,&y);
            x^=Ans,y^=Ans;
            Ans=Qry(x,y);
            printf("%d\n",Ans);
        }
    }
}
int main(){
    init();
    work();
    return 0;
}