A

The author, you [].

We need a dynamic space. You use a vector to save this matrix. Just resize it at the beginning.

Then consider making a question, and think of dividing the vertical and horizontal to calculate the distance. Open a bucket for each color, then record the horizontal and vertical coordinates of each color, traverse the coordinates from small to large, and then find the current answer linearly.

#include<bits/stdc++.h>
#define int long long
#define inf (1<<30)
#define INF (1ll<<60)
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define fi first
#define se second
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
using namespace std;
const int MAXN=1e5+10;
int cnt[MAXN];
vector<int> c[MAXN],x[MAXN],y[MAXN];
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n,m;cin>>n>>m;
	rep(i,1,n){
		c[i].resize(m+5);
		rep(j,1,m) cin>>c[i][j];
	}
	int ans=0,tot=0;
	rep(i,1,n) rep(j,1,m){
		int cur;
		if(cnt[c[i][j]]) cur=cnt[c[i][j]];
		else cnt[c[i][j]]=++tot,cur=tot;
		x[cur].pb(i);y[cur].pb(j);
	}
	rep(i,1,tot){
		sort(x[i].begin(),x[i].end());
		sort(y[i].begin(),y[i].end());
		int num=0,lst=x[i][0],fns=0;
		for(int s:x[i]) ans+=(fns=num*(s-lst)+fns),lst=s,num++;
		num=0,lst=y[i][0],fns=0;
		for(int s:y[i]) ans+=(fns=num*(s-lst)+fns),lst=s,num++;
	}cout<<ans<<'\n';
	return 0;
}

B

Consider the following:

So consider enumerating a \ (Z \) that is not in the \ (a \) array to see if \ (x,y \) can represent it. In this way, for each \ (Z \), we only need to enumerate \ (\ dfrac{c}{z} \) intervals, and then use prefix and preprocessing to \ (O(1) \) judge whether there are numbers in an interval.

#include<bits/stdc++.h>
#define int long long
#define inf (1<<30)
#define INF (1ll<<60)
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define fi first
#define se second
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
using namespace std;
const int MAXN=2e6+10;
int sum[MAXN];
void solve(){
	int n,c,a;cin>>n>>c;
	rep(i,1,n) cin>>a,sum[a]++;
	rep(i,1,c*2) sum[i]+=sum[i-1];
	bool ok=1;
	rep(z,1,c){
		if(sum[z]-sum[z-1]) continue;
		for(int y=1;y*z<=c;y++){
//			cerr<<sum[y]<<' '<<sum[y-1]<<' '<<sum[y*z+y-1]<<' '<<sum[y*z-1]<<' '<<y<<' '<<z<<'\n';
//			cerr<<y*z+y-1<<' '<<y*z-1<<'\n';
			if((sum[y]-sum[y-1])>0&&(sum[y*z+y-1]-sum[y*z-1])>0){
				ok=0;
			}
		}
	}
	rep(i,1,c*2) sum[i]=0;
	if(ok) cout<<"Yes\n";
	else cout<<"No\n";
}
signed main()
{
	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	int T;for(cin>>T;T--;)
		solve();
	return 0;
}

C

CRT, first [], rebuild pretest!

Note that this question has a very weak pretest!!!

Consider the routine of counting questions for dictionary order comparison, and consider enumerating which position \ (s_i < t_i \), and then the previous positions are equal, and the subsequent positions are filled in casually.

Then consider using a tree array to maintain the enumeration to the position of \ (I \). Remove the numbers that have been filled in the front and are equal to \ (t_i \), and how much is left for each number. Then, for enumerating to position \ (I \), there are still \ (n-i+1 \) numbers left.

Then we force \ (I \) to fill in less than \ (t_i \), so the position of the remaining \ (n-i \) can be filled in at will. That is, if we set the current number of each number to be \ (cnt_i \), the sum of all numbers to be \ (tot \), and the sum of numbers smaller than \ (t_i \) to be \ (tmp \), then the answer to the current position will be added:

Then you can maintain \ (\ prod cnt_i! \) with a variable.

Note that finally, it is necessary to judge whether \ (s \) can be the prefix of \ (t \). When enumerating, just mark it to judge whether it is the prefix.

#include<bits/stdc++.h>
#define int long long
#define inf (1<<30)
#define INF (1ll<<60)
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define fi first
#define se second
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
using namespace std;
const int MAXN=2e5+10;
const int MOD=998244353;
int ksm(int a,int p){
	int ret=1;while(p){
		if(p&1) ret=ret*a%MOD;
		a=a*a%MOD; p>>=1;
	}return ret;
}
int inv(int x){return ksm(x,MOD-2);}
struct Tree{int l,r,cnt;}tr[MAXN<<2];
int fac[MAXN];
#define ls i<<1
#define rs i<<1|1
void build(int i,int l,int r){
	tr[i].l=l;tr[i].r=r;tr[i].cnt=0;
	if(l==r) return;int mid=l+r>>1;
	build(ls,l,mid);build(rs,mid+1,r);
}
void pushup(int i){
	tr[i].cnt=tr[ls].cnt+tr[rs].cnt;
}
void upd(int i,int x,int v){
	if(tr[i].l==tr[i].r){tr[i].cnt+=v;return;}
	int mid=tr[i].l+tr[i].r>>1;
	if(x<=mid) upd(ls,x,v);else upd(rs,x,v);
	pushup(i);
}
int qcnt(int i,int l,int r){
	if(l>r) return 0;
	if(tr[i].l==l&&tr[i].r==r) return tr[i].cnt;
	int mid=tr[i].l+tr[i].r>>1;
	if(r<=mid) return qcnt(ls,l,r);
	else if(l>mid) return qcnt(rs,l,r);
	else return qcnt(ls,l,mid)+qcnt(rs,mid+1,r);
}
int s[MAXN],t[MAXN];
int cs[MAXN];
signed main()
{
	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	fac[0]=1;rep(i,1,MAXN-10) fac[i]=fac[i-1]*i%MOD;
	int n,m;cin>>n>>m;build(1,1,MAXN-10);
	rep(i,1,n) cin>>s[i],cs[s[i]]++,upd(1,s[i],1);
	rep(i,1,m) cin>>t[i];
	int all=1;
	rep(i,1,MAXN-10) all=all*fac[cs[i]]%MOD;
	int ans=0,ok=1;
	rep(i,1,min(n,m)){
		int tmp=qcnt(1,1,t[i]-1);
//		cerr<<tmp<<'\n';
		if(tmp){
			int rem=n-i;
			ans+=fac[rem]*inv(all)%MOD*tmp%MOD;
			ans%=MOD;
		}
		if(!cs[t[i]]){ok=0;break;}
		else all=all*inv(cs[t[i]])%MOD,cs[t[i]]--,upd(1,t[i],-1);
//		rep(j,1,3) cerr<<qcnt(1,j,j)<<' ';cerr<<'\n';
	}
	if(n>=m) ok=0;
	cout<<(ans+ok)%MOD<<'\n';
	return 0;
}/*
3 6
10 7 8
8 7 6 10 5 4
*/