xj这边模拟赛出了这题可还行。。。思路其实是简单的。
首先我们有$O(n^2m)$的暴力。
然后可持久化Trie支持在$\mathcal O(\log v)$的时间内查询$[l,r]$中某个数与给定数$x$的最大异或值。简单讲解
这样的时间复杂度是$\mathcal O(m\times n\log v)$的,但没什么优化空间了。
考虑分块。令每个块的大小为$B$.预处理$f(bl,br)$表示$[bl,br]$的答案(即两个端点都在$[bl,br]$这些块之间的最大异或值)。枚举bl,扫一遍其右侧的位置并用可持久化Trie查询,可以$\mathcal O(\frac{n}{B}\times n\times \log v)$的时间内预处理。
询问分两种情况:
- 若$l,r$在同一块中,暴力枚举右端点,用可持久化Trie查询即可。时间复杂度$\mathcal O(B\times \log v)$
- 不在同一块中。此时合法的区间分为三种:
-
- 右端点在$br$中。枚举右端点,用可持久化Trie查询即可。
-
- 左端点在$bl$中。我的方法是,再维护反串的可持久化Trie,再枚举左端点查询即可。
-
- 两个端点均在$[l1+1,br-1]$中。这部分答案即为$f(bl+1,br-1)$
故这部分的时间复杂度也是$\mathcal O(B\times \log v)$
- 两个端点均在$[l1+1,br-1]$中。这部分答案即为$f(bl+1,br-1)$
总时间复杂度$\mathcal O(\frac{n}{B}\times n\times \log v+m\times B\times \log v)$
假定$n,m$同价,取$B=\sqrt n$时最优,为$\mathcal O(n\sqrt n\log v)$
#define MAXN 20011
const ll B=150;
struct Lasting_Trie
{
ll t[MAXN*33][2],root[MAXN],last[MAXN*33],cnt=0;
ll a[MAXN];
void _insert(ll dex,ll k,ll pre,ll num)
{
if(k<0){last[num]=dex;return;}
bool c=(a[dex]>>k)&1;
if(pre)t[num][!c]=t[pre][!c];
t[num][c]=++cnt;
_insert(dex,k-1,t[pre][c],cnt);
last[num]=max(last[t[num][!c]],last[t[num][c]]);
}
void insert(ll dex,ll val)
{
a[dex]=val^a[dex-1];
root[dex]=++cnt;
_insert(dex,31,root[dex-1],root[dex]);
}
ll Query(ll lim,ll dex)
{
ll u=root[dex],res=0;
for(ll i=31;i>=0;--i)
{
bool c=(a[dex]>>i)&1;
if(t[u][!c]&&last[t[u][!c]]>=lim)res+=1ll<<i,u=t[u][!c];
else u=t[u][c];
}
return res;
}
}T,RT;
ll a[MAXN],bl[MAXN];
ll ff[151][151];
int main()
{
ll n=read(),m=read(),ans=0;
T.insert(0,0),RT.insert(0,0);
for(ll i=1;i<=n;++i)a[i]=read(),T.insert(i,a[i]),bl[i]=(i-1)/B+1;
for(ll i=n;i;--i)RT.insert(n-i+1,a[i]);
for(ll now=1;now<=bl[n];++now)
{
ll f=0,begin=(now-1)*B;
for(ll i=begin+1;i<n;++i)
{
umax(f,T.Query(begin,i));
if(i%B==0)ff[now][bl[i]]=f;
}
ff[now][bl[n]]=f;
}
while(m--)
{
ll l=(read()+ans)%n+1,r=(read()+ans)%n+1;
if(l>r)std::swap(l,r);
if(bl[l]==bl[r])
{
ans=0;
for(ll i=l;i<=r;++i)
umax(ans,T.Query(l-1,i));
}
else
{
ans=(bl[l]+1<bl[r]?ff[bl[l]+1][bl[r]-1]:0);
for(ll i=(bl[r]-1)*B+1;i<=r;++i)umax(ans,T.Query(l-1,i));
for(ll i=l;i<=bl[l]*B;++i)umax(ans,RT.Query(n-r,n-i+1));
}
printf("%lld\n",ans);
}
return 0;
}
两个端点均在 后面是bl吧
TQL
太巨了