题解：AT_arc196_d [ARC196D] Roadway

Albert_van · 2025-10-17 16:28:07 · 题解

题，为啥这么久没人写题解来着。结论题的核心思路：必要条件逼近，充分性证明口胡。 下面阐明想到本题结论的动态过程。

• 第一眼，对每个区间记 l_i=\min(s_i,t_i),r_i=\max(s_i,t_i)，那么这些开区间 (l_i,r_i) 相互之间要么相离、要么严格包含。否则会出现对一段区间边权加和正负性要求的矛盾。

  i.e. \forall (l_i,r_i),(l_j,r_j) 满足 l_i\le l_j，均有 l_i<l_j<r_j<r_i 或者 r_i\le l_j。①

• 记 (s_i,t_i) 的颜色 =[s_i<t_i]，上述条件实际上只对同色 (l_i,r_i) 之间生效。考虑对边权求前缀和 v，颜色 1 要求中段 v> 两端点，0 则要求中段 v< 两端点，等效于将 v 分层，而两种颜色对 v 的分层恰好反向。

• 猜想已经充分，然而并非，两种颜色都同时要求 v(s_i)=v(t_i)，因此在端点处有若干边界条件，即 l_i\ne l_j\land r_i\ne r_j 的限制对 i,j 不同色的情况也适用。此外，s_i=t_j,s_j=t_i 同样不成立。综合起来即，对于不同色的 i,j，s_i\ne t_j，且 t_i\ne s_j。②

• 往下推不动了， 再猜想充分，构造发现确实充分，在规避掉异色的端点冲突后，唯一的端点碰撞是尾尾相接或头头相接，等效于确定一个 v 的等价类；而端点不见面的情况下，两个颜色的偏序限制不可能发生冲突，只需要按照偏序关系分层即可。

最终只需要判断 ①②，双指针，判断 ② 容易，判断 ① 要求维护区间集合支持插入删除查询当前是否满足“分层”条件，直接维护不满足条件的 (l_i,r_i)(l_j,r_j) 对数，插入删除即二维数点，树套树完成。

但是官解指出：

We need to perform insertions and removals of intervals to a set and test whether the current set is laminar; this can be done with Zobrist hashing. To compute the XOR of an interval, we may use a BIT. The total complexity is O((N+M)\log N +Q)。

不理解随机异或哈希咋做的，会的在下面叫一声。

:::success[树套树代码]

#include <cstdio>
#include <random>
#include <vector>

using namespace std;

const int N=414514;int n;

mt19937 rnd;

class DS{
    struct node{
        int v,s,ls,rs;unsigned pr;
        #define v(x) t[x].v
        #define s(x) t[x].s
        #define ls(x) t[x].ls
        #define rs(x) t[x].rs
        #define pr(x) t[x].pr
    }t[N*20];int tot;
    void upd(int x){s(x)=s(ls(x))+s(rs(x))+1;}
    void div(int u,int &x,int &y,int k){
        if(!u) return x=y=0,void();
        if(v(u)<=k) x=u,div(rs(u),rs(u),y,k);
        else y=u,div(ls(u),x,ls(u),k);
        upd(u);
    }
    int mrg(int x,int y){
        if(!x||!y) return x|y;
        if(pr(x)<pr(y)){
            rs(x)=mrg(rs(x),y);
            upd(x);return x;
        }else{
            ls(y)=mrg(x,ls(y));
            upd(y);return y;
        }
    }
    int nnd(int k){return t[++tot]=(node){k,1,0,0,rnd()},tot;}
    void ist(int& rt,int k){
        int x,y;div(rt,x,y,k);
        rt=mrg(mrg(x,nnd(k)),y);
    }
    void dlt(int& rt,int k){
        int x,y,z;div(rt,x,z,k);div(x,x,y,k-1);
        rt=mrg(mrg(x,mrg(ls(y),rs(y))),z);
    }
    int qry(int& rt,int l,int r){
        int x,y,z;div(rt,x,z,r);div(x,x,y,l-1);
        int e=s(y);rt=mrg(mrg(x,y),z);
        return e;
    }
    #undef ls
    #undef rs
    int o[N<<2];
    #define ls(x) (x<<1)
    #define rs(x) (x<<1|1)
    void upd(int u,int ln,int rn,int p,int q,bool i){
        i?ist(o[u],q):dlt(o[u],q);
        if(ln==rn) return ;
        int mid=ln+rn>>1;
        if(p<=mid) upd(ls(u),ln,mid,p,q,i);
        else upd(rs(u),mid+1,rn,p,q,i);
    }
    int qry(int u,int ln,int rn,int l,int r,int p,int q){
        if(l<=ln&&rn<=r) return qry(o[u],p,q);
        int mid=ln+rn>>1,e=0;
        if(l<=mid) e+=qry(ls(u),ln,mid,l,r,p,q);
        if(r>mid) e+=qry(rs(u),mid+1,rn,l,r,p,q);
        return e;
    }
    public:int O;
    void del(int l,int r){
        upd(1,1,n,l,r,0);
        O-=qry(1,1,n,l,r-1,r,n)+qry(1,1,n,1,l,l+1,r);
    }
    void ins(int l,int r){
        O+=qry(1,1,n,l,r-1,r,n)+qry(1,1,n,1,l,l+1,r);
        upd(1,1,n,l,r,1);
    }
}F[2];

bool f[N];int l[N],r[N],sr[N],tr[N],sl[N],tl[N],cic;

void del(int i){
    cic-=(f[i]&&!--sr[l[i]]&&tl[l[i]])
        +(f[i]&&!--tr[r[i]]&&sl[r[i]])
        +(!f[i]&&!--tl[l[i]]&&sr[l[i]])
        +(!f[i]&&!--sl[r[i]]&&tr[r[i]]);
    F[f[i]].del(l[i],r[i]);
}

void ins(int i){
    cic+=(f[i]&&!(sr[l[i]]++)&&tl[l[i]])
        +(f[i]&&!(tr[r[i]]++)&&sl[r[i]])
        +(!f[i]&&!(tl[l[i]]++)&&sr[l[i]])
        +(!f[i]&&!(sl[r[i]]++)&&tr[r[i]]);
    F[f[i]].ins(l[i],r[i]);
}

bool ans[N];

struct qry{int e,id;};vector<qry> Q[N];

int main()
{
    int m,q;scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;++i){
        scanf("%d%d",l+i,r+i);
        if(!(f[i]=l[i]<r[i])) swap(l[i],r[i]);
    }
    for(int i=1,e,o;i<=q;++i) scanf("%d%d",&e,&o),Q[o].push_back({e,i});
    ins(1);for(int R=1,L=1;;ins(++R)){
        while(cic||F[0].O||F[1].O) del(L++);
        for(auto[e,id]:Q[R]) ans[id]=e>=L;
        if(R==m) break;
    }
    for(int i=1;i<=q;++i) puts(ans[i]?"Yes":"No");
}
/*
114514 5 1
1 4
2 5
3 5
1 2
2 4

3 5
*/

:::