首页 > 代码库 > BZOJ2741 【FOTILE模拟赛】L

BZOJ2741 【FOTILE模拟赛】L

2024-08-09 03:26:09   216人阅读

一个上午两道题，妥妥的作死。。。

首先还是按照之前思路建立可持久化trie，然后发现了点问题。。。

trie只能支持对于给定v求出最大xor值，也就是说我们要枚举a[i] (i ∈ [l, r])，于是单次询问复杂度O(n * 30)，爆表

于是想到了需要预处理，方法是分块，预处理复杂度O(n * (n / sz) * 30)，单次询问复杂度O(sz * 30)（sz为块的大小）

到这里的时候。。。网上的题解君们就只剩下程序了。。。于是害得蒟蒻理解错惹%>_<%

于是看到了BLADEVIL的题解，简直一目了然（但是程序注释不删不敢恭维= =）

重点要注意的就两个地方：

（1）f[i][j]为从第i个块的第一个元素开始，到第j个数的区间中，任意找两个数的xor值最大

（2）在计算l和r的时候。。。会爆int

 

技术分享
  1 /**************************************************************  2     Problem: 2741  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:5768 ms  7     Memory:11508 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <cmath> 12 #include <algorithm> 13   14 using namespace std; 15 typedef long long ll; 16 const int N = 12005; 17 const int sqrt_N = 120; 18   19 struct trie_node { 20     int son[2], cnt; 21 } t[N * 35]; 22 int cnt_trie = 1; 23   24 int n, m, a[N]; 25 int root[N], sz, w[N]; 26 int f[sqrt_N][N]; 27   28 inline int read() { 29     int x = 0; 30     char ch = getchar(); 31     while (ch < ‘0‘ || ‘9‘ < ch) 32         ch = getchar(); 33     while (‘0‘ <= ch && ch <= ‘9‘) { 34         x = x * 10 + ch - ‘0‘; 35         ch = getchar(); 36     } 37     return x; 38 } 39   40 int A[35]; 41 void insert(int &root, int v) { 42     int R = root, now = ++cnt_trie, i; 43     root = now; 44     for (i = 0; i <= 30; ++i) 45         A[i] = v & 1, v >>= 1; 46     reverse(A, A + 31); 47     for (i = 0; i <= 30; ++i) { 48         t[now].son[0] = t[R].son[0], t[now].son[1] = t[R].son[1]; 49         R = t[R].son[A[i]], now = t[now].son[A[i]] = ++cnt_trie; 50         t[now].cnt = t[R].cnt + 1; 51     } 52 } 53   54 int query(int x, int y, int v) { 55     int i, res = 0; 56     for (i = 0; i <= 30; ++i) 57         A[i] = v & 1, v >>= 1; 58     reverse(A, A + 31); 59     for (i = 0; i <= 30; ++i) { 60         if (t[t[y].son[!A[i]]].cnt - t[t[x].son[!A[i]]].cnt) 61             x = t[x].son[!A[i]], y = t[y].son[!A[i]], res += (1 << 30 - i); 62         else x = t[x].son[A[i]], y = t[y].son[A[i]]; 63     } 64     return res; 65 } 66   67 int Query(int l, int r) { 68     int i, maxi, res = w[l] < w[r] ? f[w[l] + 1][r] : 0; 69     for (i = min(w[l] * sz, r); i >= l; --i) 70         res = max(res, query(root[l - 1], root[r], a[i])); 71     return res; 72 } 73   74 void Block() { 75     int i, j, l; 76     sz = (int) sqrt(n); 77     for (i = 1; i <= n; ++i) { 78         w[i] = (int) (i - 1) / sz + 1; 79         for (j = 1; j <= w[i]; ++j) { 80             l = (j - 1) * sz; 81             f[j][i] = max(f[j][i - 1], query(root[l], root[i], a[i])); 82         } 83     } 84 } 85   86 int main() { 87     int i, x, y, l, r, last_ans = 0; 88     n = read(), m = read(); 89     for (i = 1, a[0] = root[0] = 0; i <= n; ++i) { 90         a[i] = a[i - 1] ^ read(), root[i] = root[i - 1]; 91         insert(root[i], a[i]); 92     } 93     Block(); 94     while (m--) { 95         x = read(), y = read(); 96         l = min(((ll) x + last_ans) % n + 1, ((ll) y + last_ans) % n + 1); 97         r = max(((ll) x + last_ans) % n + 1, ((ll) y + last_ans) % n + 1); 98         printf("%d\n", last_ans = Query(l - 1, r)); 99     }100     return 0;101 }
View Code

 

BZOJ2741 【FOTILE模拟赛】L


联系
我们