【BZOJ2741】【块状链表+可持久化trie】FOTILE模拟赛L

Description

FOTILE得到了一个长为N的序列A，为了拯救地球，他希望知道某些区间内的最大的连续XOR和。

即对于一个询问，你需要求出max(Ai xor Ai+1 xor Ai+2 ... xor Aj)，其中l<=i<=j<=r。

为了体现在线操作，对于一个询问(x,y)：

l = min ( ((x+lastans) mod N)+1 , ((y+lastans) mod N)+1 ).
r = max ( ((x+lastans) mod N)+1 , ((y+lastans) mod N)+1 ).

其中lastans是上次询问的答案，一开始为0。

Input

第一行两个整数N和M。

第二行有N个正整数，其中第i个数为Ai，有多余空格。

后M行每行两个数x,y表示一对询问。

Output

共M行，第i行一个正整数表示第i个询问的结果。

Sample Input

3 3
1 4 3
0 1
0 1
4 3

Sample Output

5
7
7

HINT

N=12000，M=6000，x,y,Ai在signed longint范围内。

Source

By seter

【分析】

第一次写可持久化trie，还有点问题。

题解网上都是...先不说了

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <vector>

 #include <utility>

 #include <iomanip>

 #include <string>

 #include <cmath>

 #include <queue>

 #include <assert.h>

 #include <map>

 const int N =  + ;

 const int SIZE = ;//块状链表的根号50000

 const int M =  + ;

 using namespace std;

 typedef long long ll;

 struct Node{

        int val;//代表数量

        int num;//代表值

        Node *ch[];

 }mem[N *  * ], *root[N];

 int n, m;//n为数量,m为操作次数

 struct BLOCK_LIST{//块状链表

        int data[SIZE];

        int size, next;

        void init(){

             size = ;

             memset(data, , sizeof(data));

             next = -;

        }

 }list[SIZE];

 int tot = ;//记录mem使用空间

 int Max[SIZE + ][SIZE + ], Pos;//表示从i到j块的最大异或值

 int data[N];

 Node *NEW(){//创建新trie节点

      Node *p = &mem[tot++];

      p->val = p->num = ;

      p->ch[] = p->ch[] = NULL;

      return p;

 }

 void insert(Node *&p, Node *&last, int x){//k为根

      p = NEW();

      Node *u = p, *a = last;

      for (int i = ; i >=  ; i--){

          int t = ((( << i) & x) ==  ?  : );

          if (u->ch[t] == NULL){

             u->ch[t] = NEW();

             u->ch[t]->val = t;

             u->ch[t]->num = a->ch[t]->num + ;

          }

          u->ch[t ^ ] = a -> ch[t ^ ];

          u = u -> ch[t];

          a = a -> ch[t];

      }

      return;

 }

 int find(Node *&a, Node *&b, int val){

     int Ans = ;

     Node *x = a, *y = b;

     for (int i = ; i >= ; i--){

         int t = (((( << i) & val) ==  ?  : ) ^ );

         if (x->ch[t] == NULL || (x->ch[t]->num - y->ch[t]->num) <= ) t = (t ^ );

         Ans += ( << i) * t;

         x = x->ch[t];

         y = y->ch[t];

     }

     //Ans += t;

     return Ans;

 }

 void prepare(){

      memset(Max, , sizeof( Max ));

      Pos = ;//Pos为块状链表的标号

      list[Pos++].init();

      insert(root[], root[], );//插入可持久化trie

      for (int cur = , i = ; i <= n; cur = list[cur].next){

          int j, M = ;//M用来记录块的最大值

          for (j = ; j < SIZE && i <= n; i++, j++){

              list[cur].data[j] = data[i];

              list[cur].size++;

              insert(root[i + ], root[i], data[i]);//插入可持久化trie

              int M2 = data[i];

              //M2 = find(root[i + 1], root[cur * SIZE], list[cur].data[j]);

              //printf("%d\n", M2);

              //if (M2 == data[i]) M2 = 0;//显然如果是它自己不如不加即直接从开头一直异或到i

              //Max[cur][cur] = M2;

              for (int k = Pos - ; k >= ; k--){

                  int tmp = find(root[i + ], root[k * SIZE], data[i]);

                  //if (tmp == data[i]) tmp = 0;

                  if ((M2 ^ data[i]) < (tmp ^ data[i])) M2 = tmp;

                  Max[k][cur] = max(Max[k][cur], M2 ^ data[i]);//顺便利用O(sqrt(n))的时间预处理出Max数组

              }

          }

          //创建新块

          if (j == SIZE){

             list[Pos].init();

             list[cur].next = Pos++;

          }

      }

      //printf("%d\n", root[1]->ch[0]->ch[1]->num);

 }

 int query(int l, int r){

      int x = (l - ) / SIZE, y = (r - ) / SIZE;//x代表l和r所代表的块

      int Ans = ;

      if (x == y){

            for (int i = l; i <= r; i++)

                Ans = max(Ans, find(root[r + ], root[l - ], data[i]) ^ data[i]);

            return Ans;

      }else{

            if (x  <= y - ) Ans = Max[x ][y - ];

            //for (int i = r; i >= l; i--) if ((data[i] ^ data[i - 1]) == 32767) printf("fuck");

            for (int i = l; i <= ((x + ) * SIZE) && i <= n; i++) Ans = max(Ans, find(root[r + ], root[l - ], data[i]) ^ data[i]);

            for (int i = r; i > y * SIZE; i--) Ans = max(Ans, find(root[r + ], root[l - ], data[i]) ^ data[i]);

            return Ans;

            //for (int i = l; i <= r; i++)

            //    Ans = max(Ans, find(root[r + 1], root[l - 1], data[i]) ^ data[i]);

            //return Ans;

      }

 }

 //处理询问

 void work(){

      int last_ans = ;

      for (int i = ; i <= m; i++){

          int x, y, l, r;

          scanf("%d%d", &l, &r);

          //l--;

          //l = min(((ll)((ll)x + (ll)last_ans) % n) + 1 , ((ll)((ll)y + (ll)last_ans) % n)+ 1);

          //r = max(((ll)((ll)x + (ll)last_ans) % n) + 1 , ((ll)((ll)y + (ll)last_ans) % n)+ 1);

          last_ans = query(l, r);

          printf("%d\n", last_ans);

      }

 }

 //单纯的插入一个数

 void build(Node *&b, int x){

      Node *u = b;

      for (int i = ; i >= ; i--){

          int t = ((( << i) & x) ==  ?  : );//表示这一位是否是0

          if (u->ch[t] == NULL){

             u->ch[t] = NEW();

             u->ch[t]->val = t;

             u->ch[t]->num = ;//注意，这里仅仅只是建树，所以不能改数字

          }

          u = u->ch[t];

      }

      return;

 }

 void init(){

      //读入+建初始树

      scanf("%d%d", &n, &m);

      for (int i = ; i < N; i++) root[i] = NULL;

      root[] = NEW();

      data[] = ;

      for (int i = ; i <= n; i++){

          scanf("%d", &data[i]);

          data[i] = data[i] ^ data[i - ];

          build(root[], data[i]);

          //printf("%d\n", data[i]);

      }

      build(root[], );//记得加0

      //printf("%d", root[0]->val);

 }

 void debug(){

      insert(root[], root[], );

      insert(root[], root[], );

      insert(root[], root[], );

      printf("%d\n", find(root[], root[], ));

 }

 int main(){

     #ifdef LOCAL

     freopen("data.txt",  "r",  stdin);

     freopen("out.txt",  "w",  stdout);

     #endif

     init();

     prepare();

     work();

     printf("%d\n", tot);

     //debug();

     return ;

 }

巴特西