T1 矩阵交换

题意

有一个 n×mn\times m 的矩阵，元素为 1,2,31,2,3。可以任意交换两行，判断能否使得每一列都单调不递减（形如 1,1,…,2,2,…,3,31,1,\dots,2,2,\dots,3,3）。

思路

  • 题目提到行排序后看每列内部的关系。因此自然的分析列内的性质。

  • 如果m=1m=1则直接输出YES容易解决，考虑m=2m=2。

  • 考虑以第11列元素为关键字对行进行排序，形成了11⋯1122⋯2233⋯3311\cdots1122\cdots 2233\cdots 33的序列。认为是三个区间[l1,r1],[l2,r2],[l3,r3][l_1,r_1],[l_2,r_2],[l_3,r_3]，其中l1=1,r3=m,r1+1=l2,r2+1=l3l_1=1,r_3=m,r_1+1=l_2,r_2+1=l_3，$a[l_1\cdots r_1][1]=1,a[l_2\cdots r_2][1]=2,a[l_3\cdots r_3][1]=3$。此时考虑第22列元素，$\max\{a[l_1\cdots r_1][2]\}\leq \min\{a[l_2\cdots r_2][2]\},\max\{a[l_2\cdots r_2][2]\}\leq \min\{a[l_2\cdots r_2][3]\}$，即第11列形成的33个区间在第22列内要满足非递减关系。

  • 总结下是：前一列形成了若干个区间在当前列满足非递减关系。

  • 采用上述方法从第22列推到第mm列，该问题解决。

T2 砖块摆放

题意

nn 层塔，相邻两个砖块颜色相同则上方砖块同色，不同则上方为第三种颜色。给定最底层 nn 个砖块颜色（A/B/C），求塔顶颜色。

思路

把三种颜色 A、B、C 分别映射为 0,1,20,1,2（模 33 意义下）。

观察规律：若相邻两个砖块颜色为 x1,x2x_1,x_2，则它们上方的砖块颜色为 −(x1+x2)(mod3)- (x_1+x_2) \pmod 3（也就是 3−(x1+x2) mod 33-(x_1+x_2)\bmod 3）。

这恰好是二项式展开（杨辉三角系数）的形式。自底向上第 kk 层第 ii 个砖块（从 11 开始）对顶部的贡献系数为组合数 C(k−1,i−1)C(k-1,i-1)，并且每向上一层要乘一个 −1-1。

因此塔顶颜色为：

$$\mathrm{top} = \sum_{i=0}^{n-1} a_i \cdot C(n-1,i) \pmod 3$$

若 nn 为偶数，还需整体取负（因为从底层到顶层一共 n−1n-1 层，每层乘 −1-1，偶数次负数抵消的正负号要单独处理，具体见代码）。

由于模数为 33（质数），组合数可以用 Lucas 定理计算（33 很小，直接预处理的组合数在模 33 意义下只有 0,1,20,1,2 三种取值）。

复杂度

每组数据 O(nlog⁡3n)O(n\log_3 n)（Lucas 定理）或直接预处理 O(1)O(1) 组合数。

T3 学习 lis

10分：888^8枚举然后check即可，check的过程稍微加速一下，一旦不满足就返回，否则会TLE。

20分：我们显然可以一边dfs一边check前面生成的序列是否合法，这样n,m≤10n,m\leq 10的数据就卡不掉了，复杂度接近答案的大小。

30分：其实我们并不关心mm是多少，只关心我们生成的序列，一共出现了多少种不同的数字，以及这些数字必须得是从11开始连续的，比如，我们可以用[1,2,1,3][1,2,1,3]来代表所有类似于[1,4,1,6],[2,3,2,8][1,4,1,6],[2,3,2,8]类的序列，最后乘上组合数即可，所以在dfsdfs的过程中，记录一共用了多少种数字，以及哪些数字被用到了，稍微剪枝一下就可以了。

另外40分：考虑一个状压dpdp，我们每次填入相同数字到一个子集去，比如[1,2,1,3][1,2,1,3]这个方案，我们可以先给位置1,31,3填入11，变成[1,∗,1,∗][1,*,1,*]，然后再给第22个位置填入数字22变成[1,2,1,∗][1,2,1,*]，这个过程中，凡是填入的数字的LIS都是可以算出来的。

状态是：dpi,stadp_{i,sta}表示我考虑完了数字[1,i][1,i]，填入了stasta这个集合的方案数。

转移不表，复杂度O(3n×n×n)O(3^n\times n\times n)，但是由于给定LIS数组的限制，严重卡不满。

#include <bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define mod 998244353 
using namespace std;
ll C[3005][3005];
void init()
{
	C[0][0]=1;
	for (int i=1;i<=3000;i++)
		for (int j=0;j<=i;j++)
		{
			if (i==1 || j==0) C[i][j]=1;
			else C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
		}
}
int n,m;
int a[21];
ll dp[1<<20][21]; //填了i种数字，填了哪些位置的方案数 
void add(ll &x,ll y) {x=(x+y)%mod; return;}
int can(int sta,int nxt)
{
	int mx=0;
	for (int i=0;i<n;i++)
	{
		if ((sta>>i)&1) mx=max(mx,a[i]);
		if ((nxt>>i)&1) if (a[i]!=mx+1) return 0;
	}
	return 1;
}
int main()
{
	init();
	cin>>n>>m;
	for (int i=0;i<n;i++) cin>>a[i];
	dp[0][0]=1;
	for (int sta=0;sta<(1<<n);sta++)
	for (int i=0;i<n;i++)
	if (dp[sta][i])
	{
		int bu=(1<<n)-1-sta;
		for (int S=bu;S!=0;S=(S-1)&bu)	
		if (can(sta,S))
		{
			add(dp[sta|S][i+1],dp[sta][i]);			
		}
	}
	ll ans=0;
	for (int i=1;i<=n;i++) add(ans,dp[(1<<n)-1][i]*C[m][i]);
	cout<<ans<<endl;
}

100分：考虑把状压dpdp转移子集的过程拎出来：dpi,j,stadp_{i,j,sta}表示的是，我正在考虑数字ii的填写，当前在从后向前考虑第jj个位置填不填数字ii，当前状态是stasta的方案数。

转移不表，有一个小细节是，我们并不知道有没有用到ii，这样你可以选择加一个0/10/1状态来表示是否用过了ii，也可以选择就这么dpdp下来，这样你得到的答案ans[i]ans[i]表示的是，最多用了ii个不同数字，构造出的序列满足LIS数组的方案数。

容斥一下：ANS[i]=ans[i]−∑j=1i−1ANS[j]×CijANS[i]=ans[i]-\sum_{j=1}^{i-1}ANS[j]\times C_i^j即是恰好使用了ii个数字的方案数了。

时间复杂度O(2n×n2)O(2^n\times n^2)，需要滚动一下数组。

#include <bits/stdc++.h>
#define ll long long
#define maxn 3000005
#define mod 998244353 
using namespace std;
ll C[3005][3005];
void init()
{
	C[0][0]=1;
	for (int i=1;i<=3000;i++)
		for (int j=0;j<=i;j++)
		{
			if (i==1 || j==0) C[i][j]=1;
			else C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
		}
}
int n,m;
int a[21];
int premax[1<<20];
void init2()
{
	for (int sta=0;sta<(1<<n);sta++)
	{
		for (int i=0;i<n;i++)
		if ((sta>>i)&1)
			premax[sta]=max(premax[sta],a[i]);
	}
}
int dp[2][22][1<<20];
ll ans[25]; 
void add(int &x,int y) {x=(x+y)%mod; return;}
void DP()
{
	int now=0,nxt=1;
	dp[now][n-1][0]=1;
	for (int turn=1;turn<=n;turn++)
	{
		for (int i=n-1;i>=0;i--)
		for (int sta=0;sta<(1<<n);sta++)
		if (dp[now][i][sta])
		{
			int tmp=dp[now][i][sta];
			//case1：不选 
			if (i) add(dp[now][i-1][sta],tmp);
			else add(dp[nxt][n-1][sta],tmp);
			//case2：选
			if (((sta>>i)&1)==0 && premax[sta&((1<<i)-1)]+1==a[i])
			{
				if (i) add(dp[now][i-1][sta|(1<<i)],tmp);
				else add(dp[nxt][n-1][sta|(1<<i)],tmp);
			}
			dp[now][i][sta]=0;
		}
		//此时dp[nxt][n-1][sta]就是选了最多turn个数的时候的方案数
		ans[turn]=dp[nxt][n-1][(1<<n)-1];
		swap(now,nxt);
	}
	ll tot=0;
	for (int i=1;i<=n;i++)
	{
		for (int j=i-1;j>=1;j--)
		{
			ans[i]=(ans[i]+(-1*C[i][j]*ans[j]%mod)+mod)%mod;
		}
		tot=(tot+ans[i]*C[m][i]%mod)%mod;
	}
	cout<<tot<<endl;
}
int main()
{
	cin>>n>>m;
	for (int i=0;i<n;i++) cin>>a[i];
	init(); init2();
	DP();
}

T4 战略轰炸

首先断环为链。

下文中 AA 表示联通之后的军事基地的战斗力的最大值。

考虑给定 kk 和 bb 的轰炸机是否可以完美轰炸 cc 次的本质是判断 $\sum\limits_{i=1}^n{\operatorname{min}(\left\lfloor\dfrac{a_i}{k}\right\rfloor,c)} \geq b \times c$。 原因是因为一共轰炸 cc 次，一个军事基地最多被轰炸 ⌊aik⌋\left\lfloor\dfrac{a_i}{k}\right\rfloor 次，而若 ⌊aik⌋≥c\left\lfloor\dfrac{a_i}{k}\right\rfloor \geq c，则代表每次都可以选择轰炸它。否则对剩余的 ⌊aik⌋<c\left\lfloor\dfrac{a_i}{k}\right\rfloor < c 的军事基地轮流轰炸，即求和之后除以 cc 下取整，最后加起来判断是否能否有大于等于 bb 个军事基地被一同选中。

  • 特殊性质 AA

即每次询问一个 vv，求 $\sum\limits_{i=1}^n{\operatorname{min}(\left\lfloor\dfrac{a_i}{v}\right\rfloor,c)}$。 考虑对 aa 数组排序，设定一个阈值 BB，当 v≤Bv \leq B 时，预处理计算。当 v>Bv > B 时，枚举 ⌊aiv⌋\left\lfloor\dfrac{a_i}{v}\right\rfloor 用树状数组统计。再特判一下 ai≥v×ca_i \geq v \times c 的数的个数即可。取 B=AB=\sqrt{A}，则复杂度为 O((1+log⁡n)nA)O((1+\log n)n\sqrt{A})。

  • 特殊性质 BB

即给定一个长度为 nn 的数组 aa，qq 次操作。

  • 1 u v1\ u\ v 表示将 au←au+av,av←0a_u \gets a_u+a_v,a_v \gets 0。

  • 2 k v2\ k\ v 表示求 $\sum\limits_{i=1}^n{\operatorname{min}(\left\lfloor\dfrac{a_i}{v}\right\rfloor,c)}$。 1≤n,q,ai≤1051 \leq n,q,a_i \leq 10^5。

考虑对于 v≤Bv \leq B 的每个 vv 建立一个树状数组直接维护，预处理复杂度 O(AB)O(AB)，单次询问复杂度 O(log⁡n)O(\log n)，单次修改复杂度 O(Blog⁡n)O(B \log n)。

当 v>Bv > B 时与特殊性质 AA 的方法一样做即可，预处理复杂度 O(n)O(n)，单次询问复杂度 O(ABlog⁡n)O(\frac{A}{B}\log n)，单次修改复杂度 O(log⁡n)O(\log n)。

取 B=AB=\sqrt{A}，则复杂度为 O(nlog⁡nA)O(n \log n \sqrt{A})。

  • n<=1000n<=1000

对于 op=1op=1，暴力判断目前这个区间是否被其他区间覆盖。

对于 op=2op=2，用特殊性质 BB 的方法暴力做即可。

  • 正解

重点是要维护军事基地间的连通性，然后并查集记录连通块大小即可用特殊性质 BB 的方法直接做了。

考虑维护一个连通块中每个元素连接到下一个同连通块内的点。

设 pip_i 为 ii 号点上方的边数。设我们要合并 xx 和 yy (x≤yx \leq y)。

若 px≠pyp_x \neq p_y，不妨设 px>pyp_x > p_y，则我们向右找到第一个位置 pospos 满足 px>pposp_x > p_{pos}，因为 pos≤ypos \leq y，且此时 xx 所在的连通块必定被 pospos 所在的连通块包含，故直接合并 xx 与 pospos。反之同理。

若 px=pyp_x=p_y，依旧找到 pospos，若 pos<ypos < y 则如上操作，否则代表 xx 与 yy 之间没有其他连通块阻碍了，直接连接即可。

寻找 pp 可以直接线段树上二分。

而合并连通块时分类讨论：

首先定义 lxl_x 表示 xx 所在连通块最左边的位置， rxr_x 同理。这个直接用并查集维护。

若 xx 与 yy 所在连通块无包含关系，则直接给区间 (rx,ly)(r_x,l_y) 的 pp 值加一。

否则需要断掉 (lx,rx)(l_x,r_x) 这条边，加上 (lx,ly)(l_x,l_y) 和 (ry,rx)(r_y,r_x) 这两条边，同样线段树上区间加法维护。

这部分总复杂度 O(nlog⁡nα⁡(n))O(n\log n\operatorname{\alpha}(n))。

然后维护一下连通块的 aia_i 之和直接继续做即可。

总复杂度 $O(n\log n\operatorname{\alpha}(n)+n\log n \sqrt{A}))$。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace FastIO {
    char buf[1 << 21], buf2[1 << 21], a[20], *p1 = buf, *p2 = buf, hh = ' ';
    int p, p3 = -1;
    void read() {}
    void print() {}
    inline int getc() {
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
    }
    inline void flush() {
        fwrite(buf2, 1, p3 + 1, stdout), p3 = -1;
    }
    template <typename T, typename... T2>
    inline void read(T &x, T2 &...oth) {
        int f = 0;
        x = 0;
        char ch = getc();
        while (!isdigit(ch)) {
            if (ch == '-')
                f = 1;
            ch = getc();
        }
        while (isdigit(ch)) {
            x = x * 10 + ch - 48;
            ch = getc();
        }
        x = f ? -x : x;
        read(oth...);
    }
    template <typename T, typename... T2>
    inline void print(T x, T2... oth) {
        if (p3 > 1 << 20)
            flush();
        if (x < 0)
            buf2[++p3] = 45, x = -x;
        do {
            a[++p] = x % 10 + 48;
        } while (x /= 10);
        do {
            buf2[++p3] = a[p];
        } while (--p);
        buf2[++p3] = hh;
        print(oth...);
    }
}  // namespace FastIO
#define read FastIO::read
#define print FastIO::print
#define flush FastIO::flush
const int B = 100,A = 100000;
int n,q,c,sid,timer = 0,cnt[100010],a[100010],s[100010];
int LSB(int i){
	return i & (-i);
}
struct Bit{
	int bit[100010];
	void upd(int i,int k){
		if(!i) return;
		while(i <= A){
			bit[i] += k;
			i += LSB(i);
		}
	}
	int psq(int i){
		int s = 0;
		while(i){
			s += bit[i];
			i -= LSB(i);
		}
		return s;
	}
}bt[B + 5];
void modify(int pre,int v){
	for(int i = 1; i <= B; i++){
		if(!cnt[i]) continue;
		bt[i].upd(pre,-pre / i);
		bt[i].upd(v,v / i);
	}
	bt[B + 1].upd(pre,-1);
	bt[B + 1].upd(v,1);
}
namespace DSU{
	int fa[100010],l[100010],r[100010],sz[100010],val[100010];
	void init(){
		for(int i = 1; i <= n; i++) fa[i] = l[i] = r[i] = i,sz[i] = 1,val[i] = a[i];
	}
	int Find(int i){
		return fa[i] == i ? i : fa[i] = Find(fa[i]);
	}	
	void unite(int u,int v){
		int fu = Find(u),fv = Find(v);
		if(fu == fv) return;
		if(sz[fu] > sz[fv]) swap(fu,fv);
		fa[fu] = fv;
		l[fv] = min(l[fu],l[fv]);
		r[fv] = max(r[fu],r[fv]);
		modify(val[fv],val[fu] + val[fv]);
		modify(val[fu],0);
		val[fv] += val[fu];
		val[fu] = 0;
	}
};
using DSU::init;
using DSU::Find;
using DSU::unite;
int mn[400010],tag[400010];
#define ls(i) (i << 1)
#define rs(i) (i << 1 | 1)
void pushup(int i){
	mn[i] = min(mn[ls(i)],mn[rs(i)]);
}
void Tag(int i,int v){
	mn[i] += v,tag[i] += v;
}
void pushdown(int i){
	if(tag[i]){
		Tag(ls(i),tag[i]);
		Tag(rs(i),tag[i]);
		tag[i] = 0;
	}
}
void upd(int i,int l,int r,int ql,int qr,int v){
	if(ql <= l && r <= qr){
		Tag(i,v);
		return;
	}
	pushdown(i);
	int mid = (l + r) >> 1;
	if(ql <= mid) upd(ls(i),l,mid,ql,qr,v);
	if(qr > mid) upd(rs(i),mid + 1,r,ql,qr,v);
	pushup(i);
}
int query(int i,int l,int r,int pos){
	if(l == r) return mn[i];
	pushdown(i);
	int mid = (l + r) >> 1;
	if(pos <= mid) return query(ls(i),l,mid,pos);
	else return query(rs(i),mid + 1,r,pos);
}
int queryl(int i,int l,int r,int pos,int v){
	if(r <= pos){
		if(mn[i] >= v) return 0;
		if(l == r) return l;
		pushdown(i);
		int mid = (l + r) >> 1;
		if(mn[rs(i)] < v) return queryl(rs(i),mid + 1,r,pos,v);
		return queryl(ls(i),l,mid,pos,v);
	}
	pushdown(i);
	int mid = (l + r) >> 1,res = 0;
	if(mid + 1 <= pos) res = queryl(rs(i),mid + 1,r,pos,v);
	if(!res) res = queryl(ls(i),l,mid,pos,v);
	return res; 
}
int queryr(int i,int l,int r,int pos,int v){
	if(pos <= l){
		if(mn[i] >= v) return n + 1;
		if(l == r) return l;
		pushdown(i);
		int mid = (l + r) >> 1;
		if(mn[ls(i)] < v) return queryr(ls(i),l,mid,pos,v);
		return queryr(rs(i),mid + 1,r,pos,v);
	}
	pushdown(i);
	int mid = (l + r) >> 1,res = n + 1;
	if(pos <= mid) res = queryr(ls(i),l,mid,pos,v);
	if(res == n + 1) res = queryr(rs(i),mid + 1,r,pos,v);
	return res;
}
void merge(int x,int y){
	x = Find(x),y = Find(y);
	if(DSU::r[x] < DSU::l[y]) upd(1,1,n,DSU::r[x] + 1,DSU::l[y] - 1,1);
	else upd(1,1,n,max(DSU::l[x],DSU::l[y]),min(DSU::r[x],DSU::r[y]),-1);
	unite(x,y);
}
int OP[100010],U[100010],V[100010],C[100010];
signed main(){
	read(n),read(q),read(sid);
	for(int i = 1; i <= n; i++) read(a[i]);
	for(int i = 1; i <= B; i++){
		for(int j = 1; j <= n; j++) bt[i].bit[a[j]] += (a[j] / i);
		for(int j = 1; j <= A; j++) s[j] = s[j - 1] + bt[i].bit[j];
		for(int j = 1; j <= A; j++) bt[i].bit[j] = s[j] - s[j - LSB(j)];
	}
	for(int i = 1; i <= n; i++) bt[B + 1].bit[a[i]]++;
	for(int i = 1; i <= A; i++) s[i] = s[i - 1] + bt[B + 1].bit[i];
	for(int i = 1; i <= A; i++) bt[B + 1].bit[i] = s[i] - s[i - LSB(i)];
	init();
	for(int i = 1; i <= q; i++){
		read(OP[i]),read(U[i]),read(V[i]);
		if(OP[i] == 2){
			read(C[i]);
			if(U[i] <= B) cnt[U[i]]++;
		}
	}
	int op,u,v;
	for(int t = 1; t <= q; t++){
		op = OP[t],u = U[t],v = V[t];
		if(op == 1){
			if(u > v) swap(u,v);
			int vu = query(1,1,n,u),vv = query(1,1,n,v);
			while(Find(u) != Find(v)){
				if(vu > vv) merge(u,queryr(1,1,n,u,vu)),vu--;
				else if(vu < vv) merge(queryl(1,1,n,v,vv),v),vv--;
				else{
					int pos = queryr(1,1,n,u,vu);
					if(pos < v) merge(u,pos),vu--;
					else merge(u,v);
				}
			}
		}
		else{
			c = C[t];
			swap(c,v);
			int sum = (bt[B + 1].psq(A) - bt[B + 1].psq(u * v - 1)) * v;
			if(u <= B) sum += bt[u].psq(u * v - 1),cnt[u]--;
			else{
				for(int cc = u; cc <= min(A,u * v - 1); cc += u){ //cc ~ min(u * v - 1,cc + u - 1)
					timer++;
					sum += (bt[B + 1].psq(min(u * v - 1,cc + u - 1)) - bt[B + 1].psq(cc - 1)) * (cc / u);
				}
			}
			if(sum >= c * v) printf("Yes\n");
			else printf("No\n");
		}
	}
  	return 0;
}
  • 已修改
  • 10 次查看
  • 举报
    • 🕊️ 1

1 条评论

  • @ 2026-8-18 15:02:08
    已修改

    1. 问题转化：从"圆上的弦"到"链上的区间"

    军事基地等距离围成圆，编号 1∼n1\sim n。一座桥梁连接 u,vu,v，在圆上是一根弦。题面说"两个桥梁交叉则互相连通"。

    我们把圆断环为链：展开成一条直线 1,2,…,n1,2,\dots,n（断掉 nn 与 11 之间的边）。

    于是每座桥 [u,v][u,v]（设 u<vu<v）变成一个区间。两根弦 [u1,v1][u_1,v_1] 与 [u2,v2][u_2,v_2] 交叉，当且仅当它们"端点交错"：

    $$u_1 < u_2 < v_1 < v_2 \quad \text{或} \quad u_2 < u_1 < v_2 < v_1$$

    （注意：包含关系不算交叉。例如 [1,5][1,5] 包含 [2,4][2,4]，它们不交叉。）

    因此整个问题变成：维护若干区间，相交（端点交错）的区间合并成一个连通块，连通块的战斗力是块内所有基地战斗力之和。

    2. 核心数据结构：p 数组（覆盖层数）

    给每个连通块一个区间 [l,r][l,r]（l,rl,r 是该块最左、最右的基地编号）。

    定义数组 pip_i：覆盖点 ii 的"拱"的数量。

    想象每个连通块 [l,r][l,r] 是链上方的一道"拱"，从 ll 跨越到 rr。点 ii 位于几个拱下方，pip_i 就是几。

    初始：nn 个单点连通块 [i,i][i,i]，没有任何跨越的拱，所以 pi=0p_i=0。

    例子

    桥 [1,3]：拱从 1 跨越到 3
位置:  1   2   3   4   5
拱:    ┌───────┐
p 值:  0   1   0   0   0
       ↑   ↑   ↑
   1被拱  2被拱  3不在拱内

    点 2 被拱 [1,3][1,3] 覆盖，所以 p2=1p_2=1；点 1 是拱的左端点、点 3 是右端点（端点本身 p 记为 0 或 1 均可，关键是中间跨越的部分 p 会 +1）。

    3. merge(x, y)：合并两个连通块时如何更新 p

    合并连通块 xx（区间 [lx,rx][l_x,r_x]）与 yy（区间 [ly,ry][l_y,r_y]），分两种情况：

    情况一：xx 完全在 yy 左边（rx<lyr_x < l_y）

    x:  [l_x ─── r_x]        y:  [l_y ─── r_y]
              ↑     空隙        ↑

    合并后形成一个更大的拱 [lx,ry][l_x, r_y]，它会跨越中间的空隙 [rx+1, ly−1][r_x+1,\ l_y-1]。所以对这段空隙的每个点 p +1：

    if (r[x] < l[y]) upd(1, 1, n, r[x]+1, l[y]-1, 1);

    情况二：xx 与 yy 有重叠（rx≥lyr_x \ge l_y）

    x:  [l_x ───── r_x]
y:         [l_y ───── r_y]
            └─重叠─┘

    重叠部分 [ly,rx][l_y, r_x] 原本同时被 xx 和 yy 两个拱覆盖（pp 至少为 2），合并后只剩一个大拱覆盖，所以重叠部分的每个点 p -1：

    else upd(1, 1, n, max(l[x],l[y]), min(r[x],r[y]), -1);

    最后无论如何都要把两个块合并：

    unite(x, y);   // 并查集合并，更新 l、r、战斗力

    4. 线段树维护 p，支持"二分找边界"

    p 数组需要支持两类操作：

    1. 区间加（upd，合并时 p 值 +1/-1）；
    2. 二分查找：找到某个位置左/右第一个 p < v 的位置（queryl / queryr）。

    线段树的每个节点维护区间最小值 mn（外加懒标记 tag）。

    为什么用"最小值"？因为要找"第一个 p<vp<v 的位置"，如果某区间的最小值都 ≥v\ge v，说明该区间内不存在 p<vp<v 的点，可以直接跳过整段；否则递归往下找。

    queryr(pos, v)：从 pos 向右找第一个 p < v 的位置

    queryr(区间 [l,r], 目标位置 pos, 阈值 v):
    如果 r <= pos（整个区间都在 pos 右边）:
        如果 mn >= v: 返回 n+1   # 区间内没有 p<v
        如果 l == r:  返回 l     # 找到叶子
        优先去左子树（更靠左）
    否则（区间跨过 pos）:
        先查包含 pos 的那一侧，再查另一侧

    queryl 对称（从 pos 向左找第一个 p<v）。

    为什么这个二分能给出"拱的边界"？

    假设点 uu 的 pu=kp_u = k（被 kk 道拱覆盖）。这 kk 道拱从内到外的右端点依次为 r1<r2<⋯<rkr_1 < r_2 < \dots < r_k。

    从 uu 向右看，pp 值的变化是：

    位置:    u ───── r_1 ───── r_2 ───── r_k ─────
p 值:    k        k-1       k-2        0

    所以：

    • 第一个 p < k 的位置 = r1r_1（最内层拱的右端点）；
    • 第一个 p < 1 的位置 = rkr_k（最外层拱的右端点）。

    同理向左可以找到最内层拱的左端点。线段树二分就是 O(log⁡n)O(\log n) 地找到这些边界。

    5. 连接操作 op=1 的完整流程

    给定连接 u,vu,v（设 u<vu<v），目标是让它们最终在同一个连通块，同时正确处理中间所有相交的连通块。

    if (u > v) swap(u, v);
int vu = query(u);   // p[u]
int vv = query(v);   // p[v]

while (Find(u) != Find(v)) {
    if (vu > vv) {
        // u 比 v "更深"（被更多拱覆盖）
        merge(u, queryr(u, vu));   // 合并 u 与它最内层拱的右端点
        vu--;
    } else if (vu < vv) {
        // v 比 u 更深
        merge(queryl(v, vv), v);   // 合并 v 与它最内层拱的左端点
        vv--;
    } else {
        // 一样深
        int pos = queryr(u, vu);   // u 最外层拱的右端点
        if (pos < v) { merge(u, pos); vu--; }
        else merge(u, v);          // 中间没有阻碍了，直接连
    }
}

    直觉解释

    • p[u]、p[v] 反映 u,vu,v 被多少道拱"压住"。被压得更深的那个点，其"最内层拱"需要先跟相邻块合并，逐步"解套"。
    • 每 merge 一次，对应点所在的最内层拱被合并掉，vu/vv 减一（覆盖层数变浅一层）。
    • 当 vu == vv 且中间没有其他拱阻碍时（queryr 返回的位置 ≥ v），说明 u,vu,v 之间可以直接相连，merge(u,v) 完成。
    • 循环直到 Find(u) == Find(v)。

    整个过程每个连通块最多被合并一次，线段树二分与区间加都是 O(log⁡n)O(\log n)，并查集接近 O(1)O(1)，所以总复杂度 O(nlog⁡n α(n))O(n\log n\ \alpha(n))。

    完整例子

    n=5n=5，依次连接 1−31-3、2−52-5。

    初始：全单点，p=[0,0,0,0,0]p=[0,0,0,0,0]。

    连接 1-3：

    • merge(1,3)：r1=1<l3=3r_1=1 < l_3=3，给 [2,2][2,2] 的 p +1。
    • p=[0,1,0,0,0]p=[0,1,0,0,0]，连通块 {1,3}\{1,3\}（l=1,r=3l=1,r=3）。

    连接 2-5（桥 [2,5][2,5] 与 [1,3][1,3] 交叉，因为 1<2<3<51<2<3<5）：

    • p2=1, p5=0p_2=1,\ p_5=0，vu=1>vv=0vu=1>vv=0。
    • queryr(2, 1)：从 2 向右第一个 p<1 是位置 3（p3=0p_3=0）。merge(2, 3)。
      • r2=2≥l3=1r_2=2 \ge l_3=1（有重叠），给 [2,2][2,2] 的 p -1。
      • p=[0,0,0,0,0]p=[0,0,0,0,0]，合并 {2}\{2\} 与 {1,3}\{1,3\} → {1,2,3}\{1,2,3\}。
    • vuvu 变为 0，此时 vu=vv=0vu=vv=0。
    • queryr(2, 0) 返回 7（无 p<0）≥ 5，merge(2,5)。
      • r=3<l5=5r=3 < l_5=5，给 [4,4][4,4] 的 p +1，合并 → {1,2,3,5}\{1,2,3,5\}。
    • 结束，p=[0,0,0,1,0]p=[0,0,0,1,0]。

    结果连通块 {1,2,3,5}\{1,2,3,5\}（对应交叉的两座桥），正确。

    6. 询问 op=2（略）

    连通性由并查集维护好后，每个连通块的战斗力是块内 aia_i 之和。询问"能否完美轰炸 cc 次"等价于判断

    $$\sum \min\left(\left\lfloor\frac{a_i}{k}\right\rfloor, c\right) \ge b\cdot c$$

    这部分用根号分治 + 树状数组（题解已述），与线段树无关，不再展开。

    • 1
    21
    已通过
    0
    题解被赞
    1. Language
    2. 兼容模式
    3. 主题
    3. Worker 0, 37ms
    4. Powered by Hydro v5.0.1 Community