「雅礼集训 2017 Day2」水箱 题解

思路

首先我们注意到有一个特殊性质是所有限制都是要求有水的，那么答案就是全部灌满水，$m$ 个限制都能满足。

那么考虑每一次让水平面逐渐往下降，直到降到最高的挡板，再把水分成两部分，两边依次让水面往下降，直到水分成 $n$ 份且都为空。

但是让水分裂会让一些信息非常不好处理，所以我们考虑反着来，先把水分成 $n$ 份，放在每一个小格里，处理出单独放在一个格子里的答案，然后从小到大遍历挡板的高度，每次合并挡板两边水的信息。

先考虑单独各自的答案如何计算，考虑对于第 $i$ 格子维护两个小根堆 $q0_i,q1_i$，储存 $0/1$ 类型的限制的高度，设一个变量 $now$ 实时维护满足的限制，初始化为 $q0_i$ 的大小（表示没有水的情况），一份水的贡献相当于选定一个分界线，上面是没有水的限制，下面是有谁的限制。设当前格子两侧挡板的较低高度为 $h$，则当两个小根堆中的最小值 $\le h$ 时，取出高度最小的限制，如果是 $0$ 则此限制无法满足， $now \leftarrow now-1$，否则 $1$ 的限制可以满足， $now \leftarrow now+1$。

再考虑合并两部分水的情况，首先需要合并两部分的 $q0,q1$，可以使用启发式合并，然后考虑如何计算答案，设 $fmx_i$ 表示第 $i$ 部分水的历史最大答案，$s0_i,s1_i$ 分别表示这份水还剩 $s0_i$ 个 $0$ 的限制，满足了 $s1_i$ 个 $1$ 的限制，那么合并方法和之前一样，设 $h$ 表示这份水两边的最低挡板高度，依次从低到高加入限制即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t,n,m;
// 隔板结构体：v为高度，x为位置（分隔第x格与第x+1格）
struct N{
	int v,x;
}a[100010];
// h[i]记录第i个隔板的原始高度，用于后续查询连通块边界处的水位上限
int h[100010];
// 按隔板高度升序排序，模拟水位从低到高上涨的过程
bool cmp(N a,N b){
	return a.v<b.v;
}
// fa:并查集父节点; L,R:连通块的左右边界下标
// f0,f1:连通块对应的"无水/有水"堆的实际编号（启发式合并后堆的归属可能改变）
// fmx:该连通块在当前水位限制下最多能同时满足的条件数
// s0,s1:该连通块当前已选入答案的无水/有水条件个数
int fa[100010],L[100010],R[100010],f0[100010],f1[100010],fmx[100010],s0[100010],s1[100010];
// 并查集查找，带路径压缩
int find(int x){
	return fa[x]=(fa[x]==x?x:find(fa[x]));
}
// 小根堆，q0存储k=0(无水)条件的高度y，q1存储k=1(有水)条件的高度y
// 使用数组形式是为了支持启发式合并时交换/复用堆
priority_queue<int,vector<int>,greater<int>> q0[100010],q1[100010];
// 启发式合并堆：将y堆中的元素全部倒入x堆中
void merge0(int x,int y){
	while(!q0[y].empty()){
		q0[x].push(q0[y].top());
		q0[y].pop();
	}
}
void merge1(int x,int y){
	while(!q1[y].empty()){
		q1[x].push(q1[y].top());
		q1[y].pop();
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>t;
	while(t--){
		cin>>n>>m;
		// 初始化：每个格子初始为一个独立连通块，清空堆和所有统计信息
		for(int i=1;i<=n;i++){
			while(!q0[i].empty())q0[i].pop();
			while(!q1[i].empty())q1[i].pop();
			fa[i]=i;          // 并查集指向自己
			L[i]=R[i]=i;      // 左右边界都是自己
			f0[i]=f1[i]=i;    // 初始时第i个块的堆就是q0[i]/q1[i]
			s0[i]=s1[i]=0;    // 已选条件数归零
			fmx[i]=0;         // 最优解归零
		}
		// 读入n-1个隔板高度
		for(int i=1;i<n;i++){
			cin>>a[i].v;a[i].x=i;h[i]=a[i].v;
		}
		// 读入m个条件，按类型分别放入对应格子的堆中
		// k=0(无水)默认先全部选中，计入s0；k=1(有水)暂不选中
		for(int i=1;i<=m;i++){
			int x,v,op;
			cin>>x>>v>>op;
			if(op)q1[x].push(v);       // k=1: 在高度v+0.5处有水
			else q0[x].push(v),s0[x]++; // k=0: 在高度v+0.5处无水，初始全选
		}
		// 按隔板高度从小到大排序，之后按此顺序合并连通块
		sort(a+1,a+n,cmp);
		
		// ========== 第一阶段：预处理每个单独格子的最优解 ==========
		for(int i=1;i<=n;i++){
			fmx[i]=q0[i].size(); // 初始假设所有无水条件都满足
			int now=fmx[i];
			// mxh为该格子作为独立单元时的最高水位上限
			// 即左右两侧隔板高度的较小值（边界处视为无穷大）
			int mxh=min((i==1?2e9:h[i-1]),(i==n?2e9:h[i]));
			// 贪心调整：根据水位上限mxh，决定哪些条件可以同时满足
			// 堆顶是最小高度，优先处理最容易冲突或最容易满足的条件
			while(1){
				// 两个堆顶都>=mxh，说明剩余条件都在水位之上，无需再调整
				if((q0[i].empty()||q0[i].top()>=mxh)&&(q1[i].empty()||q1[i].top()>=mxh))break;
				if(q0[i].empty()){
					// 只剩有水条件且高度<mxh，较低水位即可满足，选中它
					now++;
					q1[i].pop();
					s1[i]++;
				}
				else if(q1[i].empty()){
					// 只剩无水条件且高度<mxh，水位过高无法满足该无水条件，丢弃
					now--;
					q0[i].pop();
					s0[i]--;
				}
				else if(q0[i].top()<=q1[i].top()){
					// 无水阈值<=有水阈值，该无水条件更容易被当前水位违反，放弃它
					now--;
					q0[i].pop();
					s0[i]--;
				}
				else{
					// 有水阈值<无水阈值，较低水位就能满足该有水条件，选中它
					now++;
					q1[i].pop();
					s1[i]++;
				}
				fmx[i]=max(fmx[i],now); // 记录过程中的最大值
			}
		}
		
		// ========== 第二阶段：按隔板高度从小到大合并相邻连通块 ==========
		for(int i=1;i<n;i++){
			int x=a[i].x,y=x+1; // 当前处理的隔板分隔第x格和第x+1格
			int fx=find(x),fy=find(y); // 找到x和y所在连通块的根
			
			// 更新合并后的右边界（fx在左，fy在右，合并后右边界取fy的右边界）
			R[fx]=R[fy];
			
			// 启发式合并无水堆：始终将小的堆并入大的堆，保证总复杂度O(nlog^2n)
			if(q0[fx].size()>=q0[fy].size())merge0(f0[fx],f0[fy]);
			else{
				merge0(f0[fy],f0[fx]);
				f0[fx]=fy; // fx的无水堆指针改为指向fy的堆
			}
			// 启发式合并有水堆，同理
			if(q1[fx].size()>=q1[fy].size())merge1(f1[fx],f1[fy]);
			else{
				merge1(f1[fy],f1[fx]);
				f1[fx]=fy; // fx的有水堆指针改为指向fy的堆
			}
			
			// 合并两个连通块的统计信息
			s1[fx]+=s1[fy];
			s0[fx]+=s0[fy];
			fmx[fx]+=fmx[fy]; 
			fmx[fx]=max(fmx[fx],s1[fx]); // 合并后的下界修正（至少能满足所有有水条件）
			
			// 执行并查集合并，将fy挂到fx下
			fa[fy]=fx;
			
			// 计算合并后连通块的新水位上限mx
			// 即连通块最左侧左边界的隔板 与 最右侧右边界的隔板 的较小值
			int mx=min((L[fx]==1?2e9:h[L[fx]-1]),(R[fx]==n?2e9:h[R[fx]]));
			int now=s1[fx]+s0[fx]; // 当前已选条件总数
			
			// 与第一阶段相同的贪心调整逻辑，适配新的水位上限mx
			// 因为合并后水位上限可能变化，需要重新检查堆中条件是否还能同时满足
			while(1){
				if((q0[f0[fx]].empty()||q0[f0[fx]].top()>=mx)&&(q1[f1[fx]].empty()||q1[f1[fx]].top()>=mx))break;
				if(q0[f0[fx]].empty()){
					now++;
					q1[f1[fx]].pop();
					s1[fx]++;
				}
				else if(q1[f1[fx]].empty()){
					now--;
					q0[f0[fx]].pop();
					s0[fx]--;
				}
				else if(q0[f0[fx]].top()<=q1[f1[fx]].top()){
					now--;
					q0[f0[fx]].pop();
					s0[fx]--;
				}
				else{
					now++;
					q1[f1[fx]].pop();
					s1[fx]++;
				}
				fmx[fx]=max(fmx[fx],now);
			}
		}
		// 最终所有格子会合并为一个连通块，其fmx即为最多能同时满足的条件数
		cout<<fmx[find(1)]<<'\n';
		
	}
	return 0;
}

算法思路解析

一、建模：把物理过程翻译成离散约束

设第 $i$ 格的水位为 $l_i$。由于水从底部连续积起，条件可以翻译为：

• $k=1$（高度 $y+0.5$ 有水）$\iff l_i \ge y+0.5$（即水位超过 $y$）；
• $k=0$（高度 $y+0.5$ 无水）$\iff l_i \le y$。

物理平衡条件：对高度为 $h$ 的挡板，较高一侧水位若超过 $h$，水就会翻过去，直到两边水位相等。因此平衡时：

若 $l_i \ne l_{i+1}$，则较高的一侧必须 $\le h$；换言之，水位一旦超过 $h$，挡板两侧就"绑定"，必须同高、一起涨落。

又因为条件、挡板高度都是整数，最优解中水位只可能取 $0$ 或"整数 $+0.5$"，于是所有候选高度是离散的——这提示我们把挡板高度和条件按 $y$ 排序，从低到高扫。

二、扫掠线 + 并查集贪心

把 $n-1$ 个挡板看成 op=-1 的事件，条件看成 op=k 的事件，按高度升序扫。扫到某个高度时，被"已扫过的挡板"连起来的格子构成一个连通块：块内水位若要继续升高，就必须整体一致。对每个块维护两个量（即代码里的 ans 和 f）：

• f：块内已扫到的 $k=1$ 条件数。它代表候选方案"现在就把水位抬到比已扫高度都高"的收益：这些 $k=1$ 全满足，但已扫到的 $k=0$ 全牺牲。
• ans：块内"把水位停在不超过当前扫掠高度的某个位置"的所有候选方案的最优收益。关键观察：
  • 后来（更高处）出现的 $k=0$ 条件，对任何"已经停在低处"的方案都白送，即它给所有候选方案 $+1$，所以直接 ans++（题解所谓"$k=0$ 一定满足"）；
  • 新来的 $k=1$ 提供一个新的候选停点"恰好比这里高"，价值为 f，所以 f++; ans=max(ans,f)。

三种事件对应代码：

同高度的排序 op:-1→0→1 是必须的：同高的挡板要先绑定，之后 $k=1$ 的"抬水"决策才作用在正确的块上；同高的 $k=0$ 要先计入，这样同高 $k=1$ 抬水时才会把该 $k=0$ 算作牺牲（否则会出现矛盾条件被同时计数的错误）。

最后所有 $n-1$ 个挡板都被扫过，全体格子并成一个块，其 ans 就是答案；代码用 res 沿途取 max（ans 只增不减，等价于最后取）。

三、例子：样例 1 手玩

$n=3$，挡板 $h_1=3,h_2=4$；条件 $(1,3,1),(2,1,0),(2,2,0),(3,3,1)$。排序后事件流及执行过程：

输出 $3$。对应方案：$\{1,2\}$ 停在低处（水位 $0$），$\{3\}$ 停在 $3.5$，即水位 $(0,0,3.5)$——满足 $(2,1,0),(2,2,0),(3,3,1)$ 共 3 个；且 $l_3=3.5\le h_2=4$，不违反物理。

样例 2：同高事件按 $-1,0,1$ 序：先合并 $\{1,2\}$；$k=0$ 使 $ans=1$；$k=1$ 使 $f=1,\ ans=\max(1,1)=1$（矛盾条件只能满足一个），输出 $1$。

四、复杂度

排序 $O((n+m)\log(n+m))$，并查集带路径压缩近似 $O((n+m)\alpha(n))$，完全能过 $n,m\le 10^5$。

一句话总结：按高度从低到高扫掠，用并查集维护"水位超过挡板就必须同高"的连通块；块内 f 记录"现在抬水"的收益、ans 记录"停在某个低处"的最优收益，$k=0$ 白送（ans++），$k=1$ 提供新候选停点（ans=max(ans,f)），合并时收益相加——这正是题解图中所述的扫掠线贪心。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
struct node{int op,x,y;bool operator<(const node&rhs)const{if(y!=rhs.y)return y<rhs.y;return op<rhs.op;}}q[N<<1];
int fa[N],f[N],ans[N];
int findfa(int x){return fa[x]?fa[x]=findfa(fa[x]):x;}
void solve()
{
	int n,m;cin>>n>>m;
	int cnt=0;
	for(int i=1;i<n;i++)
	{
		int h;cin>>h;
		q[++cnt]={-1,i,h};
	}
	for(int i=1;i<=m;i++)
	{
		int x,y,k;cin>>x>>y>>k;
		q[++cnt]={k,x,y};
	}
	sort(q+1,q+cnt+1);
	for(int i=1;i<=n;i++)fa[i]=0,f[i]=0,ans[i]=0;
	int res=0;
	for(int i=1;i<=cnt;i++)
	{
		int op=q[i].op,x=q[i].x;
		if(op==-1)
		{
			int rx=findfa(x),ry=findfa(x+1);
			if(rx!=ry)
			{
				fa[ry]=rx;
				ans[rx]+=ans[ry];
				f[rx]+=f[ry];
				res=max(res,ans[rx]);
			}
		}
		else if(op==0)
		{
			int rx=findfa(x);
			ans[rx]++;
			res=max(res,ans[rx]);
		}
		else
		{
			int rx=findfa(x);
			f[rx]++;
			ans[rx]=max(ans[rx],f[rx]);
			res=max(res,ans[rx]);
		}
	}
	cout<<res<<'\n';
}
signed main()
{
	int t;cin>>t;
	while(t--)solve();
	return 0;
}

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 7, mod = 998244353;
template <typename A, typename B> inline bool chmin(A &a, B b){if(a > b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline bool chmax(A &a, B b){if(a < b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline LL add(A x, B y) {if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y;}
template <typename A, typename B> inline void add2(A &x, B y) {if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y);}
template <typename A, typename B> inline LL mul(A x, B y) {return 1ll * x * y % mod;}
template <typename A, typename B> inline void mul2(A &x, B y) {x = (1ll * x * y % mod + mod) % mod;}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, cnt, ans[MAXN], f[MAXN], fa[MAXN];
int find(int x) {
    return fa[x] ? fa[x] = find(fa[x]) : x;
}
struct Query {
    int opt, x, y;
    bool operator < (const Query &rhs) const {
        return y == rhs.y ? opt < rhs.opt : y < rhs.y;
    }
}q[MAXN];
void solve() {
    memset(ans, 0, sizeof(ans)); memset(f, 0, sizeof(f)); memset(fa, 0, sizeof(fa));
    cnt = 0;
    N = read(); M = read();
    for(int i = 1; i < N; i++) q[++cnt] = {-1, i, read()};
    for(int i = 1; i <= M; i++) q[++cnt].x = read(), q[cnt].y = read(), q[cnt].opt = read();
    stable_sort(q + 1, q + cnt + 1);
    int ret = 0;
    for(int i = 1; i <= cnt; i++) {
        int op = q[i].opt, x = q[i].x;
        if(op == -1) {
            int y = find(x + 1); x = find(x);
            fa[y] = x; f[x] += f[y]; ans[x] += ans[y]; chmax(ret, ans[x]);
        } else if(op == 0) {
            chmax(ret, ++ans[find(x)]);
        } else {
            x = find(x); chmax(ans[x], ++f[x]);
            chmax(ret, ans[x]);
        }
    }
    cout << ret << '\n';
}
int main() {
    for(int T = read(); T--; solve());
    return 0;
}