fork download
copy 
  1. import java.io.*;
  2. import java.util.Arrays;
  3. import java.util.Locale;
  4. import java.util.StringTokenizer;
  5.  
  6. public class TaskE_opt {
  7.     private final InputReader reader;
  8.     private final OutputWriter writer;
  9.  
  10.     public TaskE_opt(InputReader reader, OutputWriter writer) {
  11.         this.reader = reader;
  12.         this.writer = writer;
  13.     }
  14.  
  15.     public static void main(String[] args) {
  16.         InputReader reader = new InputReader(System.in);
  17.         OutputWriter writer = new OutputWriter(System.out);
  18.         new TaskE_opt(reader, writer).run();
  19.         writer.writer.flush();
  20.     }
  21.  
  22.     class FixedPointSegmentTree {
  23.         int[] T;
  24.         int N;
  25.         FixedPointSegmentTree(int n) {
  26.             N = 1;
  27.             while (N < n)
  28.                 N <<= 1;
  29.             T = new int[2 * N];
  30.         }
  31.         void add(int l, int r, int x) {
  32.             l += N;
  33.             r += N;
  34.             while (r >= l) {
  35.                 if ((l & 1) == 1)
  36.                     T[l] ^= x;
  37.                 if ((r & 1) == 0)
  38.                     T[r] ^= x;
  39.                 l = (l + 1) >> 1;
  40.                 r = (r - 1) >> 1;
  41.             }
  42.         }
  43.         int get(int i) {
  44.             for (int l = 0, r = N - 1, v = 1; ; ) {
  45.                 if (l == r)
  46.                     return T[v];
  47.                 T[2 * v] ^= T[v];
  48.                 T[2 * v + 1] ^= T[v];
  49.                 T[v] = 0;
  50.                 if (i <= (l + r) / 2) {
  51.                     r = (l + r) / 2;
  52.                     v = 2 * v;
  53.                 } else {
  54.                     l = (l + r) / 2 + 1;
  55.                     v = 2 * v + 1;
  56.                 }
  57.             }
  58.         }
  59.     }
  60.  
  61.     final int K = 30;
  62.     int[] tmp = new int[50 * K];
  63.     int tn = 0;
  64.     int gauss(int[] C) {
  65.         int pt = 0;
  66.         for (int i = 0; i < K; i++) {
  67.             int ind = -1;
  68.             for (int j = pt; j < tn; j++) {
  69.                 if (((tmp[j] >> i) & 1) == 1)
  70.                     ind = j;
  71.             }
  72.             if (ind == -1)
  73.                 continue;
  74.             C[pt] = tmp[ind];
  75.             tmp[ind] = tmp[pt];
  76.             for (int j = pt + 1; j < tn; j++)
  77.                 if (((tmp[j] >> i) & 1) == 1)
  78.                     tmp[j] ^= C[pt];
  79.             pt++;
  80.         }
  81.         return pt;
  82.     }
  83.  
  84.     int merge(int[] A, int apt, int[] B, int bpt, int[] C) {
  85.         tn = 0;
  86.         for (int i = 0; i < apt; i++) {
  87.             if (A[i] == 0)
  88.                 break;
  89.             tmp[tn++] = A[i];
  90.         }
  91.         for (int i = 0; i < bpt; i++) {
  92.             if (B[i] == 0)
  93.                 break;
  94.             tmp[tn++] = B[i];
  95.         }
  96.         return gauss(C);
  97.     }
  98.  
  99.     void write(int[] A, int len) {
  100.         for (int i = 0; i < len; i++)
  101.             tmp[tn++] = A[i];
  102.     }
  103.  
  104.     class BasisSegmentTree {
  105.         int[][] T;
  106.         int[] Tpt;
  107.         int N = 1;
  108.  
  109.         BasisSegmentTree(int n) {
  110.             while (N < n)
  111.                 N <<= 1;
  112.             T = new int[2 * N][K];
  113.             Tpt = new int[2 * N];
  114.         }
  115.  
  116.         void init() {
  117.             for (int i = N - 1; i > 0; i--)
  118.                 Tpt[i] = merge(T[2 * i], Tpt[2 * i], T[2 * i + 1], Tpt[2 * i + 1], T[i]);
  119.         }
  120.  
  121.         void update(int x, int v) {
  122.             if (x < 0 || x >= N)
  123.                 return;
  124.             x += N;
  125.             T[x][0] ^= v;
  126.             Tpt[x] = (T[x][0] == 0) ? 0 : 1;
  127.             while ((x >>= 1) > 0)
  128.                 Tpt[x] = merge(T[2 * x], Tpt[2 * x], T[2 * x + 1], Tpt[2 * x + 1], T[x]);
  129.         }
  130.         void get(int l, int r) {
  131.             l += N;
  132.             r += N;
  133.             int tpt = 0;
  134.             tn = 0;
  135.             while (l <= r) {
  136.                 if ((l & 1) == 1)
  137.                     write(T[l], Tpt[l]);
  138.                 if ((r & 1) == 0)
  139.                     write(T[r], Tpt[r]);
  140.                 l = (l + 1) >> 1;
  141.                 r = (r - 1) >> 1;
  142.             }
  143.         }
  144.     }
  145.  
  146.     public void run() {
  147.         int n = reader.nextInt();
  148.         int q = reader.nextInt();
  149.  
  150.         FixedPointSegmentTree T = new FixedPointSegmentTree(n);
  151.         BasisSegmentTree B = new BasisSegmentTree(n - 1);
  152.  
  153.         int lst = 0;
  154.         for (int i = 0; i < n; i++) {
  155.             int t = reader.nextInt();
  156.             T.T[T.N + i] = t;
  157.             if (i > 0) {
  158.                 B.T[B.N + i - 1][0] = t ^ lst;
  159.                 B.Tpt[B.N + i - 1] = ((t ^ lst) > 0) ? 1 : 0;
  160.             }
  161.             lst = t;
  162.         }
  163.         B.init();
  164.         int[] to = new int[K];
  165.         for (int i = 0; i < q; i++) {
  166.             int t = reader.nextInt();
  167.             if (t == 1) {
  168.                 int l = reader.nextInt() - 1;
  169.                 int r = reader.nextInt() - 1;
  170.                 int x = reader.nextInt();
  171.                 B.update(l - 1, x);
  172.                 B.update(r, x);
  173.                 T.add(l, r, x);
  174.             } else {
  175.                 int l = reader.nextInt() - 1;
  176.                 int r = reader.nextInt() - 1;
  177.                 B.get(l, r - 1);
  178.                 tmp[tn++] = T.get(l);
  179.                 int res = gauss(to);
  180.                 writer.printf("%d\n", 1 << res);
  181.             }
  182.         }
  183.     }
  184.     static class InputReader {
  185.         public BufferedReader reader;
  186.         public StringTokenizer tokenizer;
  187.  
  188.         public InputReader(InputStream stream) {
  189.             reader = new BufferedReader(new InputStreamReader(stream), 32768);
  190.             tokenizer = null;
  191.         }
  192.  
  193.         public String next() {
  194.             while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  195.                 try {
  196.                     tokenizer = new StringTokenizer(reader.readLine());
  197.                 } catch (IOException e) {
  198.                     throw new RuntimeException(e);
  199.                 }
  200.             }
  201.             return tokenizer.nextToken();
  202.         }
  203.  
  204.         public int nextInt() {
  205.             return Integer.parseInt(next());
  206.         }
  207.  
  208.         public double nextDouble() {
  209.             return Double.parseDouble(next());
  210.         }
  211.  
  212.         public long nextLong() {
  213.             return Long.parseLong(next());
  214.         }
  215.     }
  216.  
  217.     static class OutputWriter {
  218.         public PrintWriter writer;
  219.  
  220.         OutputWriter(OutputStream stream) {
  221.             writer = new PrintWriter(stream);
  222.         }
  223.  
  224.         public void printf(String format, Object... args) {
  225.             writer.print(String.format(Locale.ENGLISH, format, args));
  226.         }
  227.     }
  228. }
  229.  
  230.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:6: error: class TaskE_opt is public, should be declared in a file named TaskE_opt.java
public class TaskE_opt {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/XNsXoa
language:
Java (12.0.1)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!