专栏文章

题解：P14522 【MX-S11-T3】空之碎物

__Minmatar_Star
P14522题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@min6jf8o
此快照首次捕获于
2025/12/01 21:23
3 个月前
此快照最后确认于
2025/12/01 21:23
3 个月前
查看原文
（该解法最终时间消耗为 1.06s , 最大单组数据 186ms )

题意：

将一个区间 [l,r][l,r] 内的数用二进制不退位减法合并为一个数，使最终得到的数最大，将该值记为 f([l,r])f([l,r]) ，求各个区间所有最大值的总和

解法：

(本文中，w 为 [1,n][1,n] 最大值的二进制位数，计算复杂度时认为 w=25 ，“减”指题目中定义的运算)
初步思想（复杂度 O(wn5)O(wn^5) ) :
一种显而易见的贪心：让一个数作为最终轮被“减”数不变，另一个数“减”去其他区间内的数，最终用最终轮被“减”数减去这个数，更新该区间的最大值。
这种做法中，需要枚举每个区间，并在区间内枚举最终轮被“减”数和“减”数，且每次需要做 nwnw 次运算，最终复杂度 O(wn5)O(wn^5) ，显然无法通过本题
运算小优化（复杂度 O(n5)O(n^5) ) ：
“减”运算实质为对每一位取
CPP
a&(!b)
所以我们可以直接这样做运算
此时复杂度为 O(n5)O(n^5) ，显然仍然无法通过
对长区间的思考（复杂度 O(nw3+n2)O(nw^3+n^2) ) :
我们发现，题目中共有 n2n^2 段区间，显然，最终解法不可能需要枚举每一个区间
我们考虑一个长区间，直觉告诉我们，最终可以使最终轮“减”数变为 0 ，考虑证明这一点。
我们考虑一个数在什么情况下不会变成 0 ，我们发现，当其在有一位 1 是在所有除最终轮被“减”数以外的数中独有时，其不会消去这一位 1 。
显然，每一位 1 最多只能被区间内一个数独有。（独有的概念不考虑最终轮被“减”数中是否有这个数字）
按题目范围，数最多有 25 位，也就是钦定最终轮被“减”数后最多有 25 个数做最终轮“减”数不会变为 0 ，再算上最终轮被“减”数，最多有 26 个数。
因此，r−l+1>26r-l+1>26 的区间，必有选法使最终轮”减“数变为 0 ，即答案为区间最大值。
所以，我们两层循环遍历区间，计算区间最值和，复杂度为 O(n2)O(n^2) 。
为方便实现，我们直接计算所有区间的区间最值和，并在枚举 r−l+1<=26r-l+1<=26 的区间时减去其中的区间最值。
考虑用同样的思想思考 r−l+1<=26r-l+1<=26 的区间的答案，我们想到，应该尽可能让最终轮“减”数独有位中与最终轮被“减”数共有的位的 1 总值（每位的 1 根据所在位有不同实际权，即其所在位的位值）尽量小。
思考什么样的位是最终轮“减”数独有且与最终轮被“减”数共有的，显然，当一个位的 1 在区间内共有两个，且在区间内最终轮被“减”数中存在时，这样的位是最终轮“减”数独有且与最终轮被“减”数共有的。
一个位在区间内的出现个数可以使用前缀和维护，预处理复杂度 O(nw)O(nw) ，单次计算复杂度 O(w)O(w) ，每次枚举区间时计算区间内各个位的个数，需要处理 nwnw 个区间，总复杂度 O(nw2)O(nw^2)
然后我们对于每个 r−l+1<=26r-l+1<=26 区间，枚举其最终轮被“减”数，并根据上述结论进行可能独有位计算（计算每一位是否存在一个数独有且与最终轮被“减”数共有，时间消耗为 O(w)O(w) )。因为独有位是独有的二进制位的集合，所以可以用一个数保存独有位权值和。
区间个数 nwnw ，每个区间枚举 O(w)O(w) 个最终轮被“减”数，进行 ww 次运算统计，该部分复杂度为 O(nw3)O(nw^3) 。
然后枚举最终轮“减”数，我们只需要将其与独有位权值和取与运算，就可以得到其独有位中与最终轮被“减”数共有的位的 1 总值。然后我们用最终轮被“减”数减去这个数，更新该区间内的答案。
区间个数 nwnw ，每个区间枚举 O(w)O(w) 个最终轮被“减”数，枚举 O(w)O(w) 个最终轮“减”数，该部分复杂度为 O(nw3)O(nw^3) 。
然后我们使 sum 减去区间内最大值（原因见上文区间最值和部分），再加上区间内的答案。
综上，该做法复杂度为 O(nw3+n2)O(nw^3+n^2) ，仍然无法通过，我们考虑对两个部分分别进行优化。
最终优化（复杂度 O(nw2)O(nw^2) )：
区间最值和部分，单调栈统计贡献（该部分复杂度 O(n)O(n) ) :
暴力维护区间最值和不可行，我们考虑每个位置的贡献。
显然，每个位置在横跨该位置，且区间内的值不大于该位置的值时是区间内的最大值。
考虑使用单调栈维护位置 i 最靠左的 lil_i 使得 [li,i][l_i,i] 的数小于 i 和位置 i 最靠右的 rir_i 使得 [i,ri][i,r_i] 的数不大于 i （为防止重复元素的贡献被多次或不计算，需要一边小于一边不大于，在这里令左边小于右边不大于），然后该位置的贡献即为 a[i]×(i−li+1)×(ri−i+1)a[i] \times (i-l_i+1) \times (r_i-i+1) ，计算各位置贡献和，即为区间最值和。该做法仅需遍历三次数组，复杂度为 O(n)O(n) 。
枚举部分，使用 set 辅助剪枝（该部分复杂度 O(nw2)O(nw^2) ）：
显然，当一个数作为最终轮被“减”数时，其更新的答案不可能大于这个数本身。
因此当一个数小于等于当前答案时，无需再考虑其为最终轮“减”数的情况。
同时，当区间已经有两个数之后，向一个区间里加数不会使答案更小（直接交给最终轮“减”数去减就行）
所以，我们对同一起点的区间统一处理，将之前的答案保存下来，用于后续更新。
然后用 set 保存区间内每一个可能是最终轮被“减”数的位置，按初值从大到小依次遍历，当发现当前选的值小于等于目前答案时，从当前迭代器开始删除，不再遍历以后的部分。
这样，我们对每个起点的区间选择最终轮被“减”数的次数就是 O(w)O(w) 的。（大概原因：当区间内的数差比较大时，小的会被淘汰，差比较小时，答案会接近最值，较小的会被淘汰。但是我不知道怎么证明这个在最坏数据下也是线性。）
起点个数 nn ，每个起点的区间选择最终轮被“减”数的次数 O(w)O(w) ，每次处理 O(w)O(w) ，最终复杂度 O(nw2)O(nw^2) 。

代码：

CPP
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
namespace KitoTaisu{//快读 
	char *p1,*p2,buf[32769];
	#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,32767,stdin),p1==p2)?EOF:*p1++)
	int read(){
		int x=0,f=1;
		char ch=nc();
		while(ch<48||ch>57){
			if(ch=='-')f=-1;
			ch=nc();
		}
		while(47<ch&&ch<58){
			x=x*10+(ch^48);
			ch=nc();
		}
		return x*f;
	}
	int readstr(char* str){
		int len=0;
		char ch=nc();
		while(ch<37||ch>110){
			ch=nc();
		}
		while(36<ch&&ch<111){
			str[len++]=ch;
			ch=nc();
		}
		str[len]=0;
		return len;
	}
}
using KitoTaisu::read;
using KitoTaisu::readstr;
struct Nephren{
	int id,val;
	bool operator <(const Nephren a)const{
		return val>a.val;
	}
};
#define si set<Nephren>::iterator
#define md 998244353
set<Nephren> pss;
int n,Max,mx,ztn,zt[27],tmp[27],a[200002],pre[200002][27];
long long sum;//善用long long使常数不大的同时能保存足够大的数 
//debug的时候以为这有问题最终没用这个函数 
void menus(int* mnd,int* mns,int* ans){//求区间内各位的出现次数  
	for(int i=0;i<25;++i){
		ans[i]=mnd[i]-mns[i]; 
	}
} 
int len,kl[200002],kr[200002],stk[200002];
int main(){
	n=read();
	for(int i=1;i<=n;++i){
		a[i]=read();
		for(int j=0;j<25;++j){
			if(a[i]&(1<<j)){
				pre[i][j]=pre[i-1][j]+1;//前缀和预处理区间内各位的出现次数 
			}
			else pre[i][j]=pre[i-1][j];
		}
	}
	for(int i=1;i<=n;++i){
		while(len&&a[stk[len]]<=a[i]){ //单调栈维护点贡献可达的最右端 
			kr[stk[len]]=i-1;
			len--;
		}
		stk[++len]=i;
	}
	while(len){
		kr[stk[len]]=n;
		len--;
	}
	for(int i=n;i;--i){
		while(len&&a[stk[len]]<a[i]){//单调栈维护点贡献可达的最左端，注意要单边取等，避免相等时出现问题 
			kl[stk[len]]=i+1;
			len--;
		}
		stk[++len]=i;
	}
	while(len){
		kl[stk[len]]=1;
		len--;
	}
	for(int i=1;i<=n;i++){
		sum+=(long long)(a[i])*(i-kl[i]+1)%md*(kr[i]-i+1)%md;//计算区间最值和 
		sum%=md;
	}
//	for(int i=1;i<=n;i++){//O(n^2)的区间最值和 
//		mx=0;
//		for(int j=i;j<=n;j++){
//			mx=max(mx,a[j]);
//			sum+=mx;
//		}
//	}
	for(int i=1;i<n;++i){
		sum+=(Max=max(a[i]-(a[i]&a[i+1]),a[i+1]-(a[i]&a[i+1])))-(mx=max(a[i],a[i+1]));//特判长度为2的区间，并计算起点枚举初值
		// a[i]-(a[i]&a[i+1]) 是二进制不退位减法的另一种O（1）实现 
		sum=(sum+md)%md;//只在这里取余数，降低常数 
		pss.clear();
		if(a[i]>Max)pss.insert({i,a[i]});
		if(a[i+1]>Max)pss.insert({i+1,a[i+1]});
		//set初始情况 
		for(int j=2,k=i+2;j<27&&k<=n;++j,++k){
			if(a[k]>Max){
				pss.insert({k,a[k]});//加入可能的最终轮被“减”数 
			}
			si itl=pss.begin(),itr=pss.end();
			for(int p=0;p<25;++p){
				zt[p]=pre[k][p]-pre[i-1][p];//求出现次数 
			}
			for(si it=itl;it!=itr;++it){
				if((it->val)<=Max){
					pss.erase(it,itr);//将不再可能是该起点最终轮被“减”数的数删去 
					break;
				}
				ztn=0;
				for(int p=0;p<25;++p){
					if(((it->val)&(1<<p))&&zt[p]==2)ztn+=(1<<p);//权值和计算 
				}
				for(int p=0;p<=j;++p){
					if(i+p==(it->id))continue;//最终轮两个数不能是同一个 
					tmp[p]=a[i+p]&ztn;//计算最终轮“减”数最终实际值 
					Max=max(Max,(it->val)-tmp[p]);//更新答案 
				}
			}
			mx=max(mx,a[k]);
			sum+=Max-mx+md;//区间最值和中计算了所有区间的最值，在这里减去 
		}
	}
	printf("%lld",sum);
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...