• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

NKOJ8493 最大连续异或和

开发技术 开发技术 9小时前 2次浏览

Problem

给定一个长度为(N)的非负整数数列
有个(M)询问,询问格式为(L,R),表示询问区间([L,R])内的最大的连续异或和。
即求出(max( A_i xor A_{i+1} xor A_{i+2} xor … xor A_j )) 其中((L leq i leq j leq R))

强制在线

(1 leq N leq 12000,1 leq M leq 6000,1 leq A_i leq 2^{31}-1)

Solution

分析题目性质,因为异或((xor))操作有自反性,所以可以用前缀异或和来维护一段连续异或和,即([l,r])异或和(=sum[r] xor sum[l-1])

那么此题就被转换成了求区间([L,R])的最大的(sum[j] xor sum[i-1] (L leq i leq j leq R))

显然这个问题可以用(dp)来做

(f[i][j]:)区间([i,j])内任意两数异或之和最大
(f[i][j]=max(f[i][j-1],sum[l])^(sum[j]) (i leq l < j))

时间复杂度(O(n^3)),爆炸,考虑优化

发现(sum[l])^(sum[j])相当于是从([i,j))中找一个数异或上(sum[j])最大,考虑可持久化(01trie)计算,时间复杂度被优化到了(O(n^2logn)),可依然要炸。

那么直接考虑可持久化(01trie),暴力枚举(i),在(trie)上找异或(sum[i])最大的(sum[j]),单次询问时间复杂度(O(nlogn)),有(M)次询问,也要炸。

注意到(1 leq N leq 12000),考虑将(N)个前缀异或和分块,对每一块进行预处理(f)数组,然后询问时暴力查询不是块的部分,是完整块的直接用事先预处理好的即可。

详细的说呢,就是
(f[i][j]:)从第(i)块开头到第(j)块结尾这一段里任意两个数异或最大值
(f[i][j]=max(f[i][j-1],sum[l])^(sum[k]))
(l)枚举(j)块内元素,(k)枚举的是(i)(j-1)块的元素。
发现这里同样可以跟上面一样用可持久化(01trie)优化,于是时间复杂度变成了(O((sqrt n)^3logn) = O(nsqrt nlogn))

对于每次询问时间复杂度(O(2sqrt nlogn))
预处理空间复杂度(O(n))(trie)(O(nlogn))

(code:)

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 15000 + 5;
const int MAX_S = 200 + 5;
typedef long long ll;
int n,m,s,tot,sum[MAX_N];
ll f[MAX_S][MAX_S],lastans,a[MAX_N];
inline int calc(int x){return (x-1)/s+1;}
int root[MAX_N];
struct PTrie{
	int num;
	int nxt[2];
}Ptrie[MAX_N * 32];
void Pins(ll x,int id){
	root[id]=++tot;
	int p=root[id],q=root[id-1];
	for(int i=30;i>=0;i--){
		int c=(x>>i)&1;
		for(int j=0;j<2;j++)
			Ptrie[p].nxt[j]=Ptrie[q].nxt[j];
		Ptrie[p].num=Ptrie[q].num+1;
		Ptrie[p].nxt[c]=++tot;
		p=Ptrie[p].nxt[c];
		q=Ptrie[q].nxt[c];
	}
	Ptrie[p].num=Ptrie[q].num;
	Ptrie[p].num++;
}
ll Pask(ll x,int a,int b){
	int q=root[a-1],p=root[b];
	ll ans=0;
	for(int i=30;i>=0;i--){
		int c=(x>>i)&1;
		int ps=Ptrie[p].nxt[c^1],qs=Ptrie[q].nxt[c^1];
		if(Ptrie[ps].num-Ptrie[qs].num>=1){
			ans|=(1ll<<i);
			p=ps;
			q=qs;
		}
		else{
			p=Ptrie[p].nxt[c];
			q=Ptrie[q].nxt[c];
		}
	}
	return ans;
}
ll query(int l,int r){
    int kl=calc(l),kr=calc(r);
    ll ans=0;
    if(kl==kr){
        for(int i=l;i<=r;i++){
            ans=max(ans,Pask(sum[i],l,i));
        }
    }
    else{
        ans=0;
        if(kl+1<=kr-1) ans=f[kl+1][kr-1];
        for(int i=l;i<=kl*s;i++)
            ans=max(ans,Pask(sum[i],l,r));
        for(int i=(kr-1)*s+1;i<=r;i++)
            ans=max(ans,Pask(sum[i],l,r));
    }
    return ans;
}
int main(){
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
    scanf("%d%d",&n,&m);
    s=sqrt(n);
    Pins(sum[0],0);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        sum[i]=sum[i-1]^a[i];
        Pins(sum[i],i);
    }
    for(int i=1;i<=calc(n);i++){
        for(int j=i;j<=calc(n);j++){
        	ll maxn=0;
            for(int l=(j-1)*s+1;l<=j*s;l++)
                maxn=max(maxn,Pask(sum[l],(i-1)*s+1,l));
        	f[i][j]=max(f[i][j-1],maxn);
		}
    }
    while(m--){
        ll x,y;
        scanf("%lld%lld",&x,&y);
        ll l=(x+lastans)%n+1;
        ll r=(y+lastans)%n+1;
        if(l>r) swap(l,r);
        lastans=query(l-1,r);
        printf("%lldn",lastans);
    }
    return 0;
}

程序员灯塔
转载请注明原文链接:NKOJ8493 最大连续异或和
喜欢 (0)