题目传送门

怎么题解区都没有证明，我来一发带证明的。虽然这个证明又臭又长。

思路

part I

先考虑如何求出一个长度为 $m$ 的子数组的答案。

首先二分答案 $x$，将原串转为 $01$ 串，$\ge x$ 的变为 $1$，否则变为 $0$，原操作变为选择相邻两个进行 $\operatorname{bitand}$ 和 $\operatorname{bitor}$。

对 $m$ 的奇偶性进行分讨。

为了方便，把原 $01$ 串称为 $t$，用 $[l,r]$ 表示 $t_lt_{l+1}\cdots t_r$ 构成的子串。这里不考虑 $t$ 全 $0$ 的情况。

奇数

若 $m$ 为奇数，则最后一次操作为 $\operatorname{bitor}$。

观察到我们可以把形如 $1s_1s_2s_3\cdots s_{2k}$ 或 $s_1s_2s_3\cdots s_{2k}1$ 的一个串经过 $2k$ 次操作后变为 $1$。为了方便，我们将这个操作成为“清除”。

枚举串中的每个 $1$，设下标为 $i$，若 $i$ 是奇数则分别对 $[i,m]$ 和 $[1,i]$ 进行“清除”，一定可行。

否则每个满足 $t_i=1$ 的 $i$ 都是偶数。

此时若 $m=3$ 则一定不行。

否则，随便找一个 $1$，它的左右两边一定有一边有 $\ge2$ 个数，在这里进行一次 $\operatorname{bitand}$，然后在另外一边进行一次 $\operatorname{bitor}$，此时这个 $1$ 新的下标就变为奇数了，一定可行。

综上，只要 $t\ne010$ 就一定可行，否则不行。

偶数

若 $m$ 为奇数，则最后一次操作为 $\operatorname{bitand}$，需要在最后一次操作前保留 $2$ 个 $1$。

所以若 $t$ 只有 $1$ 个 $1$ 一定不行。

枚举串中的每两个 $1$，设下标分别为 $i,j(i<j)$。

若 $i$ 为奇数，那么此时 $[i+1,m]$ 是一个长度为奇数的串。根据上面的讨论，只要 $[i+1,m]\ne010$，然后对 $[1,i]$ 进行“清除”，就一定可行。

（这里注意到当 $i$ 为奇数，$j$ 为偶数时一定可以，下面要用。）

但是若 $[i+1,m]=010$ 也未必不行。只要 $i\ge4$，就可以用在 $[1,i-1]$ 中进行两次 $\operatorname{bitand}$ 来换两次在 $[i+1,m]$ 的 $\operatorname{bitor}$，此时局面就变成一定可行了。

也就是说，当 $i$ 为奇数时，只有当 $t=1010$ 或 $t=001010$ 时不行，否则可行。

若 $j$ 为偶数，此时将 $t$ reverse 一下就变为了 $i$ 为奇数的情况，同上有 $t=0101$ 或 $t=010100$ 时不行。

最后一种情况，$i$ 为偶数，$j$ 为奇数。只要 $i\ge 3$ 或 $j\le m-2$，假设是后者，那么你对 $[m-1,m]$ 进行 $\operatorname{bitand}$，然后对 $[1,2]$ 进行 $\operatorname{bitor}$，此时新的序列就变为 $i$ 奇 $j$ 偶了，一定可行。

否则 $i=2,j=m-1$。此时若 $j-i-1<3$ 即 $t=0110$ 或 $t=010010$ 时一定不行，否则可以用在 $[i+1,j-1]$ 中进行两次 $\operatorname{bitand}$ 来换在 $[1,i]$ 和 $[j,m]$ 的 $\operatorname{bitor}$，此时局面就变成一定可行了。

综上，只要 $t$ 的 $1$ 的个数 $\ge2$ 且 $t\ne1010\land t\ne 0101\land t\ne 0110\land t\ne 001010\land t\ne 010100 \land t\ne 010010$ 就一定可行，否则不行。

part II

你发现上面一次 check 都是 $O(N)$ 的，所以就可以得到 $O(N^3)$ 做法。

进一步发现：当 $m$ 为奇数时，大多数 $t$ 只要有 $1$ 个 $1$ 就够了；而当 $m$ 为偶数时，大多数 $t$ 只要有 $2$ 个 $1$ 就够了。也就是说，对于大多数 $t$，若长度为奇数，则答案为最大值，否则长度为偶数，答案为次大值。

对于剩下的这些“另类”，它们的长度都很小，不超过 $6$，可以暴力计算答案。

于是我们可以把问题变成：求每个长度为奇数的连续子数组的最大值和每个长度为偶数的连续子数组的次大值的和。然后对每个长度 $\le6$ 的连续子数组暴力修改贡献。

此时复杂度变为 $O(N^2)$。

part III

仔细思考发现“求每个长度为奇数的连续子数组的最大值和每个长度为偶数的连续子数组的次大值的和”并不是一件困难的事情，只需要对每个 $i$ 求出其左右两边第一、二个大于它的位置，然后枚举连续子数组的长度奇偶性和最 / 次大值的位置即可。使用并查集实现，时间复杂度 $O(N\alpha(N))$。

（其实可以用链表做到 $O(N)$，只不过这只蒟蒻写代码时没想到。）

AC code

#include<bits/stdc++.h>
using namespace std;
namespace cs{
	#define LL long long
	#define fir first
	#define sec second
	typedef pair<int,int> PII;
	const int N=1e6;
	const int INF=2e9;
	int n,a[N+5],bck[N+5],li[N+5],lgr[N+5],lsgr[N+5],rgr[N+5],rsgr[N+5];
	int ldsu[N+5],rdsu[N+5];
	int Getfal(int x){return ldsu[x]==x?x:ldsu[x]=Getfal(ldsu[x]);}
	inline void Mergel(int x,int y){ldsu[Getfal(x)]=Getfal(y);}
	int Getfar(int x){return rdsu[x]==x?x:rdsu[x]=Getfar(rdsu[x]);}
	inline void Merger(int x,int y){rdsu[Getfar(x)]=Getfar(y);}
	LL ans;
	bool check(int L,int R,int d){
		int e1=0;
		string t="";
		for(int i=L;i<=R;i++){
			if(a[i]>=d){
				e1++;
				t+='1';
			}
			else t+='0';
		}
		if(e1==0) return false;
		if((R-L+1)&1){
			return t!="010";
		}
		if(e1==1) return false;
		return t!="1010"&&t!="0101"&&t!="0110"&&t!="001010"&&t!="010100"&&t!="010010";
	}
	int Find(int L,int R,int ma,int sma){
		if((R-L+1)&1){
			if(R-L+1!=3) return ma;
		}
		else{
			if(R-L+1!=4&&R-L+1!=6) return sma;
		}
		int l=1,r=n,mid,rtn=0;
		while(l<=r){
			mid=l+r>>1;
			if(check(L,R,mid)){
				rtn=mid;
				l=mid+1;
			}
			else r=mid-1;
		}
		return rtn;
	}
	inline int count(int L,int R,int p){
		if(L>R) return 0;
		if(p) return ((R+1)>>1)-(L>>1);
		return (R>>1)-((L-1)>>1);
	}
	int main(){
		ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			bck[a[i]]++;
		}
		for(int i=1;i<=n;i++){
			bck[i]+=bck[i-1];
		}
		for(int i=n;i>=1;i--){
			bck[i]=bck[i-1]+1;
		}
		for(int i=1;i<=n;i++){
			li[bck[a[i]]++]=i;
			ldsu[i]=rdsu[i]=i;
		}
		ldsu[0]=rdsu[0]=0;
		ldsu[n+1]=rdsu[n+1]=n+1;
		for(int j=1,i=li[j];j<=n;j++,i=li[j]){
			lgr[i]=Getfal(i-1);
			lsgr[i]=Getfal(max(lgr[i]-1,0));
			rgr[i]=Getfar(i+1);
			rsgr[i]=Getfar(min(rgr[i]+1,n+1));
			Mergel(i,i-1);
			Merger(i,i+1);
		}
		for(int i=1;i<=n;i++){
			ans+=(LL)a[i]*count(lgr[i]+1,i,0)*count(i,rgr[i]-1,0);
			ans+=(LL)a[i]*count(lgr[i]+1,i,1)*count(i,rgr[i]-1,1);
			ans+=(LL)a[i]*count(lsgr[i]+1,lgr[i],0)*count(i,rgr[i]-1,1);
			ans+=(LL)a[i]*count(lsgr[i]+1,lgr[i],1)*count(i,rgr[i]-1,0);
			ans+=(LL)a[i]*count(lgr[i]+1,i,0)*count(rgr[i],rsgr[i]-1,1);
			ans+=(LL)a[i]*count(lgr[i]+1,i,1)*count(rgr[i],rsgr[i]-1,0);
		}
		int ma,sma;
		for(int i=1;i<=n;i++){
			ma=0,sma=0;
			for(int j=i;j<=n&&j<i+6;j++){
				if(a[j]>ma){
					sma=ma;
					ma=a[j];
				}
				else if(a[j]>sma) sma=a[j];
				if((j-i+1)&1) ans-=ma;
				else ans-=sma;
				ans+=Find(i,j,ma,sma);
			}
		}
		cout<<ans<<"\n";
		return 0;
	}
}
int main(){
	cs::main();
	return 0;
}