fork download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStream;
  4. import java.io.InputStreamReader;
  5. import java.util.Arrays;
  6.  
  7. import static java.lang.Integer.parseInt;
  8.  
  9. class FlippingCoins {
  10.  
  11.     static int tree[] = new int[400010];
  12.     static int lazy[] = new int[400010];
  13.     static final int UNDEFINED = -1;
  14.  
  15.     public static void main(String[] args) throws IOException {
  16.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  17.         FastReader reader = FastReader.SYSTEM_READER;
  18.         int n, q;
  19.         String s[];
  20.         //s = br.readLine().split("\\s");
  21.         n = reader.nextInt();
  22.         q = reader.nextInt();
  23.         Arrays.fill(lazy, 0, 200010, -1);
  24.         for (int i = 0; i < q; i++) {
  25.             //s = br.readLine().split("\\s");
  26.             int type = reader.nextInt();
  27.             int A = reader.nextInt();
  28.             int B = reader.nextInt();
  29.             if (type == 1) {
  30.                 System.out.println(query(1, 0, n - 1, A, B));
  31.             } else {
  32.                 update(1, 0, n - 1, A, B);
  33.             }
  34.         }
  35.     }
  36.  
  37.     private static int query(int id, int start, int end, int a, int b) {
  38.         if (a > end || b < start) {
  39.             return 0;
  40.         }
  41.         if (start >= a && end <= b) {
  42.             return tree[id];
  43.         }
  44.         if (lazy[id] > 0) {
  45.             shift(id, start, end);
  46.         }
  47.         int mid = (start + end) / 2;
  48.         return query(id << 1, start, mid, a, b) + query((id << 1) + 1, mid + 1, end, a, b);
  49.     }
  50.  
  51.     private static void update(int id, int start, int end, int a, int b) {
  52.         if (a > end || b < start) {
  53.             return;
  54.         }
  55.         if (start >= a && end <= b) {
  56.             updateNode(id, start, end);
  57.             return;
  58.         }
  59.         if (lazy[id] > 0) {
  60.             shift(id, start, end);
  61.         }
  62.         int mid = (start + end) / 2;
  63.         update(id << 1, start, mid, a, b);
  64.         update((id << 1) + 1, mid + 1, end, a, b);
  65.         tree[id] = tree[id << 1] + tree[(id << 1) + 1];
  66.     }
  67.  
  68.     private static void updateNode(int id, int start, int end) {
  69.         lazy[id] = 1-lazy[id];
  70.         tree[id] = (end - start + 1) - tree[id];
  71.     }
  72.  
  73.     private static void shift(int id, int start, int end) {
  74.         int mid = (start + end) / 2;
  75.         lazy[id << 1] = lazy[id];
  76.         lazy[(id << 1) + 1] = lazy[id];
  77.         tree[id << 1] = (mid - start + 1) - tree[id<<1];
  78.         tree[(id << 1) + 1] = (end - (mid + 1) + 1) - tree[(id << 1) + 1];
  79.         /*updateNode((id << 1), start, mid);
  80.         updateNode((id << 1) + 1, start, mid);*/
  81.         lazy[id] = 0;
  82.     }
  83.  
  84.     static final class FastReader {
  85.         public static final FastReader SYSTEM_READER = new FastReader(System.in);
  86.         private final InputStream in;
  87.         private final byte[] buffer = new byte[1 << 16];
  88.         private int pos, count;
  89.  
  90.         public FastReader(InputStream in) {
  91.             this.in = in;
  92.             pos = count = 0;
  93.         }
  94.  
  95.         public int nextInt() {
  96.             int c;
  97.             while ((c = read()) < '0');
  98.             int result = c - '0';
  99.             while ((c = read() - '0') >= 0)
  100.                 result = 10 * result + c;
  101.             return result;
  102.         }
  103.         public long nextLong() {
  104.             int c;
  105.             while ((c = read()) < '0');
  106.             long result = c - '0';
  107.             while ((c = read() - '0') >= 0)
  108.                 result = 10 * result + c;
  109.             return result;
  110.         }
  111.  
  112.         public String nextString() {
  113.             StringBuilder s = new StringBuilder();
  114.             int c;
  115.             while ((c = read()) >= 33)
  116.                 s.append((char) c);
  117.             return s.toString();
  118.         }
  119.  
  120.         private void fillBuffer() {
  121.             try {
  122.                 count = in.read(buffer, pos = 0, buffer.length);
  123.             } catch (Exception e) {
  124.             }
  125.         }
  126.  
  127.         public int read() {
  128.             if (pos == count)
  129.                 fillBuffer();
  130.             return buffer[pos++];
  131.         }
  132.     }
  133.  
  134.  
  135. }
Success #stdin #stdout 0.1s 31476KB
comments (?)
stdin
copy 
4 5
1 0 0
0 0 0 
1 0 0
0 0 3
1 0 0
stdout
copy 
0
1
0
https://ideone.com/jN6fHk
language:
Java (HotSpot 12)
created:
5 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!