Guest User

UPDATEIT

a guest
Jun 2nd, 2018
137
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.99 KB | None | 0 0
  1. import java.io.IOException;
  2. import java.io.InputStream;
  3. import java.util.Arrays;
  4.  
  5. class UPDATEIT {
  6.  
  7.     static int tree[] = new int[40010];
  8.     static int lazy[] = new int[40010];
  9.  
  10.     public static void main(String[] args) throws IOException {
  11.         //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  12.         FastReader reader = FastReader.SYSTEM_READER;
  13.         int t, n, u, v, q;
  14.         String s[];
  15.         t = reader.nextInt();
  16.         while (t-- > 0) {
  17.             StringBuilder sbr = new StringBuilder();
  18.             //s = br.readLine().split("\\s");
  19.             n = reader.nextInt();
  20.             u = reader.nextInt();
  21.             Arrays.fill(lazy, 0, 2 * n + 10, 0);
  22.             Arrays.fill(tree, 0, 2 * n + 10, 0);
  23.             for (int i = 0; i < u; i++) {
  24.                 //s = br.readLine().split("\\s");
  25.                 int l = reader.nextInt();
  26.                 int r = reader.nextInt();
  27.                 int val = reader.nextInt();
  28.                 update(1, 0, n - 1, l, r, val);
  29.             }
  30.             q = reader.nextInt();
  31.             for (int i = 0; i < q; i++) {
  32.                 int idx = reader.nextInt();
  33.                 sbr.append(query(1, 0, n - 1, idx, idx)).append("\n");
  34.             }
  35.             System.out.print(sbr.toString());
  36.         }
  37.     }
  38.     private static void update(int id, int start, int end, int l, int r, int val) {
  39.         if (end < l || start > r) {
  40.             return;
  41.         }
  42.         if (start >= l && end <= r) {
  43.             updateNode(id,start,end,val);
  44.             return;
  45.         }
  46.         shift(id, start, end);
  47.         int mid = (start + end) / 2;
  48.         update(id << 1, start, mid, l, r, val);
  49.         update((id << 1) + 1, mid + 1, end, l, r, val);
  50.         tree[id] = tree[id << 1] + tree[(id << 1) + 1];
  51.     }
  52.     private static int query(int id, int start, int end, int l, int r) {
  53.         if (end < l || start > r) {
  54.             return 0;
  55.         }
  56.         if (start >= l && end <= r) {
  57.             return tree[id];
  58.         }
  59.         shift(id, start, end);
  60.         int mid = (start + end) / 2;
  61.         return query(id << 1, start, mid, l, r) + query((id << 1) + 1, mid + 1, end, l, r);
  62.     }
  63.     private static void shift(int id, int start, int end) {
  64.         int mid = (start + end) / 2;
  65.         updateNode(id << 1, start, mid, lazy[id]);
  66.         updateNode((id << 1) + 1, mid + 1, end, lazy[id]);
  67.         lazy[id] = 0;
  68.     }
  69.     private static void updateNode(int id, int start, int end, int val) {
  70.         lazy[id] += val;
  71.         tree[id] += (end - start + 1) * val;
  72.     }
  73.     static final class FastReader {
  74.         public static final FastReader SYSTEM_READER = new FastReader(System.in);
  75.         private final InputStream in;
  76.         private final byte[] buffer = new byte[1 << 16];
  77.         private int pos, count;
  78.  
  79.         public FastReader(InputStream in) {
  80.             this.in = in;
  81.             pos = count = 0;
  82.         }
  83.  
  84.         public int nextInt() {
  85.             int c;
  86.             while ((c = read()) < '0');
  87.             int result = c - '0';
  88.             while ((c = read() - '0') >= 0)
  89.                 result = 10 * result + c;
  90.             return result;
  91.         }
  92.         public long nextLong() {
  93.             int c;
  94.             while ((c = read()) < '0');
  95.             long result = c - '0';
  96.             while ((c = read() - '0') >= 0)
  97.                 result = 10 * result + c;
  98.             return result;
  99.         }
  100.  
  101.         public String nextString() {
  102.             StringBuilder s = new StringBuilder();
  103.             int c;
  104.             while ((c = read()) >= 33)
  105.                 s.append((char) c);
  106.             return s.toString();
  107.         }
  108.  
  109.         private void fillBuffer() {
  110.             try {
  111.                 count = in.read(buffer, pos = 0, buffer.length);
  112.             } catch (Exception e) {
  113.             }
  114.         }
  115.  
  116.         public int read() {
  117.             if (pos == count)
  118.                 fillBuffer();
  119.             return buffer[pos++];
  120.         }
  121.     }
  122.  
  123. }
Add Comment
Please, Sign In to add comment