【bzoj2741】[FOTILE模拟赛] L

时间：2023-03-09 19:48:16
【bzoj2741】[FOTILE模拟赛] L

Portal --> bzoj2741

Solution

　　突然沉迷分块不能自拔

　　考虑用分块+可持久化trie来解决这个问题

　　对于每一块的块头\(L\)，预处理\([L,i]\)区间内的所有子区间的最大异或和，这个可以做到\(O(n\sqrt nlogn)\)，实现上的话就是。。将一段区间\([l,r]\)的异或和写成\(sum[r]\ xor \ sum[l-1]\)的形式，然后对于每一个

\(i\)应该是\([L,i-1]\)的答案和所有以\(i\)结尾的子区间的异或和的最大值，右端点固定的话直接在可持久化trie里面查一下就好了（弱智如我一开始在这个地方莫名卡壳==）

　　然后查询的时候，如果说\(l,r\)在同一块里面，直接暴力查

　　如果不在同一块里面，把\(l\)所在的块单独处理一下，然后再用答案和下一块的块头\(x\)预处理出来的\([x,r]\)的答案取一下max即可

　　long long 警告qwq，所以trie的层数要开大一点。。

　　

　　mark：可持久化trie在insert的时候记得newnode要放在d<0的判断之前。。

　　

　　代码大概长这个样子

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#define ll long long

using namespace std;

const int N=12010,M=6010,B=109+10;

ll a[N],sum[N];

int n,m,num,sq;

ll lastans;

namespace Trie{/*{{{*/

	const int N=::N*40,TOP=33;//just for debuging!!!

	int ch[N][2],rt[N],sz[N];

	int tot;

	void init(){tot=0; sz[0]=0; rt[0]=0; ch[0][0]=ch[0][1]=0;}

	int newnode(int pre){

		ch[++tot][0]=ch[pre][0]; ch[tot][1]=ch[pre][1]; sz[tot]=sz[pre];

		return tot;

	}

	void _insert(int pre,int &x,ll delta,int d){

		x=newnode(pre);

		++sz[x];

		if (d<0) return;

		int dir=delta>>d&1;

		_insert(ch[pre][dir],ch[x][dir],delta,d-1);

	}

	void insert(int pre,int x,ll delta){++pre; ++x;_insert(rt[pre],rt[x],delta,TOP);}

	ll _query(int L,int R,ll delta,int d){

		if (d<0) return 0;

		int dir=delta>>d&1;

		if (sz[ch[R][dir^1]]-sz[ch[L][dir^1]])

			return (1LL<<d)+_query(ch[L][dir^1],ch[R][dir^1],delta,d-1);

		return _query(ch[L][dir],ch[R][dir],delta,d-1);

	}

	ll query(int L,int R,ll delta){++L;++R; return L>R?0:_query(L?rt[L-1]:0,rt[R],delta,TOP);}

}/*}}}*/

ll rec[B][N];

int Id(int x){return (x-1)/sq+1;}

int St(int x){return (x-1)*sq+1;}

int Ed(int x){return x*sq;}

void prework(){

	Trie::init();

	for (int i=0;i<=n;++i)

		Trie::insert(i-1,i,sum[i]);

	int x;

	num=Id(n);

	for (int i=1;i<=num;++i){

		x=St(i);

		rec[i][x]=a[x];

		for (int j=x+1;j<=n;++j)

			rec[i][j]=max(rec[i][j-1],Trie::query(x-1,j-1,sum[j]));

	}

}

ll query(int l,int r){

	ll ret=0;

	int numl=Id(l),numr=Id(r);

	if (numl==numr){

		for (int i=l;i<=r;++i)

			ret=max(ret,Trie::query(i,r,sum[i-1]));

		return ret;

	}

	if (l==St(numl))

		ret=max(ret,rec[numl][r]);

	else

		for (int i=l;i<=Ed(numl);++i)

			ret=max(ret,Trie::query(i,r,sum[i-1]));

	ret=max(ret,rec[numl+1][r]);

	return ret;

}

int main(){

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

#endif

	int l,r,x,y;

	scanf("%d%d",&n,&m);

	sum[0]=0; sq=sqrt(n);

	for (int i=1;i<=n;++i)

		scanf("%lld",a+i),sum[i]=sum[i-1]^a[i];

	prework();

	lastans=0;

	for (int i=1;i<=m;++i){

		scanf("%d%d",&x,&y);

		l=min((1LL*x+lastans)%n+1,(1LL*y+lastans)%n+1);

		r=max((1LL*x+lastans)%n+1,(1LL*y+lastans)%n+1);

		lastans=query(l,r);

		printf("%lld\n",lastans);

	}

}

相关文章