fork download
copy 
  1. import java.io.*;
  2.  
  3. /**
  4.  * Created by Sony on 27-12-2017.
  5.  */
  6.  
  7. class CSUBQ {
  8.     public static String FILE = "CSUBQIn.txt";
  9.     public static void main(String[] args) throws IOException {
  10. //        TestGenerator.testGenerator();
  11.         String str = System.getProperty("user.dir");
  12.         Reader reader = null;
  13.         if (str.startsWith("C:")) {
  14.             reader = new Reader(FILE);
  15.         } else {
  16.              reader = new Reader();
  17.         }
  18.  
  19.         StringBuilder sb = new StringBuilder();
  20.  
  21.         int i = 0, N, Q, x, l, r;
  22.         long y, L, R;
  23.  
  24.         N = reader.nextInt();
  25.         Q = reader.nextInt();
  26.         L = reader.nextInt();
  27.         R = reader.nextInt();
  28.  
  29.         Segtree t1 = new Segtree(N, R);
  30.         Segtree t2 = new Segtree(N, L - 1);
  31.  
  32.         while (i < Q) {
  33.             i++;
  34.             int option = reader.nextInt();
  35.             int a = reader.nextInt();
  36.             int b = reader.nextInt();
  37.             if (option == 1) {
  38.                 x = a;
  39.                 y = b;
  40.                 if( t1.shouldUpdate(y, x-1) ) {
  41.                     t1.update(1, x - 1, y);
  42.                 }
  43.                 if( t2.shouldUpdate(y, x-1) ) {
  44.                     t2.update(1, x - 1, y);
  45.                 }
  46.             } else {
  47.                 l = a;
  48.                 r = b;
  49.                 long answer = t1.query(1, l - 1, r - 1).total - t2.query(1, l - 1, r - 1).total;
  50.                 sb.append(answer).append("\n");
  51.             }
  52.         }
  53.         System.out.println(sb);
  54.     }
  55. }
  56.  
  57. class Segtree {
  58.  
  59.     public long M;
  60.     public long[] array;
  61.     private Node[] heap;
  62.     private int sz;
  63.  
  64.     //The Node class represents a partition range of the array.
  65.     static class Node {
  66.         int pre, suf, inter, l, r, len;
  67.         long total;
  68.  
  69.         boolean isLeaf() {
  70.             return l == r;
  71.         }
  72.  
  73.         public Node() {
  74.         }
  75.  
  76.         public Node(Node node) {
  77.             this.pre = node.pre;
  78.             this.suf = node.suf;
  79.             this.inter = node.inter;
  80.             this.l = node.l;
  81.             this.r = node.r;
  82.             this.len = node.len;
  83.             this.total = node.total;
  84.         }
  85.     }
  86.  
  87.     public Segtree(int n, long m) {
  88.         this.M = m;
  89.         this.array = new long[n];
  90.         //The max size of this array is about 2 * 2 ^ log2(n) + 1
  91.         sz = (int) (2 * Math.pow(2.0, Math.floor((Math.log((double) n) / Math.log(2.0)) + 1)));
  92.         heap = new Node[sz];
  93.         build(1, 0, n);
  94.     }
  95.  
  96.     public boolean isElementWithinRange(long val) {
  97.         return val <= M;
  98.     }
  99.  
  100.     private void build(int n, int l, int sz) {
  101.         heap[n] = new Node();
  102.         heap[n].l = l;
  103.         heap[n].r = l + sz - 1;
  104.         heap[n].len = sz;
  105.         if (sz == 1) {
  106.             initLeaf(n, this.array[l]);
  107.             return;
  108.         } else {
  109.             build(2 * n, l, sz / 2);
  110.             build(2 * n + 1, l + sz / 2, sz - sz / 2);
  111.             balance(n);
  112.         }
  113.     }
  114.  
  115.     private Node balance(int n) {
  116.         Node node = heap[n];
  117.         if (node.isLeaf()) {
  118.             return node;
  119.         }
  120.  
  121.         //get refs to child nodes
  122.         //TODO: left and right can be null, or is it.. ??. NO the tree is built in such way the you never get children as null
  123.         Node left = heap[2 * n];
  124.         Node right = heap[2 * n + 1];
  125.  
  126.         return balance(node, left, right);
  127.     }
  128.  
  129.     private Node balance(Node node, Node left, Node right) {
  130.         //set prefix for node
  131.         if (left.pre < left.len) {
  132.             node.pre = left.pre;
  133.         } else {
  134.             node.pre = left.pre + right.pre;
  135.         }
  136.  
  137.         //set suffix for node
  138.         if (right.suf < right.len) {
  139.             node.suf = right.suf;
  140.         } else {
  141.             node.suf = left.suf + right.suf;
  142.         }
  143.  
  144.         //set intersection for node
  145.         node.inter = left.suf + right.pre;
  146.  
  147.         node.total = left.total + right.total + f(left.suf + right.pre) - f(left.suf) - f(right.pre);
  148.  
  149.         node.len = left.len + right.len;
  150.  
  151.         return node;
  152.     }
  153.  
  154.     private long f(long n) {
  155.         return ((n + 1) * (n)) / 2;
  156.     }
  157.  
  158.     private void initLeaf(int n, long y) {
  159.         if (isElementWithinRange(y)) {
  160.             heap[n].pre = 1;
  161.             heap[n].suf = 1;
  162.             heap[n].total = 1;
  163.         } else {
  164.             heap[n].pre = 0;
  165.             heap[n].suf = 0;
  166.             heap[n].total = 0;
  167.         }
  168.     }
  169.  
  170.     private void heapify(int n) {
  171.         while (n > 0) {
  172.             balance(n);
  173.             n = n >> 1;
  174.         }
  175.     }
  176.  
  177.     public void update(int n, int x, long y) {
  178.         if (heap[n].isLeaf()) {
  179.             array[x] = y;
  180.             initLeaf(n, y);
  181. //            heapify(n);
  182.             return;
  183.         }
  184.         Node left = heap[2 * n];
  185.         if (x <= left.r) {
  186.             update(2 * n, x, y);
  187.         } else {
  188.             update(2 * n + 1, x, y);
  189.         }
  190.         balance(n);
  191.     }
  192.  
  193.     public Node query(int n, int l, int r) {
  194.         Node node = new Node(heap[n]);
  195.         if (l == node.l && r == node.r) {
  196.             return node;
  197.         }
  198.  
  199.         Node lc = heap[2 * n];
  200.         Node rc = heap[2 * n + 1];
  201.  
  202.         if (r <= lc.r) {
  203.             return query(2 * n, l, r);
  204.         }
  205.  
  206.         if (l >= rc.l) {
  207.             return query(2 * n + 1, l, r);
  208.         }
  209.  
  210.         //TODO: is it necessary to create nodes at runtime to answer queries?
  211.         Node ln = query(2 * n, l, lc.r);
  212.         Node rn = query(2 * n + 1, lc.r + 1, r);
  213.  
  214.         return balance(node, ln, rn);
  215.     }
  216.  
  217.     public boolean shouldUpdate(long y, int x) {
  218.         return ( (y <= M && array[x] > M ) || (y > M && array[x] <= M) );
  219.     }
  220.  
  221. }
  222.  
  223. class Reader {
  224.     final private int BUFFER_SIZE = 1 << 16;
  225.     private DataInputStream din;
  226.     private byte[] buffer;
  227.     private int bufferPointer, bytesRead;
  228.  
  229.     public Reader() {
  230.         din = new DataInputStream(System.in);
  231.         buffer = new byte[BUFFER_SIZE];
  232.         bufferPointer = bytesRead = 0;
  233.     }
  234.  
  235.     public Reader(String file_name) throws IOException {
  236.         din = new DataInputStream(new FileInputStream(file_name));
  237.         buffer = new byte[BUFFER_SIZE];
  238.         bufferPointer = bytesRead = 0;
  239.     }
  240.  
  241.     public String readLine() throws IOException {
  242.         byte[] buf = new byte[64]; // line length
  243.         int cnt = 0, c;
  244.         while ((c = read()) != -1) {
  245.             if (c == '\n')
  246.                 break;
  247.             buf[cnt++] = (byte) c;
  248.         }
  249.         return new String(buf, 0, cnt);
  250.     }
  251.  
  252.     public int nextInt() throws IOException {
  253.         int ret = 0;
  254.         byte c = read();
  255.         while (c <= ' ')
  256.             c = read();
  257.         boolean neg = (c == '-');
  258.         if (neg)
  259.             c = read();
  260.         do {
  261.             ret = ret * 10 + c - '0';
  262.         } while ((c = read()) >= '0' && c <= '9');
  263.  
  264.         if (neg)
  265.             return -ret;
  266.         return ret;
  267.     }
  268.  
  269.     public long nextLong() throws IOException {
  270.         long ret = 0;
  271.         byte c = read();
  272.         while (c <= ' ')
  273.             c = read();
  274.         boolean neg = (c == '-');
  275.         if (neg)
  276.             c = read();
  277.         do {
  278.             ret = ret * 10 + c - '0';
  279.         }
  280.         while ((c = read()) >= '0' && c <= '9');
  281.         if (neg)
  282.             return -ret;
  283.         return ret;
  284.     }
  285.  
  286.     public double nextDouble() throws IOException {
  287.         double ret = 0, div = 1;
  288.         byte c = read();
  289.         while (c <= ' ')
  290.             c = read();
  291.         boolean neg = (c == '-');
  292.         if (neg)
  293.             c = read();
  294.  
  295.         do {
  296.             ret = ret * 10 + c - '0';
  297.         }
  298.         while ((c = read()) >= '0' && c <= '9');
  299.  
  300.         if (c == '.') {
  301.             while ((c = read()) >= '0' && c <= '9') {
  302.                 ret += (c - '0') / (div *= 10);
  303.             }
  304.         }
  305.  
  306.         if (neg)
  307.             return -ret;
  308.         return ret;
  309.     }
  310.  
  311.     private void fillBuffer() throws IOException {
  312.         bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  313.         if (bytesRead == -1)
  314.             buffer[0] = -1;
  315.     }
  316.  
  317.     private byte read() throws IOException {
  318.         if (bufferPointer == bytesRead)
  319.             fillBuffer();
  320.         return buffer[bufferPointer++];
  321.     }
  322.  
  323.     public void close() throws IOException {
  324.         if (din == null)
  325.             return;
  326.         din.close();
  327.     }
  328. }
  329.  
  330.  
  331.  
  332.  
  333. //5 6 1 10
  334. //1 1 2
  335. //2 1 5
  336. //1 3 11
  337. //1 4 3
  338. //2 3 5
  339. //2 1 5
  340.  
  341. //#2
  342. //7 7 1 6
  343. //2 1 7
  344. //1 1 4
  345. //2 1 7
  346. //2 1 2
  347. //1 4 6
  348. //1 2 1
  349. //2 1 7
  350.  
  351. //#3
  352. //7 7 1 6
  353. //2 1 7
  354. //1 2 4
  355. //2 1 7
  356. //2 1 2
  357. //1 5 6
  358. //1 3 1
  359. //2 1 7
  360.  
  361. //#4
  362. //5 9 1 5
  363. //2 1 5
  364. //1 2 1
  365. //2 1 5
  366. //1 2 0
  367. //2 1 5
  368. //1 1 1
  369. //2 1 5
  370. //1 2 1
  371. //2 1 5
  372.  
  373. //#5
  374. //10 7 1 500
  375. //1 5 45
  376. //2 3 6
  377. //1 8 600
  378. //2 2 7
  379. //1 10 10
  380. //1 2 800
  381. //2 1 10
  382.  
  383. //#6
  384. //100 7 100 100000000
  385. //1 50 45
  386. //2 30 60
  387. //1 80 600
  388. //2 20 70
  389. //1 100 99
  390. //1 20 800
  391. //2 10 100
  392.  
  393. //#7
  394. //100 5 100 100000000
  395. //1 80 600
  396. //2 20 70
  397. //1 100 100
  398. //1 20 800
  399. //2 10 100
  400.  
  401. //class TestGenerator {
  402. //    public static void testGenerator() throws IOException {
  403. //        BufferedWriter writer = new BufferedWriter(new FileWriter(Mainy.FILE, true));
  404. //        int n = 1;
  405. //
  406. //        writer.append(100000 + " ");
  407. //        writer.append(100000 + " ");
  408. //        writer.append(2 + " ");
  409. //        writer.append(100000000 + "\n");
  410. //
  411. //        writer.append("1 " + 1 + " " + 100000 + "\n");
  412. //
  413. //        for (int i = 1; i < 100000; i++) {
  414. //            writer.append("2 " + i + " " + i + "\n");
  415. //        }
  416. ////        writer.append("\n");
  417. ////        for (int i = 0; i < n; i++) {
  418. ////            writer.append(0 + " ");
  419. ////        }
  420. ////        writer.append("\n");
  421. ////        for (int i = n - 1; i >= 0; i--) {
  422. ////            writer.append(i + " ");
  423. ////        }
  424. //
  425. //        writer.close();
  426. //    }
  427. //}
  428.  
Success #stdin #stdout 0.1s 27912KB
comments (?)
stdin
copy 
5 6 1 10
1 1 2
2 1 5 
1 3 11
1 4 3
2 3 5
2 1 5
stdout
copy 
5
2
4
https://ideone.com/EwmVSH
language:
Java (HotSpot 12)
created:
6 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!