[CSP-S 2024] 擂臺游戲題解

CSP-S2024 T4

后天就 CSP2025 了我終于想起來訂正 [CSP-S 2024] 擂臺游戲了。

謹以此篇，安慰去年考場上拼盡全力大戰 \(2.5h\) 只獲得 \(40pts\) 的自己。

思路來自于這篇題解。

約定

為了方便描述，我們做如下約定：

對于每個詢問 \(c_i\)，我們把那些可以任意欽定能力值的編號 \(>c_i\) 的人稱為 bot。對于編號 \(>n\) 的人他們始終是 bot，稱為完全 bot。
把最終的二叉樹畫出來之后，對于一個點 \(u\)，我們設他的父親是 \(fa_u\)，左兒子是 \(ls_u\)，右兒子是 \(rs_u\)，他管轄的區間為 \([L_u,R_u]\)，其子樹內的獲勝者為它的 winner，他的高度是 \(H_u\)（根的高度為 \(K\)，其中 \(K\) 是第一個滿足 \(2^K\ge n\) 的數），換句話說他的兩個兒子子樹的 winner 在對決時擂主的能力值需要 \(\ge H_u\) 才能獲勝。

觀察

我們先做一些簡單的觀察：

如果子樹內的全都是真人那么子樹的 winner 是唯一的。
當某一次對決的擂主為 bot，我們可以任意欽定這次對決是誰贏。

證：如果要讓 bot 贏，直接讓他的能力值為 \(+\infty\) 即可；如果要讓對手贏，注意到假設 bot 是 \(u\) 子樹的 winner，他其實只需要滿足 \(a_i \ge H_u\) 即可，因此我們直接令 \(H_u \to a_i\)，這樣就有 \(a_i < H_{fa_u}=H_u+1\)，于是他就守擂失敗了。

因此能感受到 bot 的可操作性很高，如果我們要讓某一個人獲勝，那么我們應該盡可能地給他安排 bot 作為對手，因為 bot 可以給他放水。

\(O(Tn^2m)\) + \(A\) 性質

考場上就只寫出了這個。

根據結論 \(1\)，特殊性質 A 的單次詢問答案是確定的，直接 DP 預處理即可。
對于 \(O(Tn^2m)\) 的做法，我們實現一個返回值為 vector 的函數 dfs(l,r) 表示當前詢問下區間 \([l,r]\) 可能的 winner 的集合，假設 \([l,mid]\) 的 winner 的集合為 \(A\)，\([mid+1,r]\) 的集合為 \(B\)，擂主是 \([l,mid]\) 的 winner：

對于 \(A\) 中的點，只有它的能力值大于等于當前高度或者他是 bot 才可能贏。
對于 \(B\) 中的點，只要 \(A\) 中存在一個 bot 或者存在一個能力值小于當前高度的真人就能贏。

單次詢問總共需要處理 \(O(n)\) 個這樣的區間 \([l,r]\)，每次合并是 \(O(n)\) 的，因此總復雜度是 \(O(Tn^2m)\)。
加上 A 性質，期望得分 \(40pts\)。

下面是考場代碼：

點擊查看代碼

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e5+5;
inline int read(){
	int w=1,s=0;
	char c=getchar();
	for(;c<'0'||c>'9';w*=(c=='-')?-1:1,c=getchar()) ;
	for(;c>='0'&&c<='9';s=s*10+c-'0',c=getchar()) ;
	return w*s;
}
int n,m,t[N],a[N],c[N],K,T,X[5],f[N][20],lg[N];
char d[20][N];
void Read(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&t[i]);
	for(int i=1;i<=m;i++) scanf("%lld",&c[i]);
	while((1<<K)<n) K++;
	for(int i=1;i<=K;i++) scanf("%s",d[i]+1);
	scanf("%lld",&T);
	for(int i=1;i<=n;i++) lg[i]=((1<<__lg(i))==i)?__lg(i):(__lg(i)+1);
}
void Get_f(){
	for(int i=1;i<=n;i++) f[i][0]=i;
	for(int t=1;t<=K;t++){
		for(int i=1,j=1;i+(1<<t)-1<=n;i+=(1<<t),j++){
			if(d[t][j]=='0'){
				if(a[f[i][t-1]]>=t) f[i][t]=f[i][t-1];
				else f[i][t]=f[i+(1<<(t-1))][t-1]; 
			}
			else{
				if(a[f[i+(1<<(t-1))][t-1]]>=t) f[i][t]=f[i+(1<<(t-1))][t-1]; 
				else f[i][t]=f[i][t-1];
			} 
		}
	}
}
vector<int> dfs(int t,int l,int r,int Limit){
	if(l==r) return {l};
	vector<int> L=dfs(t-1,l,l+(1<<(t-1))-1,Limit),R=dfs(t-1,l+(1<<(t-1)),r,Limit),res;
	if(d[t][l/(1<<t)+1]=='1') swap(L,R);
	bool flag=false;
	for(int u:L){
		if((u<=Limit&&a[u]>=t)||u>Limit) res.push_back(u);
		if((u<=Limit&&a[u]<t)||u>Limit) flag=true;
	}
	if(flag) for(int v:R) res.push_back(v);
	return res;
}

void work(){
	Get_f();
	
	int ans=0;
	for(int i=1;i<=m;i++){
		if(c[i]==(c[i]&(-c[i]))) ans^=i*f[1][lg[c[i]]];
		else if(n<=500 && m<=500){
			vector<int> res=dfs(lg[c[i]],1,1<<lg[c[i]],c[i]);
			int sum=0;
			for(int id:res) sum+=id;
			ans^=i*sum;
		}
	}
	printf("%lld\n",ans);
}
signed main(){
// 	freopen("arena.in","r",stdin);
// 	freopen("arena.out","w",stdout);
	Read();

	while(T--){
		for(int i=0;i<=3;i++) scanf("%lld",&X[i]);
		for(int i=1;i<=n;i++) a[i]=t[i]^X[i%4];
		work();
	}
	return 0;
}

閑話：不難發現其實只需要把 vector 換成平衡樹就可以做到 \(O(Tnm\log n)\) 拿到 \(52pts\)。不過這個做法前途不大，不做展開。

\(O(Tnm\log n)\)

仍然是對每次詢問單獨處理，不妨假設 \(c_i=n\)，上面這個做法轉移的復雜度太難繃了，考慮直接對每個點 \(i\) 算貢獻，判斷它能否成為最終的 winner。
我們讓他不斷往上爬，假設現在爬到點 \(u\)，\(u\) 的兄弟是 \(v\)：

如果擂主是 \(i\)，此時是簡單的，如果他是真人且能力值沒有達到要求就完蛋了，否則可以繼續往上爬。
如果擂主是 \(v\) 子樹的 winner，這個時候需要分類討論一下：

如果 \(v\) 子樹內全是真人，那么 winner 是確定的，預處理一下然后判斷即可。
否則 \(v\) 子樹內存在 bot，根據我們一開始的結論 2，如果我們希望 \(i\) 贏，那么我們應該盡可能的讓 \(v\) 子樹的 winner 是個 bot，所以我們直接令所有 bot 的能力值全都為 \(+\infty\) 就可以讓 bot 的贏面最大化，然后把 bot 當成真人一起預處理即可。如果預處理算出來 \(v\) 子樹的 winner 真的是個 bot，再把它的能力值改為 \(H_v\)（這樣顯然不改變他是 \(v\) 子樹的 winner 這個事實），然后 \(i\) 就贏了；否則 \(v\) 的 winner 是個真人，拿他的能力值和當前高度比較一下判斷他是否守擂成功即可。

復雜度 \(O(Tnm\log n)\)，期望得分 \(40pts\)，拼上 A 性質就有 \(52pts\)。

code：

點擊查看代碼

#include<bits/stdc++.h>
#define Debug puts("------------------------")
#define LL long long 
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define fa(p) (p/2)
#define bro(p) (p^1) 
using namespace std;
const int N=3e5+5;
inline int read(){
	int w=1,s=0;
	char c=getchar();
	for(;c<'0'||c>'9';w*=(c=='-')?-1:1,c=getchar()) ;
	for(;c>='0'&&c<='9';s=s*10+c-'0',c=getchar()) ;
	return w*s;
}
int n,m,T,t[N],a[N],c[N],d[20][N],X[5],K,ans[N],lg[N],num,id[N],rt[20],L[N],R[N],H[N],G[N];
char s[N];
void build(int p,int l,int r,int h){
	L[p]=l,R[p]=r,H[p]=h,G[p]=l/(1<<h)+1,num=p;
	if(l==1) rt[h]=p;
	if(l==r) return id[l]=p,void();
	int mid=(l+r)>>1;
	build(ls(p),l,mid,h-1),build(rs(p),mid+1,r,h-1);
}
void Read(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&t[i]);
	for(int i=1;i<=m;i++) scanf("%d",&c[i]);
	while((1<<K)<n) K++;
	for(int i=1;i<=K;i++){
		scanf("%s",s+1);
		for(int j=1;j<=(1<<(K-i));j++) d[i][j]=s[j]-'0';
	}
	scanf("%d",&T);
	for(int i=1;i<=n;i++) lg[i]=((1<<__lg(i))==i)?__lg(i):(__lg(i)+1);
	build(1,1,(1<<K),K);
}
int f[N];
void dfs(int p,int n){
	if(L[p]==R[p]) return f[p]=L[p],void();
	dfs(ls(p),n),dfs(rs(p),n);
	int x=f[ls(p)],y=f[rs(p)];
	if(d[H[p]][G[p]]==0) f[p]=(x>n||a[x]>=H[p])?x:y;
	else f[p]=(y>n||a[y]>=H[p])?y:x;  
}
bool check(int i,int n){
	int u=id[i],v,fa,root=rt[lg[n]];
	while(u!=root){
		v=bro(u),fa=fa(u);
		if(d[H[fa]][G[fa]]==(u&1)){
			if(i<=n&&a[i]<H[fa]) return false;
		}
		else if(f[v]<=n&&a[f[v]]>=H[fa]) return false;
		u=fa;
	}
	return true;
}
void work(){
	for(int _=1;_<=m;_++){
		int n1=c[_];
		ans[_]=0;
		dfs(rt[lg[n1]],n1);
		for(int i=1;i<=(1<<lg[n1]);i++) ans[_]+=check(i,n1)*i;
	}
	LL res=0;
	for(int i=1;i<=m;i++) res^=1ll*i*ans[i];
	printf("%lld\n",res);
}
signed main(){
// 	freopen("arena.in","r",stdin);
// 	freopen("arena.out","w",stdout);
	Read();
	while(T--){
		for(int i=0;i<=3;i++) scanf("%d",&X[i]);
		for(int i=1;i<=n;i++) a[i]=t[i]^X[i%4];
		work();
	}
	return 0;
}

\(O(T(n\log n+m))\)

對 \(m\) 個詢問每個都單獨算一遍顯然沒有前途，考慮能不能一起處理。
我們稱二叉樹左鏈上的點為關鍵點（或者說 \(L_u=1\) 的點），可以發現每個詢問其實都是在問某一個關鍵點子樹內的答案（只不過不同的詢問可能會導致一些真人變成 bot 而已），我們稱這個關鍵點為這個詢問的查詢點。
所以我們仍然考慮對每個點計算貢獻，但是在他往上跳的過程中，每跳到一個關鍵點就貢獻到所有以這個關鍵點為查詢點的詢問。

由于現在我們是一起處理所有詢問，因此每個點 \(i\le n\) 既可能是真人也可能是 bot，我們把點 \(i\) 是真人和 bot 的情況都做一遍即可。
還是假設現在爬到點 \(u\)，\(u\) 的兄弟是 \(v\)：

如果擂主是 \(i\)，如果 \(i\) 能力值不夠那他是真人的情況就寄了，但是他是 bot 的情況仍然是可行的；否則兩種情況都是可行的。
如果擂主是 \(v\) 子樹的 winner，這個時候就有點麻煩了，因為現在我們不能確定到底哪些人是真人，哪些人是 bot。

我們不妨先假設所有 \(i\le n\) 都是真人，對于那些完全 bot，仍然像上面所說的那樣把他的能力值設為 \(+\infty\)，然后跑一遍樹形 DP 預處理出 \(f_u\) 表示此時每棵子樹的 winner。
如果 \(f_v\) 是個完全 bot 或者是個能力值沒達到 \(H_{fa_u}\) 的真人，那么不管詢問是啥樣的，\(i\) 都可以直接獲勝，因為即使把某個真人變成 bot 了我們也可以把這個 bot 的能力值設成他原先的能力值，然后復現 \(v\) 子樹內的對局情況。

否則，如果 \(i\) 想要獲勝，那么詢問的 \(c_i\) 應該要使得 \(v\) 子樹的 winner 能是個 bot。
注意到一個事情：如果 \(c_i=n'\) 時 \(v\) 子樹的 winner 能是個 bot，那么 \(c_i<n'\) 時 \(v\) 子樹的 winner 也一定能是個 bot。
因此我們樹形 DP 預處理出 \(g_u\) 表示能使得 \(u\) 子樹的 winner 是個 bot 的最大的詢問 \(n'\)（具體求法下面有），然后在整個過程中維護一個變量 \(mn\)（初始為 \(n\)），表示要使得 \(i\) 成為 winner 的詢問的上限。每次出現這個情況就令 \(\min(mn,g_v) \to mn\)。

然后是貢獻答案。當 \(i\) 跳到某個關鍵點 \(u\) 時，考慮有哪些以 \(u\) 為查詢點的詢問 \(c\) 可以以 \(i\) 為最終的 winner：

顯然需要滿足 \(c \in (R_{ls_u},R_u]\)，否則不可能以 \(u\) 為關鍵點。
然后我們上面維護了一個上界 \(mn\)，因此 \(c \in [1,mn]\)。
最后，如果一開始我們欽定了 \(i\) 是真人，那么應滿足 \(c \in [i,n]\)；否則應滿足 \(c \in [1,i)\)。

這三個區間的交即為可能讓 \(i\) 成為 winner 的詢問區間，用差分前綴和實現區間加即可。

最后稍微提一下 \(g\) 是咋 DP 的，算 \(g_u\) 的時候，不妨設 \(ls\) 是擂主，那么：

如果 \(a_{f_{ls}}\ge H_u\)，令 \(g_{ls} \to g_u\)：若 \(f_{ls}\) 是個完全 bot，那么 \(g_u=g_{ls}=n\) 沒有問題；否則，只要 \(ls\) 的 winner 仍然不是 bot，\(ls\) 的 winner 始終能守擂成功，\(u\) 的 winner 也始終不能是 bot。
否則，只要左右子樹其中一個的 winner 是 bot 就好了：\(\max(g_{ls},g_{rs}) \to g_u\)。

總復雜度 \(O(T(n\log n+m))\)，期望得分 \(68pts\)，實際得分 \(\ge 76pts\)。
記得特判 \(c_i=1\)。

code：

點擊查看代碼

#include<bits/stdc++.h>
#define Debug puts("------------------------")
#define LL long long 
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define fa(p) (p>>1)
#define bro(p) (p^1) 
using namespace std;
const int N=3e5+5;
inline int read(){
	int w=1,s=0;
	char c=getchar();
	for(;c<'0'||c>'9';w*=(c=='-')?-1:1,c=getchar()) ;
	for(;c>='0'&&c<='9';s=s*10+c-'0',c=getchar()) ;
	return w*s;
}
int n,m,T,t[N],a[N],c[N],d[20][N],X[5],K,lg[N],num,id[N],rt[20],L[N],R[N],H[N],G[N];
LL ans[N];
char s[N];
void build(int p,int l,int r,int h){
	L[p]=l,R[p]=r,H[p]=h,G[p]=l/(1<<h)+1,num=p;
	if(l==1) rt[h]=p;
	if(l==r) return id[l]=p,void();
	int mid=(l+r)>>1;
	build(ls(p),l,mid,h-1),build(rs(p),mid+1,r,h-1);
}
void Read(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&t[i]);
	for(int i=1;i<=m;i++) scanf("%d",&c[i]);
	while((1<<K)<n) K++;
	for(int i=1;i<=K;i++){
		scanf("%s",s+1);
		for(int j=1;j<=(1<<(K-i));j++) d[i][j]=s[j]-'0';
	}
	scanf("%d",&T);
	for(int i=1;i<=n;i++) lg[i]=((1<<__lg(i))==i)?__lg(i):(__lg(i)+1);
	for(int i=n+1;i<=(1<<K);i++) a[i]=INT_MAX;
	build(1,1,(1<<K),K);
}
int f[N],g[N];
void dfs(int p){
	if(L[p]==R[p]) return f[p]=L[p],g[p]=(L[p]>n)?n:(L[p]-1),void();
	dfs(ls(p)),dfs(rs(p));
	int x=f[ls(p)],y=f[rs(p)];
	if(d[H[p]][G[p]]==0){
		if(a[x]>=H[p]) f[p]=x,g[p]=g[ls(p)];
		else f[p]=y,g[p]=max(g[ls(p)],g[rs(p)]);
	}
	else{
		if(a[y]>=H[p]) f[p]=y,g[p]=g[rs(p)];
		else f[p]=x,g[p]=max(g[ls(p)],g[rs(p)]);	
	} 
}
void modify(int l,int r,int x){if(l<=r) ans[l]+=x,ans[r+1]-=x;}
void update(int i){
	int u=id[i],v,fa,mn=n;
	bool flag=(i<=n);  //i 是否可以作為真人成為 winner 
	while(u!=1){
		fa=fa(u),v=bro(u);
		if(d[H[fa]][G[fa]]==(u&1)){
			if(a[i]<H[fa]) flag=false;
		}
		else{
			if(a[f[v]]>=H[fa]) mn=min(mn,g[v]);
		}
		u=fa;		
		if(L[u]==1){
			if(flag) modify(max(R[ls(u)]+1,i),min(R[u],mn),i);
			modify(R[ls(u)]+1,min({R[u],i-1,mn}),i); 
		}
	}
}
void work(){
	for(int i=1;i<=n+1;i++) ans[i]=0;
	dfs(1);
	for(int i=1;i<=(1<<K);i++) update(i);
	for(int i=1;i<=n;i++) ans[i]+=ans[i-1];
	ans[1]=1;
	LL res=0;
	for(int i=1;i<=m;i++) res^=1ll*i*ans[c[i]];
	printf("%lld\n",res);
}
signed main(){
// 	freopen("arena.in","r",stdin);
// 	freopen("arena.out","w",stdout);
	Read();
	while(T--){
		for(int i=0;i<=3;i++) scanf("%d",&X[i]);
		for(int i=1;i<=n;i++) a[i]=t[i]^X[i%4];
		work();
	}
	return 0;
}

\(O(T(n+m))\)

注意到關鍵點只有 \(O(K)\) 個，且每個關鍵點只有他子樹內的葉子可以在他上面產生貢獻，而每個高度的關鍵點只有一個，因此關鍵點子樹內的葉子個數之和是 \(\sum_{i=0}^K 2^i = O(n)\) 的，換句話說區間加的總次數是 \(O(n)\) 的。
同理我遍歷每個關鍵點的子樹復雜度也是 \(O(n)\) 的，可以接受。

因此我們不再從下往上貢獻，而是直接對每個關鍵點從上往下遍歷他的子樹并計算這個關鍵點上的答案。
我們回顧一下上面 \(i\) 向上爬的流程：

若他是擂主，直接根據它的能力值和 \(H_u\) 判斷它是否寄了。
若他不是擂主且 \(f_v\) 可以成功守擂，令 \(\min(mn,g_v) \to mn\)。

發現這些操作其實是互相獨立的，我們沒有必要按照 \(i\) 所在點 \(u\) 從下到上的順序依次去執行每一個操作，我們完全可以先把所有要執行的操作存下來，然后先執行第一類操作，再執行第二類操作。
并且我們還發現一個很好的事情，這兩個操作都是可以合并的！
也就是說，對于操作 1，我們可以先求出所有 \(H_u\) 的 \(\max\) 再看一下是否有 \(a_i \ge \max(H_u)\)；對于第二類操作，反正你按照任何順序合并最后取 \(\min\) 的結果都是不變的。
這就為我們從上往下處理提供了良好的條件，具體的，我們在 dfs 的時候維護兩個變量 \(lim\) 和 \(mn\)，當 dfs 到一個點 \(u\) 時：

若 \(u\) 和兄弟 \(v\) 決斗時，\(u\) 是擂主就令 \(\max(lim,H_{fa_u}) \to lim\)。
否則若 \(a_{f_v} \ge H_{fa_u}\)，就令 \(\min(g_v,mn) \to mn\)。

最后當遍歷到一個葉子 \(i\) 時，就看一下 \(a_i\) 和 \(lim\) 的關系并通過 \(mn\) 決定如何貢獻即可。

復雜度 \(O(T(n+m))\)，期望得分 \(100pts\)，CCF 機子實際得分 \(???\)，洛谷實際得分 \(88pts\)。
code：

點擊查看代碼

#include<bits/stdc++.h>
#define Debug puts("------------------------")
#define LL long long 
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define fa(p) (p>>1)
#define bro(p) (p^1) 
using namespace std;
const int N=3e5+5;
inline int read(){
	int w=1,s=0;
	char c=getchar();
	for(;c<'0'||c>'9';w*=(c=='-')?-1:1,c=getchar()) ;
	for(;c>='0'&&c<='9';s=s*10+c-'0',c=getchar()) ;
	return w*s;
}
int n,m,T,t[N],a[N],c[N],d[20][N],X[5],K,lg[N],num,id[N],rt[20],L[N],R[N],H[N],G[N];
LL ans[N];
char s[N];
void build(int p,int l,int r,int h){
	L[p]=l,R[p]=r,H[p]=h,G[p]=l/(1<<h)+1,num=p;
	if(l==1) rt[h]=p;
	if(l==r) return id[l]=p,void();
	int mid=(l+r)>>1;
	build(ls(p),l,mid,h-1),build(rs(p),mid+1,r,h-1);
}
void Read(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&t[i]);
	for(int i=1;i<=m;i++) scanf("%d",&c[i]);
	while((1<<K)<n) K++;
	for(int i=1;i<=K;i++){
		scanf("%s",s+1);
		for(int j=1;j<=(1<<(K-i));j++) d[i][j]=s[j]-'0';
	}
	scanf("%d",&T);
	for(int i=1;i<=n;i++) lg[i]=((1<<__lg(i))==i)?__lg(i):(__lg(i)+1);
	for(int i=n+1;i<=(1<<K);i++) a[i]=INT_MAX;
	build(1,1,(1<<K),K);
}
int f[N],g[N];
void dfs(int p){
	if(L[p]==R[p]) return f[p]=L[p],g[p]=(L[p]>n)?n:(L[p]-1),void();
	dfs(ls(p)),dfs(rs(p));
	int x=f[ls(p)],y=f[rs(p)];
	if(d[H[p]][G[p]]==0){
		if(a[x]>=H[p]) f[p]=x,g[p]=g[ls(p)];
		else f[p]=y,g[p]=max(g[ls(p)],g[rs(p)]);
	}
	else{
		if(a[y]>=H[p]) f[p]=y,g[p]=g[rs(p)];
		else f[p]=x,g[p]=max(g[ls(p)],g[rs(p)]);	
	} 
}
void modify(int l,int r,int x){if(l<=r) ans[l]+=x,ans[r+1]-=x;}
void solve(int u,int lim,int mn,int root){
	int fa=fa(u),v=bro(u);
	if(d[H[fa]][G[fa]]==(u&1)) lim=max(lim,H[fa]);
	else if(a[f[v]]>=H[fa]) mn=min(mn,g[v]);
	if(L[u]==R[u]){
		int i=L[u];
		if(a[i]>=lim) modify(max(R[ls(root)]+1,i),min(R[root],mn),i);
		modify(R[ls(root)]+1,min({R[root],i-1,mn}),i);			
		return;
	}
	solve(ls(u),lim,mn,root),solve(rs(u),lim,mn,root);
}
void work(){
	for(int i=1;i<=n+1;i++) ans[i]=0;
	dfs(1);
	for(int i=1;i<=K;i++) solve(ls(rt[i]),0,n,rt[i]),solve(rs(rt[i]),0,n,rt[i]);
	for(int i=1;i<=n;i++) ans[i]+=ans[i-1];
	ans[1]=1;
	LL res=0;
	for(int i=1;i<=m;i++) res^=1ll*i*ans[c[i]];
	printf("%lld\n",res);
}
signed main(){
// 	freopen("arena.in","r",stdin);
// 	freopen("arena.out","w",stdout);
	Read();
	while(T--){
		for(int i=0;i<=3;i++) scanf("%d",&X[i]);
		for(int i=1;i<=n;i++) a[i]=t[i]^X[i%4];
		work();
	}
	return 0;
}

卡常

這個做法雖說是線性的但是常數有點大，而且時限不太充裕。
想要通過只要加上下面兩個優化就好了：

把計算 \(f,g\) 的樹形 DP 寫成非遞歸的循環形式。
遍歷子樹的時候，如果當前的 \(mn\) 已經比子樹根節點左子樹的 \(R+1\) 要小了，最后計算出的區間的交一定為空，直接返回即可。

期望得分 \(100pts\)，實際得分 \(100pts\)。

code

#include<bits/stdc++.h>
#define Debug puts("------------------------")
#define LL long long 
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define fa(p) (p>>1)
#define bro(p) (p^1) 
using namespace std;
const int N=3e5+5;
int n,m,T,t[N],a[N],c[N],d[20][N],X[5],K,lg[N],num,id[N],rt[20],L[N],R[N],H[N],G[N];
LL ans[N];
char s[N];
void build(int p,int l,int r,int h){
	L[p]=l,R[p]=r,H[p]=h,G[p]=l/(1<<h)+1,num=p;
	if(l==1) rt[h]=p;
	if(l==r) return id[l]=p,void();
	int mid=(l+r)>>1;
	build(ls(p),l,mid,h-1),build(rs(p),mid+1,r,h-1);
}
void Read(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&t[i]);
	for(int i=1;i<=m;i++) scanf("%d",&c[i]);
	while((1<<K)<n) K++;
	for(int i=1;i<=K;i++){
		scanf("%s",s+1);
		for(int j=1;j<=(1<<(K-i));j++) d[i][j]=s[j]-'0';
	}
	scanf("%d",&T);
	for(int i=1;i<=n;i++) lg[i]=((1<<__lg(i))==i)?__lg(i):(__lg(i)+1);
	for(int i=n+1;i<=(1<<K);i++) a[i]=INT_MAX;
	build(1,1,(1<<K),K);
}
int f[N],g[N];
void DP(){
	for(int p=num;p>=1;p--){
		if(L[p]==R[p]){
			f[p]=L[p],g[p]=(L[p]>n)?n:(L[p]-1);
			continue;
		}
		int x=f[ls(p)],y=f[rs(p)];
		if(d[H[p]][G[p]]==0){
			if(a[x]>=H[p]) f[p]=x,g[p]=g[ls(p)];
			else f[p]=y,g[p]=max(g[ls(p)],g[rs(p)]);
		}
		else{
			if(a[y]>=H[p]) f[p]=y,g[p]=g[rs(p)];
			else f[p]=x,g[p]=max(g[ls(p)],g[rs(p)]);	
		} 
	}
}
void modify(int l,int r,int x){if(l<=r) ans[l]+=x,ans[r+1]-=x;}
void solve(int u,int lim,int mn,int root){
	if(mn<R[ls(root)]+1) return;
	int fa=fa(u),v=bro(u);
	if(d[H[fa]][G[fa]]==(u&1)) lim=max(lim,H[fa]);
	else if(a[f[v]]>=H[fa]) mn=min(mn,g[v]);
	if(L[u]==R[u]){
		int i=L[u];
		if(a[i]>=lim) modify(max(R[ls(root)]+1,i),min(R[root],mn),i);
		modify(R[ls(root)]+1,min({R[root],i-1,mn}),i);			
		return;
	}
	solve(ls(u),lim,mn,root),solve(rs(u),lim,mn,root);
}
void work(){
	for(int i=1;i<=n+1;i++) ans[i]=0;
	DP();
	for(int i=1;i<=K;i++) solve(ls(rt[i]),0,n,rt[i]),solve(rs(rt[i]),0,n,rt[i]);
	for(int i=1;i<=n;i++) ans[i]+=ans[i-1];
	ans[1]=1;
	LL res=0;
	for(int i=1;i<=m;i++) res^=1ll*i*ans[c[i]];
	printf("%lld\n",res);
}
signed main(){
// 	freopen("arena.in","r",stdin);
// 	freopen("arena.out","w",stdout);
	Read();
	while(T--){
		for(int i=0;i<=3;i++) scanf("%d",&X[i]);
		for(int i=1;i<=n;i++) a[i]=t[i]^X[i%4];
		work();
	}
	return 0;
}

總結

現在看來，這確實是一道不錯的題，沒有用到高深的數據結構和復雜度的動態規劃，也沒有很非人類的結論，碼量也很小，但是確實有一定難度。
就我個人觀點來看：

\(16pts\) 或者 \(24pts\) 應該是送的分。
\(40pts\) 是基本分，只需要分析出一點性質就可以了。
\(52pts\) 我去年拿不到純粹是我自己唐。即使不用平衡樹的寫法，這個拆貢獻的思路也比較套路。
\(76pts\) 是分水嶺，我想不到也可以理解。
\(100pts\) 其實相當對來講是比較簡單的，想到從上往下計算之后，后面的思路有點對著 \(76pts\) 的代碼優化的意思了（\(76pts \to 88pts\) 的代碼確實也不需要改很多）。至于卡常的問題，我覺得 CCF 的少爺機你不卡常也是能拿到很好看的分數的。

最后，祝所有選手 CSP2025 RP++！！！

Update：這下把自己的 RP 加成負數了，CSP 爆炸了。

posted @ 2025-10-30 21:33 Green&White 閱讀(17) 評論(0) 收藏舉報

刷新頁面返回頂部

OIer_Cyq

[CSP-S 2024] 擂臺游戲題解

約定

觀察

\(O(Tn^2m)\) + \(A\) 性質

\(O(Tnm\log n)\)

\(O(T(n\log n+m))\)

\(O(T(n+m))\)

卡常

總結

公告

OIer_Cyq

[CSP-S 2024] 擂臺游戲 題解

約定

觀察

\(O(Tn^2m)\) + \(A\) 性質

\(O(Tnm\log n)\)

\(O(T(n\log n+m))\)

\(O(T(n+m))\)

卡常

總結

公告

[CSP-S 2024] 擂臺游戲題解