Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.OutputStream;
- import java.io.IOException;
- import java.io.InputStream;
- import java.io.OutputStream;
- import java.io.PrintWriter;
- import java.util.PriorityQueue;
- import java.io.BufferedWriter;
- import java.util.InputMismatchException;
- import java.io.IOException;
- import java.util.ArrayList;
- import java.util.AbstractCollection;
- import java.io.Writer;
- import java.io.OutputStreamWriter;
- import java.util.Collections;
- import java.io.InputStream;
- /**
- * Built using CHelper plug-in
- * Actual solution is at the top
- *
- * @author ilyakor
- */
- public class Main {
- public static void main(String[] args) {
- InputStream inputStream = System.in;
- OutputStream outputStream = System.out;
- InputReader in = new InputReader(inputStream);
- OutputWriter out = new OutputWriter(outputStream);
- TaskE solver = new TaskE();
- solver.solve(1, in, out);
- out.close();
- }
- static class TaskE {
- public void solve(int testNumber, InputReader in, OutputWriter out) {
- int n = in.nextInt();
- int m = in.nextInt();
- ArrayList<ii> entries = new ArrayList<>();
- for (int i = 0; i < n; ++i) {
- entries.add(new ii(in.nextInt(), i));
- }
- SegmentTreeFastIntervalAddSum tree = new SegmentTreeFastIntervalAddSum(1 << 18);
- for (ii entry : entries) if (entry.first == 1) tree.set(entry.second + 1, 1);
- Collections.shuffle(entries);
- Collections.sort(entries);
- PriorityQueue<TaskE.Query> qu = new PriorityQueue<>();
- long[] ans = new long[m];
- for (int i = 0; i < m; ++i) {
- TaskE.Query q = new TaskE.Query(in.nextInt() - 1, in.nextInt() - 1);
- q.ind = i;
- q.sum = tree.querySum(q.l + 1, q.r + 1);
- if (q.sum == 0) {
- ans[i] = 1;
- } else {
- qu.add(q);
- }
- }
- for (ii entry : entries) {
- int x = entry.first, ind = entry.second;
- if (x <= 1) continue;
- while (!qu.isEmpty() && qu.peek().sum < x - 1) {
- TaskE.Query q = qu.poll();
- q.sum = tree.querySum(q.l + 1, q.r + 1);
- if (q.sum >= x - 1) {
- qu.add(q);
- } else {
- ans[q.ind] = q.sum + 1;
- }
- }
- tree.set(ind + 1, x);
- }
- while (!qu.isEmpty()) {
- TaskE.Query q = qu.poll();
- q.sum = tree.querySum(q.l + 1, q.r + 1);
- ans[q.ind] = q.sum + 1;
- }
- for (int i = 0; i < m; ++i)
- out.printLine(ans[i]);
- }
- static class Query implements Comparable<TaskE.Query> {
- int l;
- int r;
- int ind;
- long sum;
- public Query(int l, int r) {
- if (l > r) {
- int t = l;
- l = r;
- r = t;
- }
- this.l = l;
- this.r = r;
- sum = 0;
- }
- public int compareTo(TaskE.Query o) {
- return Long.compare(sum, o.sum);
- }
- }
- }
- static class ii implements Comparable<ii> {
- public int first;
- public int second;
- public ii() {
- }
- public ii(int first, int second) {
- this.first = first;
- this.second = second;
- }
- public boolean equals(Object o) {
- if (this == o) return true;
- if (o == null || getClass() != o.getClass()) return false;
- ii ii = (ii) o;
- if (first != ii.first) return false;
- if (second != ii.second) return false;
- return true;
- }
- public int hashCode() {
- int result = first;
- result = 31 * result + second;
- return result;
- }
- public int compareTo(ii o) {
- if (first != o.first) {
- return first < o.first ? -1 : 1;
- }
- if (second != o.second) {
- return second < o.second ? -1 : 1;
- }
- return 0;
- }
- public String toString() {
- return "{" +
- "first=" + first +
- ", second=" + second +
- '}';
- }
- }
- static class OutputWriter {
- private final PrintWriter writer;
- public OutputWriter(OutputStream outputStream) {
- writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
- }
- public OutputWriter(Writer writer) {
- this.writer = new PrintWriter(writer);
- }
- public void print(Object... objects) {
- for (int i = 0; i < objects.length; i++) {
- if (i != 0) {
- writer.print(' ');
- }
- writer.print(objects[i]);
- }
- }
- public void printLine(Object... objects) {
- print(objects);
- writer.println();
- }
- public void close() {
- writer.close();
- }
- }
- static class SegmentTreeFastIntervalAddSum {
- final int n;
- final long[] t;
- final long[] m;
- final boolean[] h;
- final long[] q;
- public SegmentTreeFastIntervalAddSum(int n) {
- this.n = n;
- t = new long[2 * n];
- m = new long[2 * n];
- h = new boolean[2 * n];
- q = new long[2 * n];
- for (int i = n; i < 2 * n; i++)
- q[i] = 1;
- for (int i = 2 * n - 1; i > 1; i -= 2)
- q[i >> 1] = q[i] + q[i ^ 1];
- }
- void modifierHelper(int i, long p) {
- t[i] += p * q[i];
- m[i] += p;
- h[i] = true;
- }
- void pop(int i) {
- if (h[i >> 1]) {
- t[i >> 1] = t[i] + t[i ^ 1] + m[i >> 1] * q[i >> 1];
- } else {
- t[i >> 1] = t[i] + t[i ^ 1];
- }
- }
- void popUp(int i) {
- for (; i > 1; i >>= 1)
- pop(i);
- }
- void push(int i) {
- if (h[i >> 1]) {
- modifierHelper(i, m[i >> 1]);
- modifierHelper(i ^ 1, m[i >> 1]);
- h[i >> 1] = false;
- m[i >> 1] = 0;
- }
- }
- void pushDown(int i) {
- int k;
- for (k = 0; (i >> k) > 0; k++)
- ;
- for (k -= 2; k >= 0; k--)
- push(i >> k);
- }
- public void modifyAdd(int a, int b, long v) {
- a += n;
- b += n;
- pushDown(a);
- pushDown(b);
- int ta = a;
- int tb = b;
- for (; a <= b; a = (a + 1) >> 1, b = (b - 1) >> 1) {
- if ((a & 1) != 0)
- modifierHelper(a, v);
- if ((b & 1) == 0)
- modifierHelper(b, v);
- }
- popUp(ta);
- popUp(tb);
- }
- public long querySum(int a, int b) {
- a += n;
- b += n;
- pushDown(a);
- pushDown(b);
- long res = 0;
- for (; a <= b; a = (a + 1) >> 1, b = (b - 1) >> 1) {
- if ((a & 1) != 0)
- res += t[a];
- if ((b & 1) == 0)
- res += t[b];
- }
- return res;
- }
- public void set(int i, long v) {
- modifyAdd(i, i, -querySum(i, i) + v);
- }
- }
- static class InputReader {
- private InputStream stream;
- private byte[] buffer = new byte[10000];
- private int cur;
- private int count;
- public InputReader(InputStream stream) {
- this.stream = stream;
- }
- public static boolean isSpace(int c) {
- return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
- }
- public int read() {
- if (count == -1) {
- throw new InputMismatchException();
- }
- try {
- if (cur >= count) {
- cur = 0;
- count = stream.read(buffer);
- if (count <= 0)
- return -1;
- }
- } catch (IOException e) {
- throw new InputMismatchException();
- }
- return buffer[cur++];
- }
- public int readSkipSpace() {
- int c;
- do {
- c = read();
- } while (isSpace(c));
- return c;
- }
- public int nextInt() {
- int sgn = 1;
- int c = readSkipSpace();
- if (c == '-') {
- sgn = -1;
- c = read();
- }
- int res = 0;
- do {
- if (c < '0' || c > '9') {
- throw new InputMismatchException();
- }
- res = res * 10 + c - '0';
- c = read();
- } while (!isSpace(c));
- res *= sgn;
- return res;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement