#WD231105A. 自福串(string)--自编题题解

网址

题目详情 - 字胡串(string) - Super

题解 - 字胡串(string) - Super

数据

骗分代码

考虑找到每个区间最大值的位置，设区间表示该最大值的位置向左向右找到的首个大于最大值的位置，设区间表示该最大值的位置向左向右找到的第一个能使异或和变大的位置，对答案的贡献是：

​

可以用倍增+线段树来维护求出区间或和与区间最大值，然后再求和区间的贡献即可。

时间复杂度：

​ 最优, 当最大值总是在区间中心时取得；

​ 最劣, 当输入的自福串从小到大或从大到小排序后取得。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#define _for(i,n) for(int i=1;i<=n;i++)
#define N 1012345
#define int long long
using namespace std;
inline int input(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
} 
int n,a[N],ans;

#define ls p<<1
#define rs p<<1|1
struct TR{
	int max,huo,pos;
}tr[N<<2|3];

void pushup(int p){
	tr[p].max=max(tr[ls].max,tr[rs].max);
	tr[p].huo=tr[ls].huo|tr[rs].huo;
	tr[p].pos=tr[ls].max==tr[p].max?tr[ls].pos:tr[rs].pos;
}

void build(int p,int l,int r){
	if(l==r){
		tr[p].max=tr[p].huo=a[l];
		tr[p].pos=l;
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(p);
}

struct B{
	int x,id;
	bool operator<(const B y)const{return x<y.x;}
}b[N];
inline B ask_max(int p,int l,int r,int L,int R){
	if(L<=l&&r<=R) return {tr[p].max,tr[p].pos};
	B res={0,0};
	int mid=(l+r)>>1;
	if(L<=mid){
		B s=ask_max(ls,l,mid,L,R);
		if(s.x>res.x) res=s;
	}	
	if(R>mid){
		B s=ask_max(rs,mid+1,r,L,R);
		if(s.x>res.x) res=s;
	}
	return res;
}

inline int ask_huo(int p,int l,int r,int L,int R){
	if(L<=l&&r<=R) return tr[p].huo;
	int mid=(l+r)>>1;
	int res=0;
	if(L<=mid) res=(res|ask_huo(ls,l,mid,L,R));
	if(R>mid) res=(res|ask_huo(rs,mid+1,r,L,R));
	return res;
}

void search(int L,int R){
	if(L>=R) return;
	//找到区间最大值位置 
	B maxnum=ask_max(1,1,n,L,R);
	int l=maxnum.id,r=maxnum.id;
	int pos=maxnum.id;
//	printf("maxnum=a[%d]=%d\n",pos,maxnum.x);
//	printf("%d %d %d\n",L,R,pos);
	//寻找左侧首个满足 g(T)>f(T) 的位置
	for(int i=24;i>=0;i--){
		if(l-(1<<i)<L) continue;
		if(ask_huo(1,1,n,l-(1<<i),pos)>maxnum.x) continue;
		else l=l-(1<<i);
	}
	//寻找右侧首个满足 g(T)>f(T) 的位置
	for(int i=24;i>=0;i--){
		if(r+(1<<i)>R) continue;
		if(ask_huo(1,1,n,pos,r+(1<<i))>maxnum.x) continue;
		else r=r+(1<<i);
	}
	ans+=(l-L)*(R-pos+1)+(R-r)*(pos-L+1)-(R-r)*(l-L);
	search(L,pos-1);search(pos+1,R);
}

void solve(){
	_for(i,n) b[i]={a[i],i};
	sort(b+1,b+n+1);
	search(1,n);
}

signed main(){
	freopen("string.in", "r", stdin);
	freopen("string.out", "w", stdout);
	n=input();
	_for(i,n) a[i]=input();
	build(1,1,n);
	solve();
	printf("%lld",ans);
	return 0;
}

正解代码

对于, 直接枚举区间,判断是否合法即可。

对于, 考虑一个区间, 只要这个区间的任意值非最大值有一位不与最大值相同, 那么这个区间就是 合法区间。

找出所有值左右第一个大于它的位置, 那么以它为最大值的区间就固定在这一段中。只要再 找出这个区间中左右第一个有一位不与最大值相同的值的位置, 那么这个位置左边的所有位置都 可以与最大值右边的位置构成一个合法区间。右边也同理。 可以用单调栈找出左右第一个大于它的位置, 再用的时间处理出左右第一个某一位为当前数超集的地方（备注：就是找到首个使当前数异或能变大的数的位置，用与表示的上一个与下一个转化为二进制后第位为的位置，可预处理）, 然后就可以统计答案了, 注意处理值相同的情况。

时间复杂度。

#include <bits/stdc++.h>
using namespace std;
inline int read(){
    char ch=getchar();int i=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){i=(i<<1)+(i<<3)+ch-'0';ch=getchar();}
    return i*f;
}
const int N=1e6+50;
int n,a[N],l[N],r[N],st[N],pos[N],top,diff_l[N],diff_r[N],mx[35];
int mxpos[35];

int main(){
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
    n=read(); 
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++){
        while(top&&st[top]<=a[i])top--;
        l[i]=pos[top]+1;
        st[++top]=a[i];pos[top]=i;
    }
    top=0; pos[top]=n+1;
    for(int i=n;i>=1;i--){
        while(top&&st[top]<a[i]) top--;
        r[i]=pos[top]-1;
        st[++top]=a[i];pos[top]=i;
    }
    for(int i=1;i<=n;i++){
        int p=0;
        for(int j=0;(1ll<<j)<=a[i];j++){
            if((1ll<<j)&a[i])mx[j]=max(mx[j],i);
            else p=max(p,mx[j]);
        }
        diff_l[i]=p;
    }
    fill(mx,mx+32+1,n+1);
    for(int i=n;i>=1;i--) {
        int p=n+1;
        for(int j=0;(1ll<<j)<=a[i];j++) {
            if((1ll<<j)&a[i]) mx[j]=min(mx[j],i);
            else p=min(p,mx[j]);
        }
        diff_r[i]=p;
    }
    long long ans=0;
    for(int i=1;i<=n;i++) {
        if(diff_l[i]>=l[i])
            ans+=1ll*(diff_l[i]-l[i]+1)*(r[i]-i+1);
        if(diff_r[i]<=r[i])
            ans+=1ll*(r[i]-diff_r[i]+1)*(i-l[i]+1);
        if(diff_l[i]>=l[i]&&diff_r[i]<=r[i])
            ans-=1ll*(r[i]-diff_r[i]+1)*(diff_l[i]-l[i]+1);
    }
    cout<<ans<<endl;
}