做题笔记 - 数据结构 1

Bridge(ICPC 2017 Shenyang)

场切的最难题，纪念一下。

我们称形如 $(x,y)-(x,y+1)$ 的边为 横边，形如 $(0,y)-(1,y)$ 的边为 竖边。不难发现如果在 $(y,y+1)$ 之间的两条竖边有一条断掉了，那么另外一条必然为桥。

扩展一下，对于最靠近任意一个 $y$ 左边的横边 $L$ 和最靠近 $y+1$ 右边的横边 $R$ 所代表的区间 $[L,R]$ 中的所有横边，断边的数量最多只能有一条，否则图不连通。当断边数为 $0$ 时，所有边都不是桥边，因为会成一个 $[L,R]$ 环；当断边数为 $1$ 时，桥边的数量为 $2(R-L)-1$。

这下我们可以快速判断横边是否为桥了。接下来是竖边。设存在竖边 $x$，靠近的最左、右竖边分别为 $L,R$，那么竖边 $x$ 为桥边的充要条件是 $[L,x]$ 和 $[x,R]$ 中的所有横边中各有一条是断边，否则成环就不是桥边了。

综上所述，我们需要维护所有的竖边和快速求区间横边数量。分别用 $\text{set}$ 和 $\text{Fenwick Tree}$ 维护即可。

set<int>s;
int getL(int x){ // 找到左侧最近竖边
	auto it=s.lower_bound(x);--it;
	return *it;
}
int getR(int x){ // 找到右侧最近竖边
	auto it=s.upper_bound(x);
	return *it;
}
int query1(int x){ // 查询 x 所代表的竖边是否为桥边
	if(x==1||x==n)return 0;
	int L=getL(x),R=getR(x);
	if(!query_bit(L,x-1))return 0;
	if(!query_bit(x,R-1))return 0;
	return 1; // 当且仅当 [L,x],[x,R] 中不含横边断边才不会成环
}
int query2(int l,int r){ // 查区间 [L,R] 中的桥边数量，包括所有横边竖边
	int res=0;
	res+=query1(l); // 别忘记加上竖边贡献
	res+=query1(r);
	if(query_bit(l,r-1))res+=(r-l)*2-1;
	return res;
}
void solve(){
	n=read()+2,m=read(); // 加 0 和 n+1 两个虚拟竖边特殊点，防止查 s 时越界报错
	init_bit();
	add_bit(1,1),add_bit(n-1,1); // 连通 (0,1) 和 (n,n+1) 横边
	s.clear();
	REP(i,1,n)s.insert(i);
	int res=0; // 答案
	REP(i,1,m){
		int tp=read(),x1=read(),y1=read()+1,x2=read(),y2=read()+1;
		if(y1>y2)swap(y1,y2);
		int L=getL(y2),R=getR(y1);
		if(tp==1){ // 加边
			if(x1==x2){ // 加横边，会影响一个极小区间
				res-=query2(L,R);
				add_bit(y1,1);
				res+=query2(L,R);
			}else{ // 加竖边，会影响两个左右极小区间
				res-=query2(L,R);
				s.insert(y1);
				res+=query2(L,y1);
				res+=query2(y1,R);
				res-=query1(y1);
			}
		}else{ // 断边，反之同理
			if(x1==x2){
				res-=query2(L,R);
				add_bit(y1,-1);
				res+=query2(L,R);
			}else{
				res-=query2(L,y1);
				res-=query2(y1,R);
				res+=query1(y1);
				s.erase(s.find(y1));
				res+=query2(L,R);
			}
		}
		writeln(res);
	}
}

那一年的秘密基地(SCCPC 2026)

典中典小 DS 题。

拆分成两个问题。一个问题是静态问题，另外一个问题是动态询问两个点的贡献。

考虑对于二元组 $(i,j)(i\lt j)$，会对哪些节点产生 $1$ 的贡献。先随便找一个点 $1$ 作为根。然后分析 $i$ 和 $j$ 的位置关系。

第一种情况，$a_i$ 为 $a_j$ 的祖先或同祖先的子孙。如图 A-1，这里 $a_i=4,a_j=9$。$f$ 权值加 $1$ 仅对 $\text{Sub 9}$ 即以 $9$ 号节点为根的子树有生效。不难发现实际在 dfn 序列上是一段区间，即只需要执行 dfn 序列区间 $+1$ 即可。

第二种情况，$a_i$ 为 $a_j$ 的子孙。如图 A-2，这里 $a_i=9,a_j=4$。注意到实际上是对于除了以 $7$ 号节点为根的以外的子树的节点，其余节点均有贡献。这里 $7$ 号节点是 $9$ 的祖先且深度与 $4$ 号节点仅差 $1$。同样考虑在 dfn 上的表现，即除了 $[in_7,out_7]$ 区间其余区间都有 $+1$ 的贡献。

【子问题 1】

这里是静态问题，如果考虑每个有序二元组 $(i,j)$ 显然不行，我们可以考虑只枚举 $j$ 这一维，然后把 $i$ 这维的信息整合在一起统计。

对于所有 $a_i$ 为以 $a_j$ 的子树的节点，设 $a_i$ 的 $dep_{a_i}-dep_{a_j}-1$ 级祖先为 $u$，则会为 $[1,in_u)$ 和 $(out_u,n]$ 两个区间产生 $+1$ 的贡献。为了整合所有 $u$ 相同的节点 $a_i$，可以用树状数组去维护；对于要求最小的危险值以及区间 $+1$ 的贡献，可以用一个线段树去支持全局 $\min$ 和区间加的操作。

【子问题 2】

交换 $a_i,a_{i+1}$，影响的只是有序对 $(i,i+1)$。根据子问题前的两种情况分类讨论 $a_i,a_{i+1}$ 的位置关系，同样用线段树维护。

Celester 2

来源：AT_abc464_g

难度：2592

感觉这题用反悔贪心做的真的牛完了。我是一个比较蠢的选手，所以这篇题解还是大家喜闻乐见的闵可夫斯基和 + 分治优化 DP。

题目要输出的是改 $x$ 个位置最多能获得多少个 $\text{RS}$。这不一眼 $\Theta(n^2)$，但是似乎没有什么前途。所以交换两维，对偶一下即询问获得 $x$ 个 $\text{RS}$ 最少需要改多少个位置。然后不难证明这个这个函数是单调不减且下凸的（好吧其实我并不会怎么严格证明，但由于这题可以给出最小费用最大流建模，同时可以用来证明函数凸性和反悔贪心正确性）。

关于 DP 状态，处理两个分治区间合并的时候，要关注可能左区间的最后一个元素为 $\text{R}$ 且右区间的最后一个元素为 $\text{S}$ 时，会贡献一个新的 $\text{RS}$。所以设计如下的 DP 状态：

$$f_{l,r,i,0/1,0/1}$$

表示区间 $[l,r]$ 中至少存在 $i$ 个 $\text{RS}$ 且左右端点分别为 $\text{R/S}$ 和 $\text{R/S}$ 最少需要更改的位置数。记得 $l=r$ 且两个 $0/1$ 状态相反时是没有意义的，要特判。

然后用 $\text{vector}$ 维护每个分治区间的函数，合并两个函数的时候根据函数凸性双指针加入，合并的复杂度是线性的。分治共有 $\log$ 层，所以复杂度是 $\Theta(n\log n)$。

vector<int>merge(vector<int>a,vector<int>b,int len,int dl){ // dl=1 时中间可以贡献一个新的 RS，为 -1 时无意义
	vector<int>f(len+1,inf);
	if(dl==-1)return f;
	PER(i,a.size()-1,1)a[i]-=a[i-1];
	PER(i,b.size()-1,1)b[i]-=b[i-1];
	int p=0,q=0,i=dl;
	f[dl]=a[p]+b[q];
	while(p+1<a.size()&&q+1<b.size()&&i+1<=len){ // 根据函数凸性，双指针合并函数
		++i;
		if(a[p+1]<b[q+1])f[i]=f[i-1]+a[++p];
		else f[i]=f[i-1]+b[++q];
	}
	while(p+1<a.size()&&i+1<=len){
		++i;
		f[i]=f[i-1]+a[++p];
	}
	while(q+1<b.size()&&i+1<=len){
		++i;
		f[i]=f[i-1]+b[++q];
	}
	if(dl)f[0]=f[1];
	return f;
}
struct node{
	vector<int>f[2][2];
};
string s;
node solve(int l,int r){
	node res;
	int len=(r-l+1)/2;
	REP(i,0,1)REP(j,0,1)res.f[i][j]=vector<int>(len+1,inf);
	if(l==r){
		res.f[0][0][0]=s[l-1]!='R';
		res.f[1][1][0]=s[l-1]!='S';
		return res;
	}
	int mid=(l+r)>>1;
	node L=solve(l,mid),R=solve(mid+1,r); // 分治下去
	REP(i,0,1)REP(j,0,1)REP(p,0,1)REP(q,0,1){
		int dl=0;
		if(j==0&&p==1)dl=1;
		if(l==mid&&i!=j)dl=-1; // 特判，下行同理
		if(mid+1==r&&p!=q)dl=-1;
		vector<int>v=merge(L.f[i][j],R.f[p][q],len,dl);
		REP(k,0,len)Min(res.f[i][q][k],v[k]);
	}
	return res;
}

---

接下来是最小费用最大流的建模。具体建图方式如下：

• 第一层：源点 $S$。
• 源点 $S$ 向每一个奇数点连 $(1,0)$ 的边。
• 第二层：奇数点。
• 每个奇数点 $k$ 向 $\text{R}$ 和 $\text{S}$ 分别连 $(1,[s_k=\text{S}])$ 和 $(1,[s_k=\text{R}])$ 的边。
• 第三层：奇数点根据选择 $\text{R}$ 和 $\text{S}$ 拆成两个点 $\text{R}k$ 和 $\text{S}k$。
• 每一组相邻的 $k,k+1$ 奇数点 $\text{R/S}$ 向偶数点的 $\text{S/R}$ 连边。
• 第四层：偶数点根据选择 $\text{R}$ 和 $\text{S}$ 拆成两个点 $\text{R}k$ 和 $\text{S}k$。
• 每个偶数拆点 $\text{R}$ 和 $\text{S}$ 向 $k$ 分别连 $(1,[s_k=\text{S}])$ 和 $(1,[s_k=\text{R}])$ 的边。
• 第五层：偶数点。
• 每一个偶数点向汇点 $T$ 连 $(1,0)$ 的边。
• 第六层：汇点 $T$。