Advertisement
999ms

Untitled

Apr 20th, 2019
196
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 6.39 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class Main {
  5.  
  6.     String fileName = "";
  7.  
  8.     void solve() throws IOException {
  9.         int n = readInt();
  10.  
  11.     }
  12.  
  13.     class FenwickTree {
  14.         long[] t;
  15.         int n;
  16.  
  17.         FenwickTree(int n) {
  18.             this.n = n;
  19.             t = new long[n];
  20.         }
  21.  
  22.         void add(int i, int val) {
  23.             while (i < n) {
  24.                 t[i] += val;
  25.                 i = (i + 1) | i;
  26.             }
  27.         }
  28.  
  29.         long get(int i) {
  30.             long ans = 0;
  31.             while (i >= 0) {
  32.                 ans += t[i];
  33.                 i = (i & (i + 1)) - 1;
  34.             }
  35.             return ans;
  36.         }
  37.  
  38.         long get(int l, int r) {
  39.             return get(r) - (l > 0 ? get(l - 1) : 0);
  40.         }
  41.     }
  42.  
  43.     int[] buffer = new int[1 << 20];
  44.  
  45.     int[] merger(int[] a, int[] b) {
  46.         int itr1 = 0;
  47.         int itr2 = 0;
  48.         while (itr1 < a.length && itr2 < b.length) {
  49.             if (a[itr1] < b[itr2]) {
  50.                 buffer[itr1 + itr2] = a[itr1++];
  51.             } else {
  52.                 buffer[itr1 + itr2] = b[itr2++];
  53.             }
  54.         }
  55.         while (itr1 < a.length) {
  56.             buffer[itr1 + itr2] = a[itr1++];
  57.         }
  58.         while (itr2 < b.length) {
  59.             buffer[itr1 + itr2] = b[itr2++];
  60.         }
  61.         int size = 0;
  62.         int prev = Integer.MIN_VALUE;
  63.         for (int i = 0; i < itr1 + itr2; i++) {
  64.             if (prev == buffer[i]) {
  65.                 continue;
  66.             } else {
  67.                 buffer[size++] = buffer[i];
  68.             }
  69.         }
  70.         int[] ans = new int[size];
  71.         for (int i = 0; i < size; i++) {
  72.             ans[i] = buffer[i];
  73.         }
  74.         return ans;
  75.     }
  76.  
  77.     class Node {
  78.         int[] y;
  79.         int n;
  80.         FenwickTree t;
  81.  
  82.         int get_ind(int val) {
  83.             int left = 0;
  84.             int right = this.y.length - 1;
  85.             int mid;
  86.             int ans = -1;
  87.             while (left <= right) {
  88.                 mid = (left + right) / 2;
  89.                 if (this.y[mid] <= val) {
  90.                     ans = mid;
  91.                     left = mid + 1;
  92.                 } else {
  93.                     right = mid - 1;
  94.                 }
  95.             }
  96.             return ans;
  97.         }
  98.  
  99.         Node(int[] y) {
  100.             this.y = y;
  101.             this.n = this.y.length;
  102.             this.t = new FenwickTree(this.n);
  103.         }
  104.  
  105.         Node(Node l, Node r) {
  106.             this.y = merger(l.y, r.y);
  107.             this.n = this.y.length;
  108.             this.t = new FenwickTree(this.n);
  109.         }
  110.  
  111.         void add(int i, int val) {
  112.             this.t.add(i, val);
  113.         }
  114.  
  115.         long get(int l, int r) {
  116.             return this.t.get(l, r);
  117.         }
  118.     }
  119.  
  120.     class SegmentTree {
  121.         Node[] t;
  122.         SegmentTree(int[][] xy) {
  123.             this.t = new Node[xy.length];
  124.             build(0, 0, xy.length, xy);
  125.         }
  126.  
  127.         void build(int v, int tl, int tr, int[][] xy) {
  128.             if (tl + 1 == tr) {
  129.                 t[v] = new Node(xy[tl]);
  130.             } else {
  131.                 int tm = (tl + tr) / 2;
  132.                 build(v * 2 + 1, tl, tm, xy);
  133.                 build(v * 2 + 2, tm, tr, xy);
  134.                 t[v] = new Node(t[v * 2 + 1], t[v * 2 + 2]);
  135.             }
  136.         }
  137.  
  138.         void update(int v, int tl, int tr, int x, int y, int val) {
  139.             if (tl + 1 == tr) {
  140.                 t[v].add(t[v].get_ind(y), val);
  141.             } else {
  142.                 int tm = (tl + tr) / 2;
  143.                 if (x < tm) {
  144.                     update(v * 2 + 1, tl, tm, x, y, val);
  145.                 } else {
  146.                     update(v * 2 + 2, tm, tr, x, y, val);
  147.                 }
  148.                 t[v].add(t[v].get_ind(y), val);
  149.             }
  150.         }
  151.  
  152.         long get(int v, int tl, int tr, int x1, int y1, int x2, int y2) {
  153.             if (tl >= x2 || tr <= x1) return 0;
  154.             if (tl >= x1 && tr <= x2) {
  155.                 return t[v].get(t[v].get_ind(y1), t[v].get_ind(y2));
  156.             } else {
  157.                 int tm = (tl + tr) / 2;
  158.                 return get(v * 2 + 1, tl, tm, x1, y1, x2, y2) +
  159.                         get(v * 2 + 2, tm, tr, x1, y1, x2, y2);
  160.             }
  161.         }
  162.     }
  163.  
  164.     public static void main(String[] args) throws NumberFormatException, IOException {
  165.         new Main().run();
  166.     }
  167.  
  168.     void run() throws NumberFormatException, IOException {
  169.         solve();
  170.         out.close();
  171.     }
  172.  
  173.     BufferedReader in;
  174.     PrintWriter out;
  175.  
  176.     StringTokenizer tok;
  177.     String delim = " ";
  178.  
  179.     Main() throws FileNotFoundException {
  180.         try {
  181.             in = new BufferedReader(new FileReader("input.txt"));
  182.             out = new PrintWriter("output.txt");
  183.         } catch (Exception e) {
  184.             if (fileName.isEmpty()) {
  185.                 in = new BufferedReader(new InputStreamReader(System.in));
  186.                 out = new PrintWriter(System.out);
  187.             } else {
  188.                 in = new BufferedReader(new FileReader(fileName + ".in"));
  189.                 out = new PrintWriter(fileName + ".out");
  190.             }
  191.  
  192.         }
  193.         tok = new StringTokenizer("");
  194.     }
  195.  
  196.     String readLine() throws IOException {
  197.         return in.readLine();
  198.     }
  199.  
  200.     String readString() throws IOException {
  201.         while (!tok.hasMoreTokens()) {
  202.             String nextLine = readLine();
  203.             if (null == nextLine) {
  204.                 return null;
  205.             }
  206.  
  207.             tok = new StringTokenizer(nextLine);
  208.         }
  209.         return tok.nextToken(delim);
  210.     }
  211.  
  212.     int readInt() throws NumberFormatException, IOException {
  213.         return Integer.parseInt(readString());
  214.     }
  215.  
  216.     long readLong() throws NumberFormatException, IOException {
  217.         return Long.parseLong(readString());
  218.     }
  219.  
  220.     int[] readIntArray(int n) throws NumberFormatException, IOException {
  221.         int[] a = new int[n];
  222.         for (int i = 0; i < n; ++i) {
  223.             a[i] = readInt();
  224.         }
  225.         return a;
  226.     }
  227.  
  228.     double readDouble() throws NumberFormatException, IOException {
  229.         return Double.parseDouble(readString());
  230.     }
  231.  
  232.     void sortIntArray(int[] a) {
  233.         Integer[] arr = new Integer[a.length];
  234.         for (int i = 0; i < a.length; i++) {
  235.             arr[i] = a[i];
  236.         }
  237.         Arrays.sort(arr);
  238.         for (int i = 0; i < a.length; i++) {
  239.             a[i] = arr[i];
  240.         }
  241.     }
  242.  
  243.  
  244. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement