空之碎物

超级无敌结论题。与图论无关的两只

\log

做法。

按位考虑。发现最终的数一个二进制位上一定能被写成

(((x_1\ominus x_2)\ominus x_3)\ominus...)\ominus x_k

的形式，而这个东西能取到

1

当且仅当

x_1=1

且

\forall i\in[2,k] x_i=0

（注意这里的

x_k

并不一定是原序列中的某个数的该二进制位，也有可能是若干个数该二进制位下操作的结果）。

Observation

1

x\ominus y\leq x

。

证明：显然。

Observation

2

: 若至少有

2

个数，则取

k=2

一定不劣。

证明：考虑

x_1\ominus (((x_2\ominus x_3)\ominus ... )\ominus x_k)

。若原来的那个形式能取到

1

，则现在这个形式依旧能取到

1

。

Observation

3

: 当

r-l+1>26

时，

f(l,r)=\max_{i=l}^{r} a_i

。

证明：取

x_1=\max_{i=l}^{r} a_i

。则我们需要做的事情就是尽可能让

x_1

取值为

1

的那些二进制位保持为

1

。

构造是容易的，不妨让剩下的数按照

(((x_2\ominus x_3)\ominus x_4)\ominus...)\ominus x_k

的形式操作，对于一个二进制位，如果除了

x_1

以外剩下的数里面有

\geq 2

个为

1

的，那么无论如何操作最终这一位一定是

0

。所以当剩余数个数

>25

时一定存在一种操作方案是的最终与

x_1

操作的数为

0

。而由于

x\ominus y\leq x

，所以我们在

r-l+1>26

时答案一定为区间最大值。

Observation

4

: 当

r-l+1\neq 3

时，

f(l,r)

的值一定由 Observation

3

中的构造方式得来（即除去最大值以外的数按某个顺序依次操作，最后最大值操作这个结果）。

上述已经证明

k=2

，所以问题转化为

x_2

在

x_1

的那些为

1

的位尽量为

0

。

证明：

显然

x_1

一定是一个数，不然把其他数丢进

x_2

里不劣，同时

x_2

一定是按顺序依次操作，因为这样只会让

x_2

更小。

如果存在

x_1'<x_1

且

x_1'\ominus x_2'>x_1\ominus x_2

，那么令

i

为

x_1>x_1'

的最高位，

j

为

x_1'\ominus x_2'>x_1\ominus x_2

的最高位。可以得到

i>j

，且

x_2(i)=1

。对于所有

i'>i

且

x_1(i')=1

，显然

x_1'(i')=1

。此时其他任何数都无法充当

i'

位唯一一个

1

。所以，对于第

i

位，其他但凡有一个数为

0

或至少两个数为

1

，那么

x_2(i)

就一定为

0

，这与上述矛盾。

唯一的反例出现在

r-l+1=3

，即除了

x_1,x_1'

以外的最后一个数该位上为

1

的情况。而且反例很好找，好找到样例

2

就有。

于是剩下的就不难了，从高位到低位贪心，如果这一位

x_1

是

1

且其他数只有一个

1

，把唯一拥有那个

1

的数标记不能充当构成

x_2

的第一个数，如果除了它全被标记了那么这一位无论如何取不到

1

。对于长度

>26

的区间，直接单调栈算出最大值，对于长度

=3

，暴力枚举所有操作方式即可。

时间复杂度：

长度 $=3$ : $O(1)$
长度 $>26$ : $O(n)$
长度 $\in\{2,4,5,..,26\}$ : $O(n\log^2 V)$ （ $n\log V$ 个区间，每个区间计算需要 $\log V$ ）

参考代码：

CPP

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define _rep(i,a,b) for(int i=(a);i>=(b);i--)
#define subset(i,x) for(int i=(x);i;i=((i-1)&x))
#define pi pair<int,int>
#define arr(a) array<int,(a)>
#define F fflush(stdout)
#define RE return puts("-1"),void()
#define cases(_) while((_)--) solve();
using namespace std;
const int mod=998244353;
inline void ckmin(int& x,int y){x=min(x,y);}
inline void ckmax(int& x,int y){x=max(x,y);}
inline void add(int& x,int y){x=(x%mod+y%mod+mod)%mod;}
inline void mul(int& x,int y){x=(x%mod)*(y%mod)%mod;}
const int N=200005,BIT=25;
int _=1,n,a[N],t[BIT+5],flg[BIT+5],vis[N],ans,res,tmp,nxt[N],pre[N];
inline void add(int x){
	if(x==0) return;
	rep(o,0,BIT) if((a[x]>>o)&1) t[o]++,flg[o]=x;
}
inline int f(int x,int y){
	int res=0;
	rep(o,0,BIT) if((x>>o)&1 && !((y>>o)&1)) res+=(1<<o);
	return res;
}
inline int calc(int x,int y,int z){
	int r1=f(f(x,y),z),r2=f(f(x,z),y),r3=f(f(y,z),x),r4=f(f(y,x),z),r5=f(f(z,y),x),r6=f(f(z,x),y);
	int c1=f(z,f(x,y)),c2=f(y,f(x,z)),c3=f(x,f(y,z)),c4=f(z,f(y,x)),c5=f(x,f(z,y)),c6=f(y,f(z,x));
	int a1=max(max(max(r1,r2),r3),max(max(r4,r5),r6));
	int a2=max(max(max(c1,c2),c3),max(max(c4,c5),c6));
	return max(a1,a2);
}
void solve(){
	scanf("%lld",&n),a[0]=-1;
	rep(i,1,n) scanf("%lld",&a[i]);
	rep(l,1,n){
		int mx=0;
		rep(o,0,BIT) t[o]=0,flg[o]=0;
		rep(r,l,min(l+30,n)){
			if(a[r]<=a[mx]) add(r);
			else add(mx),mx=r;
			rep(o,l,r) vis[o]=0;
			int sum=r-l,res1=0;
			_rep(o,BIT,0) if(t[o]==1 && (a[mx]>>o)&1){
				sum-=(vis[flg[o]]==0);
				if(sum==0) sum++,res1+=(1ll<<o);
				else vis[flg[o]]=1;
			}
			if(r-l!=2) add(ans,a[mx]-res1);
			else add(ans,calc(a[l],a[l+1],a[l+2]));
			add(tmp,a[mx]);
		}
	}
	fill(nxt+1,nxt+n+1,n+1);
	stack<int> st;
	rep(i,1,n){
		while(!st.empty() && a[i]>a[st.top()]) nxt[st.top()]=i,st.pop();
		st.push(i);
	}
	while(!st.empty()) st.pop();
	_rep(i,n,1){
		while(!st.empty() && a[i]>=a[st.top()]) pre[st.top()]=i,st.pop();
		st.push(i);
	}
	rep(i,1,n) add(res,(i-pre[i])*(nxt[i]-i)%mod*a[i]);
	add(ans,res-tmp);
	printf("%lld\n",ans);
}
signed main(){
	cases(_);
	return 0;
}

文章操作

相关推荐

评论

空之碎物