Z1.java

Z1.java

package s0;

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Arrays;

public class Z1 {
  public static final int level = 18;

  public int data[];
  public int levelStep[];
  public int levelBase[];

  public void initArrays() {
    data = new int[1 << level + 1];
    levelStep = new int[level];
    levelBase = new int[level];

    for (int i = 0; i < level; i++) {
      levelStep[i] = 1 << i;
//      System.out.println(levelStep[i]);
    }

    int base = 0;
    for (int i = 0; i < level; i++) {
      levelBase[i] = base;
      base += levelStep[level - 1 - i] * 2;
//      System.out.println(levelBase[i]);
    }
  }

  public int rangeSum(int b, int e) {
    int sum = 0;
    int level = 0;
    int o = b;
    int o2;
    int o3;
    int e1 = e + 1;
    int c = 0;

    while (true) {
      if ((o & levelStep[level]) == 0) {
        level += 1;
        continue;
      }

      o2 = o + levelStep[level];

      if (o2 > e1) {
        break;
      }

      o3 = (o >> (level)) + levelBase[level];
      sum += data[o3];
      // c += 1 << level;
      // System.out.format("%d - %d - %d - %d - %d/%X/%s\n", level, c, o3, sum, o, o, Integer.toBinaryString(o));
      o = o2;
      level += 1;
    }

    if (o == e1) {
      return sum;
    }

    while (true) {
      o2 = o + levelStep[level];
      if (o2 > e1) {
        level -= 1;
        if (level < 0) {
          break;
        }
        continue;
      }

      o3 = (o >> (level)) + levelBase[level];
      sum += data[o3];
      // c += 1 << level;
      // System.out.format("%d - %d - %d - %d - %d/%X/%s\n", level, c, o3, sum, o, o, Integer.toBinaryString(o));
      o = o2;
      level -= 1;

      if (o2 == e1) {
        return sum;
      }
    }

    return 0;
  }

  public void add(int s, int v) {
    int s0 = s;

    for (int l = 0; l < level; l++) {
      data[s0 + levelBase[l]] += v;
      // System.out.format("add - %d %d %d %d - %d %d\n", l, s0, levelBase[l], s0 + levelBase[l], v, data[s0 + levelBase[l]] );
      s0 >>= 1;
    }
  }

  public void minus(int s, int v) {
    int s0 = s;
    for (int l = 0; l < level; l++) {
      data[s0 + levelBase[l]] -= v;
      s0 >>= 1;
    }
  }


  public void process(String fn) throws IOException {
    String s = new String(Files.readAllBytes(Paths.get(fn)));
    String tokens[] = s.split("[ \n]");

    int ts = tokens.length;
    long sum = 0;

    for (int o = 0; o < ts; o += 3) {
      String action = tokens[o];
      int p1 = Integer.parseInt(tokens[o + 1]);
      int p2 = Integer.parseInt(tokens[o + 2].trim());
      switch(action.length()) {
        case 2: add(p2, p1); break;
        case 4: minus(p2, p1); break;
        case 5: {
          int q = rangeSum (p1, p2);
          sum += q;
        }
      }
    }
    // System.out.println(tokens.length);
    System.out.println(sum);
  }


  public static void main(String args[]) throws IOException {
    Z1 app = new Z1();
    long tb = System.currentTimeMillis();
    app.initArrays();
    Arrays.fill(app.data, 0);
    app.process("misc/144043063958496.txt");
    long te = System.currentTimeMillis();
    System.out.println((te - tb) + " ms");
  }
}

// data URL http://121.201.63.168/download/144043063958496.txt