Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class Main {
- String fileName = "";
- void solve() throws IOException {
- int n = readInt();
- }
- class FenwickTree {
- long[] t;
- int n;
- FenwickTree(int n) {
- this.n = n;
- t = new long[n];
- }
- void add(int i, int val) {
- while (i < n) {
- t[i] += val;
- i = (i + 1) | i;
- }
- }
- long get(int i) {
- long ans = 0;
- while (i >= 0) {
- ans += t[i];
- i = (i & (i + 1)) - 1;
- }
- return ans;
- }
- long get(int l, int r) {
- return get(r) - (l > 0 ? get(l - 1) : 0);
- }
- }
- int[] buffer = new int[1 << 20];
- int[] merger(int[] a, int[] b) {
- int itr1 = 0;
- int itr2 = 0;
- while (itr1 < a.length && itr2 < b.length) {
- if (a[itr1] < b[itr2]) {
- buffer[itr1 + itr2] = a[itr1++];
- } else {
- buffer[itr1 + itr2] = b[itr2++];
- }
- }
- while (itr1 < a.length) {
- buffer[itr1 + itr2] = a[itr1++];
- }
- while (itr2 < b.length) {
- buffer[itr1 + itr2] = b[itr2++];
- }
- int size = 0;
- int prev = Integer.MIN_VALUE;
- for (int i = 0; i < itr1 + itr2; i++) {
- if (prev == buffer[i]) {
- continue;
- } else {
- buffer[size++] = buffer[i];
- }
- }
- int[] ans = new int[size];
- for (int i = 0; i < size; i++) {
- ans[i] = buffer[i];
- }
- return ans;
- }
- class Node {
- int[] y;
- int n;
- FenwickTree t;
- int get_ind(int val) {
- int left = 0;
- int right = this.y.length - 1;
- int mid;
- int ans = -1;
- while (left <= right) {
- mid = (left + right) / 2;
- if (this.y[mid] <= val) {
- ans = mid;
- left = mid + 1;
- } else {
- right = mid - 1;
- }
- }
- return ans;
- }
- Node(int[] y) {
- this.y = y;
- this.n = this.y.length;
- this.t = new FenwickTree(this.n);
- }
- Node(Node l, Node r) {
- this.y = merger(l.y, r.y);
- this.n = this.y.length;
- this.t = new FenwickTree(this.n);
- }
- void add(int i, int val) {
- this.t.add(i, val);
- }
- long get(int l, int r) {
- return this.t.get(l, r);
- }
- }
- class SegmentTree {
- Node[] t;
- SegmentTree(int[][] xy) {
- this.t = new Node[xy.length];
- build(0, 0, xy.length, xy);
- }
- void build(int v, int tl, int tr, int[][] xy) {
- if (tl + 1 == tr) {
- t[v] = new Node(xy[tl]);
- } else {
- int tm = (tl + tr) / 2;
- build(v * 2 + 1, tl, tm, xy);
- build(v * 2 + 2, tm, tr, xy);
- t[v] = new Node(t[v * 2 + 1], t[v * 2 + 2]);
- }
- }
- void update(int v, int tl, int tr, int x, int y, int val) {
- if (tl + 1 == tr) {
- t[v].add(t[v].get_ind(y), val);
- } else {
- int tm = (tl + tr) / 2;
- if (x < tm) {
- update(v * 2 + 1, tl, tm, x, y, val);
- } else {
- update(v * 2 + 2, tm, tr, x, y, val);
- }
- t[v].add(t[v].get_ind(y), val);
- }
- }
- long get(int v, int tl, int tr, int x1, int y1, int x2, int y2) {
- if (tl >= x2 || tr <= x1) return 0;
- if (tl >= x1 && tr <= x2) {
- return t[v].get(t[v].get_ind(y1), t[v].get_ind(y2));
- } else {
- int tm = (tl + tr) / 2;
- return get(v * 2 + 1, tl, tm, x1, y1, x2, y2) +
- get(v * 2 + 2, tm, tr, x1, y1, x2, y2);
- }
- }
- }
- public static void main(String[] args) throws NumberFormatException, IOException {
- new Main().run();
- }
- void run() throws NumberFormatException, IOException {
- solve();
- out.close();
- }
- BufferedReader in;
- PrintWriter out;
- StringTokenizer tok;
- String delim = " ";
- Main() throws FileNotFoundException {
- try {
- in = new BufferedReader(new FileReader("input.txt"));
- out = new PrintWriter("output.txt");
- } catch (Exception e) {
- if (fileName.isEmpty()) {
- in = new BufferedReader(new InputStreamReader(System.in));
- out = new PrintWriter(System.out);
- } else {
- in = new BufferedReader(new FileReader(fileName + ".in"));
- out = new PrintWriter(fileName + ".out");
- }
- }
- tok = new StringTokenizer("");
- }
- String readLine() throws IOException {
- return in.readLine();
- }
- String readString() throws IOException {
- while (!tok.hasMoreTokens()) {
- String nextLine = readLine();
- if (null == nextLine) {
- return null;
- }
- tok = new StringTokenizer(nextLine);
- }
- return tok.nextToken(delim);
- }
- int readInt() throws NumberFormatException, IOException {
- return Integer.parseInt(readString());
- }
- long readLong() throws NumberFormatException, IOException {
- return Long.parseLong(readString());
- }
- int[] readIntArray(int n) throws NumberFormatException, IOException {
- int[] a = new int[n];
- for (int i = 0; i < n; ++i) {
- a[i] = readInt();
- }
- return a;
- }
- double readDouble() throws NumberFormatException, IOException {
- return Double.parseDouble(readString());
- }
- void sortIntArray(int[] a) {
- Integer[] arr = new Integer[a.length];
- for (int i = 0; i < a.length; i++) {
- arr[i] = a[i];
- }
- Arrays.sort(arr);
- for (int i = 0; i < a.length; i++) {
- a[i] = arr[i];
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement