手机 网站 源码,设计工作室与网站建设工作室,联想网络营销推广方法,常州百度推广优化题目链接 首先记\(sum\)为前缀异或和#xff0c;那么区间\(s[l,r]sum[l-1]^{\wedge}sum[r]\)。即一个区间异或和可以转为求两个数的异或和。 那么对\([l,r]\)的询问即求\([l-1,r]\)中某两个数异或的最大值。 区间中某一个数和已知的一个数异或的最大值可以用可持久化Trie \(O(…题目链接 首先记\(sum\)为前缀异或和那么区间\(s[l,r]sum[l-1]^{\wedge}sum[r]\)。即一个区间异或和可以转为求两个数的异或和。 那么对\([l,r]\)的询问即求\([l-1,r]\)中某两个数异或的最大值。 区间中某一个数和已知的一个数异或的最大值可以用可持久化Trie \(O(\log v)\)求出。所以尽量确定一个数再在区间中求最大值。 而且数据范围提醒我们可以分块。 用\(head[i]\)表示第\(i\)块的开头位置\(Max(l,r,x)\)表示\(x\)与\([l,r]\)中某一个数异或的最大值\(f[i][j]\)表示从第\(i\)块的开始到位置\(j\)某两个数异或的最大值是多少。 那么 \(f[i][j] \max(f[i-1][j-1], Max(head[i], j-1, A[j]))\)。可以在\(O(n\sqrt n\log v)\)时间内预处理。\(A[]\)是前缀异或和 查询的时候设\(x\)表示\(l\)后面的第一块若\(l,r\)在同一块里则 \(ans Max(l, r, A[i]), i\in[l,r]\)。对啊 和自己异或也没什么意义 否则 \(ans \max(f[x][r], Max(l, r, A[i]))\)\(i\in[l,begin[x]-1]\)。 对\([1,r]\)的询问可能会有同上一题一样的边界问题可以异或0把\(A[0]0\)也试一遍就行了。。 询问复杂度同样\(O(q\sqrt n\log v)\)。 //11020kb 8232ms
#include cmath
#include cstdio
#include cctype
#include algorithm
#define gc() getchar()
#define MAXIN 500000//为什么50000WATLE啊 QAQ
//#define gc() (SSTT(TT(SSIN)fread(IN,1,MAXIN,stdin),SSTT)?EOF:*SS)
#define BIT 30
typedef long long LL;
const int N12005,M111;int root[N],A[N],bel[N],H[N],f[M][N];
char IN[MAXIN],*SSIN,*TTIN;
struct Trie
{#define S N*32int tot,son[S][2],sz[S];void Insert(int x,int y,int v){for(int iBIT; ~i; --i){int cvi1;son[x][c]tot, son[x][c^1]son[y][c^1];xtot, yson[y][c];sz[x]sz[y]1;}}int Query(int x,int y,int v){int res0;for(int iBIT; ~i; --i){int c(vi1)^1;if(sz[son[y][c]]-sz[son[x][c]]0)xson[x][c], yson[y][c], res|1i;elsec^1, xson[x][c], yson[y][c];}return res;}
}T;inline int read()
{int now0;register char cgc();for(;!isdigit(c);cgc());for(;isdigit(c);nownow*10c-0,cgc());return now;
}int main()
{int nread(),Qread(),sizesqrt(n);for(int i1; in; i)bel[i](i-1)/size1, T.Insert(root[i]T.tot,root[i-1],A[i]A[i-1]^read());//^不是 H[1]1;for(int i2,limbel[n]; ilim; i) H[i]H[i-1]size;for(int i1,limbel[n]; ilim; i)for(int jH[i]1,rtlroot[H[i]-1]; jn; j)f[i][j]std::max(f[i][j-1],T.Query(rtl,root[j-1],A[j]));for(int l,r,x,y,ans0; Q--; ){x((LL)read()ans)%n1, y((LL)read()ans)%n1;//read()%nans%n 都可能爆int。。and LL要在括号里面。。lstd::min(x,y), rstd::max(x,y);--l, ans0;if(bel[l]bel[r])for(int il,rtlroot[std::max(0,l-1)],rtrroot[r]; ir; i)ansstd::max(ans,T.Query(rtl,rtr,A[i]));else{ansf[bel[l]1][r];for(int il,limH[bel[l]1]-1,rtlroot[std::max(0,l-1)],rtrroot[r]; ilim; i)ansstd::max(ans,T.Query(rtl,rtr,A[i]));}printf(%d\n,ans);}return 0;
} 转载于:https://www.cnblogs.com/SovietPower/p/9719943.html
