题解：P10690 Fotile 模拟赛 L

· · 题解

不懂为啥都可持久化 Trie，甚至有的人还用区间 dp 过了。

这里讲一种比区间 dp 更好写，且跑的更快的做法，时间复杂度也为 O(n^2)。

代码压一压 596B。

Solution

先求前缀异或和是自然的。

考虑对于每个 i 预处理出 f_{i, j}(j < i) 表示 pre_i \oplus pre_k(j \le k < i) 的最大值。这个直接扫一遍就做完了。时间复杂度 O(n^2)，当然还有个 \frac{1}{2} 的常数。空间复杂度也是这个，开一维数组就不会爆。

然后查询的时候就是 \max_{l \le i \le r}\{f_{i, l-1}\}。时间复杂度 O(nq)。

比区间 dp 快了 300ms。

:::success[AC Code]

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(Tx, Ty) make_pair(Tx, Ty)
#define For(Ti, Ta, Tb) for(auto Ti = (Ta); Ti <= (Tb); Ti++)
#define Dec(Ti, Ta, Tb) for(auto Ti = (Ta); Ti >= (Tb); Ti--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
const int N = 12005;
int f[N * N / 2];
int n, m, a[N];
int pre[N];
int get(int x, int y) {
    if (x == y) return 0;
    return x * (x - 1) / 2 + y + 1;
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    For(i ,1, n) cin >> a[i];
    For(i, 1,n) pre[i] = pre[i - 1] ^ a[i];
    For(i ,1, n) Dec(j, i - 1, 0) f[get(i, j)] = max(f[get(i, j + 1)], pre[i] ^ pre[j]);
    int lastans = 0;
    while (m--) {
        int x, y;
        cin >> x >> y;
        x = (1ll * x + lastans) % n + 1;
        y = (1ll * y + lastans) % n + 1;
        if (x > y) swap(x, y);
        lastans = 0;
        For(i, x, y) lastans = max(lastans, f[get(i, x - 1)]);
        cout << lastans << '\n';
    }
    return 0; 
}

:::

这里再给个压行的。

:::success[AC Code]

#include <iostream>
using namespace std;
#define For(Ti,Ta,Tb) for(auto Ti=(Ta);Ti<=(Tb);Ti++)
#define Dec(Ti,Ta,Tb) for(auto Ti=(Ta);Ti>=(Tb);Ti--)
const int N=12005;
int n,m,a[N],f[N*N/2],pre[N],x,y,lastans;
int get(int x,int y){return x*(x-1)/2+y+1;}
int main(){
    cin>>n>>m;
    For(i,1,n)cin>>a[i];
    For(i,1,n)pre[i]=pre[i-1]^a[i];
    For(i,1,n)Dec(j,i-1,0)f[get(i,j)]=max(f[get(i,j+1)],pre[i]^pre[j]);
    while(m--){
        cin>>x>>y;
        x=(1ll*x+lastans)%n+1,y=(1ll*y+lastans)%n+1;
        if(x>y)swap(x,y);
        lastans=0;
        For(i,x,y)lastans=max(lastans,f[get(i,x-1)]);
        cout<<lastans<<'\n';
    }
    return 0; 
}

:::