T1 矩阵交换

题目提到行排序后看每列内部的关系。因此自然的分析列内的性质。
如果 $m=1$ 则直接输出YES容易解决，考虑 $m=2$ 。
考虑以第 $1$ 列元素为关键字对行进行排序，形成了 $11\cdots1122\cdots 2233\cdots 33$ 的序列。认为是三个区间 $[l_1,r_1],[l_2,r_2],[l_3,r_3]$ ，其中 $l_1=1,r_3=m,r_1 1=l_2,r_2 1=l_3$ ，

alt

。此时考虑第 $2$ 列元素， $\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]\}$ ，即第 $1$ 列形成的 $3$ 个区间在第 $2$ 列内要满足非递减关系。

总结下是：前一列形成了若干个区间在当前列满足非递减关系。
采用上述方法从第 $2$ 列推到第 $m$ 列，该问题解决。

T2 砖块摆放

把三种颜色分别当作 0、1、2 三种数字、

假设相邻两个砖块的颜色为 $x_1,x_2$ ，那么通过大眼观察法可以发现上面的一个它们上面的砖块等于 $-(x_1 x_2)(\%$ $3)$ 意义下

根据公式可以发现砖块中每个数字和二项式定理（杨辉三角系数）的形式一致，即可用组合数学获得答案。

T3 学习 lis

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

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

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

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

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

转移不表，复杂度 $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分：考虑把状压 $dp$ 转移子集的过程拎出来： $dp_{i,j,sta}$ 表示的是，我正在考虑数字 $i$ 的填写，当前在从后向前考虑第 $j$ 个位置填不填数字 $i$ ，当前状态是 $sta$ 的方案数。

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

容斥一下： alt

即是恰好使用了 $i$ 个数字的方案数了。

时间复杂度 $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 战略轰炸

首先断环为链。

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

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

特殊性质 $A$

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

特殊性质 $B$

即给定一个长度为 $n$ 的数组 $a$ ， $q$ 次操作。

$1\ u\ v$ 表示将 $a_u \gets a_u a_v,a_v \gets 0$ 。
$2\ k\ v$ 表示求 $\sum\limits_{i=1}^n{\operatorname{min}(\left\lfloor\dfrac{a_i}{v}\right\rfloor,c)}$ 。 $1 \leq n,q,a_i \leq 10^5$ 。

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

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

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

$n \leq 1000$

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

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

正解

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

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

alt

设 $p_i$ 为 $i$ 号点上方的边数。设我们要合并 $x$ 和 $y$ ( $x \leq y$ )。

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

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

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

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

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

若 $x$ 与 $y$ 所在连通块无包含关系，则直接给区间 $(r_x,l_y)$ 的 $p$ 值加一。

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

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

然后维护一下连通块的 $a_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;
}

2023 OI 集训营提高组第五场题解

T1 矩阵交换

T2 砖块摆放

T3 学习 lis

T4 战略轰炸