Codeforces 620F Xors on Segments DP

題意

• n個數，m次查詢。n<=5e4,m<=1e3
• 每次查詢為一個區間l，r，要在n的數的[l,r]區間内選出2個數a,b(a<=b)
• 計算f(a, b) = a^(a+1)^(a+2)^…^b，輸出最大的這個值

思路

• 我想了好久，想到用莫隊+Trie樹了。。可是還是沒想出來。。标程好像也是這樣。。不過我沒細看。。之後我會再嘗試用這個方法解決~
• 我參考了大神的部落格，看到居然O(n^2)也能過。。。然後就寫了一發過了。。
• 基本想法就是，離線算法，計算每個(i,j)的最大值，然後如果查詢問道，就更新這個查詢的ans
• 但是呢，如果樸素的計算每個(i,j)，複雜度要O(n^3)是不行的。
• 我們注意到，實際我們需要計算的隻有對任意a[i]和a[j]（設min(a[i], a[j]) = x, max(a[i], a[j]) = y），f(x, y)，這個單獨計算每一組預處理之後是O(1)的，是以呢我們隻需要枚舉i, j即可算出所有這樣的f(x, y)，複雜度是O(n ^ 2)
• 然後，由于我們存不下這麼多對的解，是以要考慮如何更新ans了，這裡有點dp的想法
• dp(i,j)表示，在[i, j]區間内，必須用到i的最大值，dp(i, j) = max(dp(i,j-1), f(a[i], a[j]) )
• 這個dp可以滾動數組，壓掉i這一維
• 對于第j組的查詢，L[j], R[j], ans[j] = max(dp(i, R[j]) ) 其中L[j] <= i <= R[j]

實作

#include <bits/stdc++.h>
using namespace std;
const int maxn =  + ;
const int maxm =  + ;
const int Max = +;
int L[maxm], R[maxm];
int a[maxn], b[maxn];
int Xor[Max];
int ans[maxm];

int main(){
    int n,m;
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for (int i=;i<n;i++){
        cin>>a[i];
    }
    for (int i=;i<m;i++){
        cin>>L[i]>>R[i];
        L[i]--, R[i]--;
    }
    for (int i=;i<Max;i++){
        Xor[i] = Xor[i-] ^ i;
    }
    for (int i=;i<n;i++){
        int maxx = ;
        for (int j=i;j<n;j++){
            if (a[i] >= a[j]){
                maxx = max(maxx, Xor[a[i]] ^ Xor[a[j]-]);
            }
            else{
                maxx = max(maxx, Xor[a[i]-] ^ Xor[a[j]]);
            }
            b[j] = maxx;
        }
        for (int j=;j<m;j++){
            if (L[j] <= i && R[j] >= i){
                ans[j] = max(ans[j], b[R[j]]);
            }
        }

    }
    for (int j=;j<m;j++){
        cout << ans[j] << endl;
    }
    return ;
}