难度预估：黄，蓝，黑，紫/黑。

A

题意：给定一个 $n$ 个数的排列 $a$，每次操作交换相邻两个数，求最小的操作次数，使得每个前缀都不是一个 $[1,i]$ 的排列，并使操作的字典序最小。$n\le 10^5$。

注意到，对于原序列中存在的每个 $i$，若 $i$ 的前缀是一个 $[1,i]$ 的排列（可以使用哈希等方法判断），那么必须交换 $i$ 和 $i+1$。

不难发现这样交换完毕后一定满足条件。另外字典序需要最小，从左到右执行所有操作即可。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ul;
const int N=1e5+5;
const ul base=1e9+7;
int n,a[N];
ul pw[N],hs[N];
void init(){
	pw[1]=1;
	for(int i=2;i<=n;i++){
		pw[i]=pw[i-1]*base;
	}
	for(int i=1;i<=n;i++){
		hs[i]=hs[i-1]+pw[i];
	}
}
void sol(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	init();
	ul now=0;
	vector<int> ans;
	for(int i=1;i<n;i++){
		now+=pw[a[i]];
		if(now==hs[i]){
			ans.push_back(i);
		}
	}
	cout<<(int)ans.size()<<"\n";
	for(int i:ans){
		cout<<i<<" ";
	}
	cout<<"\n";
}
signed main(){
	freopen("queue.in","r",stdin);
	freopen("queue.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	int ct=1;
//	cin>>ct;
	while(ct--){
		sol();
	}
} 

B

题意：一个 $n\times m$ 的网格，处于位置 $(i,j)$ 时可以向 $a_{i,j}$ 对应的方向（上下左右中的一种）移动不超过 $k$ 格。求从多少个点出发可以移动到网格外。$n,m,k\le 3000$。

一个直接的想法是线段树优化建图，将所有边反向后搜一遍整个图。但是带 $\log$ 而且常数很大，过不去。注意到每次都是一段长度固定为 $k$ 的区间，考虑是否有线性的优化建图方式。

不难想到，对于每行和每列都以 $k$ 为块长进行分块，每块内部使用前后缀优化建图。从每个原始点向外连边时只需要连出 $2$ 条边即可。这样就是 $O(nm)$ 的了。

但如果你就这么写完交上去，你就会得到一个 MLE。原因是我们使用了 $nm$ 个原始点和 $4nm$ 个辅助点，每个点对应两条边，$512$ MB 的空间连图都存不下。考虑如何处理。

考虑一个 trick：注意到建图的逻辑是确定的，我们可以不显式的把图建出来，而是在搜索过程中，每搜到一个点，就根据建图逻辑计算这个点的所有出边。

时间复杂度依然为 $O(nm)$。注意用 bfs，不要用 dfs，否则大量栈空间使用会导致 MLE。

#include<bits/stdc++.h>
using namespace std;
const int N=3005;
int n,m,k,ans;
unsigned char a[N][N];
bitset<N> c[N];
bitset<5<<24> vis;
int q[5*N*N],qc;
int zp(int l,int i,int j){
	return (l<<24)|(i<<12)|j;
}
array<int,3> rzp(int x){
	return {x>>24,(x>>12)&4095,x&4095};
}
void eds(int l,int i,int j,int stk[],int &top){
	if(l==0){
		for(int o=1;o<=4;o++){
			stk[top++]=zp(o,i,j);
		}
	}
	if(l==1){
		if((j-1)%k!=0&&j!=1){
			stk[top++]=zp(1,i,j-1);
		}
		if(j-1>=1&&a[i][j-1]==1){
			stk[top++]=zp(0,i,j-1);
		}
		if(j+k<=m&&a[i][j+k]==3){
			stk[top++]=zp(0,i,j+k);
		}
	}
	if(l==3){
		if(j%k!=0&&j!=m){
			stk[top++]=zp(3,i,j+1);
		}
		if(j-k>=1&&a[i][j-k]==1){
			stk[top++]=zp(0,i,j-k);
		}
		if(j+1<=m&&a[i][j+1]==3){
			stk[top++]=zp(0,i,j+1);
		}
	}
	if(l==2){
		if((i-1)%k!=0&&i!=1){
			stk[top++]=zp(2,i-1,j);
		}
		if(i-1>=1&&a[i-1][j]==2){
			stk[top++]=zp(0,i-1,j);
		}
		if(i+k<=n&&a[i+k][j]==4){
			stk[top++]=zp(0,i+k,j);
		}
	}
	if(l==4){
		if(i%k!=0&&i!=n){
			stk[top++]=zp(4,i+1,j);
		}
		if(i-k>=1&&a[i-k][j]==2){
			stk[top++]=zp(0,i-k,j);
		}
		if(i+1<=n&&a[i+1][j]==4){
			stk[top++]=zp(0,i+1,j);
		}
	}
}
signed main(){
	freopen("sprint.in","r",stdin);
	freopen("sprint.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char x;
			cin>>x;
			if(x=='R') a[i][j]=1;
			if(x=='D') a[i][j]=2;
			if(x=='L') a[i][j]=3;
			if(x=='U') a[i][j]=4;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]==1){
				if(j+k>m) c[i][j]=1;
			}
			if(a[i][j]==3){
				if(j-k<1) c[i][j]=1;
			}
			if(a[i][j]==2){
				if(i+k>n) c[i][j]=1;
			}
			if(a[i][j]==4){
				if(i-k<1) c[i][j]=1;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(c[i][j]){
				q[++qc]=zp(0,i,j);
				vis[zp(0,i,j)]=1;
			}
		}
	}
	while(qc){
		auto [l,i,j]=rzp(q[qc--]);
		if(l==0) ans++;
		int stk[4];
		int top=0;
		eds(l,i,j,stk,top);
		for(int o=0;o<top;o++){
			int v=stk[o];
			if(!vis[v]){
				q[++qc]=v;
				vis[v]=1;
			}
		}
	}
	cout<<ans<<"\n";
}

C

题意：对长度为 $n+2$ 的非负整数序列 $a$，满足 $a_0=a_{n+1}=0,\sum \max(a_{i+1}-a_i,0)=m$ 进行计数。对 $998244353$ 取模。$n,m\le 2\times 10^5$。

将问题转化一下，改为构造差分序列。然后考虑把模型放到格点上。问题变为：从 $(0,0)$ 走到 $(m,m)$ 的所有不越过对角线格路分为 $n+1$ 段的答案之和，其中格路的拐点必须分开。

如果直接 dp，无论如何都至少要记录至少两到三维状态，不行。考虑使用组合意义。

考虑枚举拐点数量 $k$（我们每两个拐点枚举一个，所以真实数量是 $2k+1$）。设拐点坐标分别为 $(x_1,y_1),(x_2,y_2),\dots,(x_k,y_k)$。此时需要处理不经过对角线的限制。考虑正难则反，令其经过对角线，设其第一次经过对角线在 $i$ 个格点，则满足 $x_{i}>y_i$ 以及所有 $j<i$ 都满足 $x_i\le y_i$，可列式如下：

$$0<y_1<y_2<\dots<y_{i-1}<x_{i+1}<x_{i+2}<\dots<x_k<m$$$$0<x_1<x_2<\dots<x_i<y_i<y_{i+1}<\dots<y_k<m$$

上下两式互不干扰，分别为其中的 $k+1$ 和 $k-1$ 个数分配值即可。方案数为 $\binom{k+1}{m-1} \binom{k-1}{m-1}$。这是非法的方案数，合法方案数为 $w(k)=\binom{k}{m-1} \binom{k}{m-1} -\binom{k+1}{m-1} \binom{k-1}{m-1}$。

然后考虑如何计算答案。我们需要从格路中的 $2m$ 个单位线段的 $2m+1$ 个空隙中，插入 $n-2k-1$ 个板（可插入同位置）。答案为 $\binom{n-2k-1}{(2m+1)+(n-2k-1)-1}\times w(k)$。

枚举 $k$ 并求和即可，时间复杂度 $O(n)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=6e5+5;
const int p=1e9+7;
void add(int &x,int y){
	x=(x+y)%p;
	if(x<0) x+=p;
}
int fac[N],inv[N];
void init(){
	fac[0]=1;
	for(int i=1;i<N;i++){
		fac[i]=fac[i-1]*i%p;
	}
	inv[0]=inv[1]=1;
	for(int i=2;i<N;i++){
		inv[i]=inv[p%i]*(p-p/i)%p;
	}
	for(int i=2;i<N;i++){
		inv[i]=inv[i-1]*inv[i]%p;
	}
}
int cc(int x,int y){
	if(x<0||y<0||x>y) return 0;
	return fac[y]*inv[x]%p*inv[y-x]%p;
}
int n,m,ans;
signed main(){
	freopen("cake.in","r",stdin);
	freopen("cake.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	init();
	cin>>n>>m;
	for(int k=0;k<m;k++){
		int w=((k)?((cc(k,m-1)*cc(k,m-1)-cc(k+1,m-1)*cc(k-1,m-1))%p):(1));
		if(n-2*k-1>=0) add(ans,cc(n-2*k-1,2*m+1+(n-2*k-1)-1)*w);
	}
	cout<<ans<<"\n";
} 

D

给定长为 $n$ 的元素序列 $a$ 和 $m$ 种元素的对应关系 $i\to b_i$，其中 $b$ 为排列。支持单点修改 $a$，以及给定 $l,r,x$ 询问 $[l,r]$ 内能够找到的最长的包含 $x$ 的子区间，满足区间内每个元素的右侧都是其对应的元素。

引入布尔数组 $c_i$ 表示 $i$ 右侧是否是其对应的元素。寻找区间 $[l,r]$ 时，需要令 $[l,r-1]$ 的 $c$ 值均为 $1$。以下的表述建立在 $r$ 减 $1$ 的意义上。

考虑根号做法。考虑直接分块。全局维护每个位置所属的 $c=1$ 连续段，使用分块结构维护，支持 $O(\sqrt n)$ 区间覆盖和 $O(1)$ 单点查询。并在每块内部对每个值 $x$ 记录，完全包含于此块内且段内包含 $x$ 的 $c=1$ 连续段的长度最大值。修改时直接暴力重构受影响的块，查询时，暴力枚举所有散块和跨块连续段，并对整块内使用计算好的答案。所以还需要能够快速查询区间内是否包含 $x$，且支持 $O(\sqrt n)$ 以内单点修改的数据结构。

一个直接的想法是，使用一种较常规的区间查询元素个数的分块方法：对于每一块和每个值，维护这一块及其前面所有块种该值的总出现次数。对于每一块内部的每个前缀和后缀，维护这一块内出现过的每个值的出现次数。但是如果仔细想一下就会发现，如果使用 umap 等那么绝对超时，如果不使用 umap 那么也需要一定的哈希结构，而无法在 $512$ MB 内解决，所以只能宣告报废。

注意到我们并不需要严格 $O(1)$ 查询（散块必须 $O(1)$，但整块部分可以对跨越的每个整块 $O(1)$ 计算），也不需要求个数而只需要知道有没有出现。考虑一种特异的优化版本：对每个块内的每个值，记录其最左侧和最右侧的出现位置。这样就可以完美的满足我们的要求，且只开两个 short 数组不会 MLE。

代码如下。此代码常数较大，无法通过。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,B=500,M=N/B+5;
int n,m,q,a[N],b[N];
int c[N];
short s[M][N];
int stk[M][B*2+5],top[M];
int lf[N*4],rf[N*4],tot;
int bc(int x){
	return (x-1)/B+1;
}
int L(int bc){
	return (bc-1)*B+1;
}
int R(int bc){
	return bc*B;
}
struct ds{
	short sl[M][N],sr[M][N];
	void cl(int b){
		for(int i=L(b);i<=R(b);i++){
			sl[b][a[i]]=sr[b][a[i]]=0;
		}
	}
	void reb(int b){
		for(int i=L(b);i<=R(b);i++){
			sr[b][a[i]]=i-L(b)+1;
		}
		for(int i=R(b);i>=L(b);i--){
			sl[b][a[i]]=i-L(b)+1;
		}
	}
	int que(int l,int r,int x){
		int bl=bc(l),br=bc(r);
		if(bl==br){
			for(int i=l;i<=r;i++){
				if(a[i]==x){
					return 1;
				}
			}
		}
		else{
			if(sr[bl][x]&&sr[bl][x]+L(bl)-1>=l) return 1;
			for(int i=bl+1;i<br;i++){
				if(sr[i][x]) return 1;
			}
			if(sl[br][x]&&sl[br][x]+L(br)-1<=r) return 1;
		}
		return 0;
	}
}t;
struct ds1{
	int s[N],t[M];
	bool e[M];
	void push_down(int bc){
		if(e[bc]){
			for(int i=L(bc);i<=R(bc);i++){
				s[i]=t[bc];
			}
			e[bc]=0;
		}
	}
	void upd(int l,int r,int k){
		int bl=bc(l),br=bc(r);
		if(bl==br){
			push_down(bl);
			for(int i=l;i<=r;i++){
				s[i]=k;
			}
		}
		else{
			push_down(bl);
			for(int i=l;i<=R(bl);i++){
				s[i]=k;
			}
			for(int i=bl+1;i<br;i++){
				e[i]=1;
				t[i]=k;
			}
			push_down(br);
			for(int i=L(br);i<=r;i++){
				s[i]=k;
			}
		}
	}
	int que(int x){
		int b=bc(x);
		if(e[b]) return t[b];
		return s[x];
	}
}f;
void reb(int bc){
	for(int i=1;i<=top[bc];i++){
		int v=stk[bc][i];
		s[bc][v]=0;
	}
	top[bc]=0;
	for(int i=L(bc);i<=R(bc);i++){
		int w=f.que(i);
		if(w==0) continue;
		if(L(bc)<=lf[w]&&rf[w]<=R(bc)){
			short len=rf[w]-lf[w]+1;
			for(int j=lf[w];j<=rf[w];j++){
				s[bc][a[j]]=max(s[bc][a[j]],len);
				stk[bc][++top[bc]]=a[j];
				s[bc][a[j+1]]=max(s[bc][a[j+1]],len);
				stk[bc][++top[bc]]=a[j+1];
			}
			i=rf[w];
		}
	}
}
map<int,int> tr;
void del_seg(int w){
	f.upd(lf[w],rf[w],0);
	if(bc(lf[w])==bc(rf[w])){
		tr[bc(lf[w])]=1;
	}
}
void ins_seg(int w){
	f.upd(lf[w],rf[w],w);
	if(bc(lf[w])==bc(rf[w])){
		tr[bc(lf[w])]=1;
	}
}
void del_c(int x){
	int w=f.que(x);
	del_seg(w);
	if(lf[w]<=x-1){
		lf[++tot]=lf[w];
		rf[tot]=x-1;
		ins_seg(tot);
	}
	if(x+1<=rf[w]){
		lf[++tot]=x+1;
		rf[tot]=rf[w];
		ins_seg(tot);
	}
	for(auto [i,_]:tr){
		reb(i);
	}
	tr={};
}
void add_c(int x){
	int nl=x,nr=x;
	int wl=f.que(x-1);
	int wr=f.que(x+1);
	if(wl){
		del_seg(wl);
		nl=lf[wl];
	}
	if(wr){
		del_seg(wr);
		nr=rf[wr];
	}
	lf[++tot]=nl;
	rf[tot]=nr;
	ins_seg(tot);
	for(auto [i,_]:tr){
		reb(i);
	}
	tr={};
}
bool ck(int x){
	return a[x+1]==b[a[x]];
}
void ch_c(int x){
	int k=ck(x);
	if(c[x]==0&&k==1){
		add_c(x);
		c[x]=1;
	}
	else if(c[x]==1&&k==0){
		del_c(x);
		c[x]=0;
	}
}
signed main(){
	freopen("magic.in","r",stdin);
	freopen("magic.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=bc(n);i++){
		t.reb(i);
	}
	for(int i=1;i<=m;i++){
		cin>>b[i];
	}
	for(int i=1;i<n;i++){
		ch_c(i);
	}
	while(q--){
		int op;
		cin>>op;
		if(op==1){
			int x,k;
			cin>>x>>k;
			t.cl(bc(x));
			a[x]=k;
			t.reb(bc(x));
			if(x>1) ch_c(x-1);
			ch_c(x);
		}
		else{
			int l,r,x;
			cin>>l>>r>>x;
			if(l==r){
				if(a[l]==x) cout<<"1\n";
				else cout<<"0\n";
				continue;
			}
			if(!t.que(l,r,x)){
				cout<<"0\n";
				continue;
			}
			r--;
			int bl=bc(l),br=bc(r);
			int res=0;
			auto ckpos=[&](int pos){
				int w=f.que(pos);
				if(!w) return pos;
				int tl=max(lf[w],l);
				int tr=min(rf[w],r);
				if(t.que(tl,tr+1,x)){
					res=max(res,tr-tl+1);
				}
				return tr;
			};
			if(bl==br){
				for(int i=l;i<=r;i++){
					i=ckpos(i);
				}
			}
			else{
				for(int i=l;i<=R(bl);i++){
					i=ckpos(i);
				}
				int las=0;
				for(int i=bl+1;i<br;i++){
					if(L(i)>las) las=ckpos(L(i));
					res=max(res,(int)s[i][x]);
				}
				for(int i=L(br);i<=r;i++){
					i=ckpos(i);
				}
			}
			cout<<res+1<<"\n";
		}
	}
}