AC代码
#include<bits/stdc++.h>
using namespace std;
namespace OI{
#define I inline
typedef long long LL;
typedef long double LD;
typedef double D;
inline bool rd ( int &k ){
char c = getchar ();
bool neg = false;
while ( c != EOF && c != '-' && ( c < '0' || c > '9' ) )
c = getchar ();
if ( c == EOF ) return false;
if ( c == '-' ){
neg = true;
k = 0;
}else
k = c - '0';
c = getchar ();
while ( c >= '0' && c <= '9' ){
k = ( k << 1 ) + ( k << 3 ) + c - '0'; c = getchar ();
}
if ( neg ) k = -k;
return true;
}
inline bool lrd ( long long &k ){
char c = getchar ();
bool neg = false;
while ( c != EOF && c != '-' && ( c < '0' || c > '9' ) )
c = getchar ();
if ( c == EOF ) return false;
if ( c == '-' ){
neg = true;
k = 0;
}else
k = c - '0';
c = getchar ();
while ( c >= '0' && c <= '9' ){
k = ( k << 1 ) + ( k << 3 ) + c - '0'; c = getchar ();
}
if ( neg ) k = -k;
return true;
}
inline void freo (){
freopen ( "data.in", "r", stdin );
freopen ( "data.out", "w", stdout );
}
const int N = 12002;
const int S = 384099;
const int M = 115;
const int B = 30;
const int C = 2;
int dir [S][C], latest [S], root [N], versionNow, bound [M][2], lenPer, lenTot, chunkTot, vTot, belong [N];
LL pre [N], maxAmong [M][N];
I void insert ( LL val, int bit, int old, int young, int myVersion ){
if ( bit < 0 ){
latest [young] = myVersion;
return;
}
int num = ( val >> bit ) & 1;
if ( old ){ dir [young][num^1] = dir [old][num^1]; }
dir [young][num] = ++vTot;
insert ( val, bit-1, dir [old][num], dir [young][num], myVersion );
latest [young] = max ( latest [ dir [young][0] ], latest [ dir [young][1] ] );
}
I LL ask ( LL val, int bit, int now, int limit ){
if ( bit < 0 ){ return val ^ pre [ latest [now] ]; }
int num = ( val >> bit ) & 1;
if ( latest [ dir [now][num^1] ] >= limit ){ return ask ( val, bit-1, dir [now][num^1], limit ); }
else return ask ( val, bit-1, dir [now][num], limit );
}
I void chunk (){
lenPer = sqrt ( lenTot );
chunkTot = ( lenTot % lenPer ? lenTot/lenPer+1 : lenTot/lenPer );
// printf ( "chunkTot is %d\n", chunkTot );
for ( int i = 1; i <= chunkTot; ++i ){ bound [i][0] = (i-1)*lenPer+1; bound [i][1] = min ( lenTot, i*lenPer ); }
for ( int i = 1; i <= chunkTot; ++i ){
for ( int j = bound [i][0]; j <= bound [i][1]; ++j ){ belong [j] = i; }
}
}
void Main (){
// freo ();
rd ( lenTot ); int many; rd ( many );
chunk ();
latest [0] = -1;
root [0] = ++vTot;
insert ( 0, B, 0, root [0], 0 );
for ( int i = 1; i <= lenTot; ++i ){
lrd ( pre [i] ); pre [i] ^= pre [i-1];
root [i] = ++vTot;
versionNow ++;
insert ( pre [i], B, root [i-1], root [i], versionNow );
}
for ( int i = 1; i < chunkTot; ++i ){
for ( int j = i; j <= lenTot; ++j ){
maxAmong [i][j] = max ( maxAmong [i][j-1], ask ( pre [j], B, root [j], bound [i][0] - 1 ) );
// printf ( "maxAmong [%d][%d] is %lld\n", i, j, maxAmong [i][j] );
}
}
LL uper = 0;
for ( int i = 1; i <= many; ++i ){
LL fakeL, fakeR; lrd ( fakeL ); lrd ( fakeR );
int l = min ( ( ( fakeL + uper ) % lenTot )+1, ( ( (LL)fakeR + uper ) % lenTot )+1 );
int r = max ( ( ( fakeL + uper ) % lenTot )+1, ( ( (LL)fakeR + uper ) % lenTot )+1 );
// int l, r;
// rd ( l ); rd ( r );
// printf ( "%d %d\n", l, r );
int lB = belong [l-1], rB = belong [r];
if ( rB - lB <= 1 ){
uper = -0x7fffffff;
for ( int i = l-1; i <= r-1; ++i ){
uper = max ( uper, ask ( pre [i], B, root [r], l-1 ) );
}
printf ( "%lld\n", uper );
}else{
uper = maxAmong [lB+1][r];
// printf ( "start with %lld\n", uper );
for ( int j = l-1; j <= bound [lB][1]; ++j ){
uper = max ( uper, ask ( pre [j], B, root [r], j+1 ) );
}
// printf ( "compare with %lld\n", ask ( pre [r], B, root [r-1], l ) );
// uper = max ( uper, ask ( pre [r], B, root [r-1], l-1 ) );
printf ( "%lld\n", uper );
}
}
}
}
int main (){
OI :: Main ();
return 0;
}
巨水数据生成器代码
#include<bits/stdc++.h>
using namespace std;
const int N = 10;
const int M = 4;
const int Z = 4;
typedef long long LL;
inline int rol ( int n ){
return (LL)rand()*rand()%n;
}
int main (){
srand ( (unsigned)time(0) );
freopen ( "data.in", "w", stdout );
int n = N; printf ( "%d %d\n", n, n );
for ( int i = 1; i <= n; ++i ) printf ( "%d ", rol (Z)+1 );
puts ("");
for ( int i = 1; i <= n; ++i ){
int l = rol (N)+1, r = rol (N)+1;
if ( l > r ) swap ( l, r );
printf ( "%d %d\n", l, r );
}
return 0;
}
细节提醒
转化为两个前缀和的单点异或后要注意范围,用[l-1,r-1]
和[l,r]
中的各一个数统计答案;算所在块也要注意。
真正明白可持久化Trie的查询函数到底实现了什么功能。