题解：AT_arc196_d [ARC196D] Roadway

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

第一眼，对每个区间记 $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)$ 。

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

树套树代码

CPP

#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
*/

题解：AT_arc196_d [ARC196D] Roadway

文章操作

相关推荐

评论

题解：AT_arc196_d [ARC196D] Roadway