模拟 Codeforces620F Xors on Segments

傳送門：點選打開連結

題意：n個數，m次查詢。n<=5e4,m<=1e3

每次查詢為一個區間l，r，要在n的數的[l,r]區間内選出2個數a,b(a<=b),然後計算a^(a+1)^(a+2)^...^b，輸出最大的這個值

思路：标準答案好像是莫隊算法＋trie

不過好多人複雜度都是O(n(n+m))的，，Tourist也是。。

隻要你敢寫就能過。大概就是i枚舉第一個數a，然後j枚舉第二個數b，mx記錄另一個數所在的數組範圍在[i,j]的對應的函數的最大值。

周遊所有的查詢，看i是否在某個查詢的區間範圍内，如果在，那麼就更新答案。

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;

const int MAX = 1e6 + 5;
const int MX = 5e4 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3ff3f3f;

int z[MAX], A[MX], B[MX];
int L[MX], R[MX], ans[MX];

int main() {
    int n, m; //FIN;
    z[0] = 0;
    for(int i = 1; i < MAX; i++) z[i] = z[i - 1] ^ i;
    while(~scanf("%d%d", &n, &m)) {
        memset(ans, 0, sizeof(ans));
        for(int i = 1; i <= n; i++) {
            scanf("%d", &A[i]);
        }
        for(int i = 1; i <= m; i++) {
            scanf("%d%d", &L[i], &R[i]);
        }
        for(int i = 1; i <= n; i++) {
            int mx = 0;
            for(int j = i; j <= n; j++) {
                if(A[i] <= A[j]) {
                    mx = max(mx, z[A[j]] ^ z[A[i] - 1]);
                }else mx = max(mx, z[A[j] - 1] ^ z[A[i]]);
                B[j] = mx;
            }
            for(int k = 1; k <= m; k++) {
                if(L[k] <= i && i <= R[k]) {
                    ans[k] = max(ans[k], B[R[k]]);
                }
            }
        }
        for(int i = 1; i <= m; i++) {
            printf("%d\n", ans[i]);
        }
    }
    return 0;
}