Sereja and Ballons
All submissions for this problem are available.
Sereja has n boxes with balloons. Boxes are numbered with integers from 1 to n. The first box contains a balloons, the second- a balloons and so on.
Also Sereja wrote down m pairs of the number (l, r), (l, r), ..., (l[m], r[m]) on a piece of paper. Now Sereja decided to play and began to burst the balloons in the boxes. At every step Sereja bursts one balloon from some box and wants to know : what is the count of the indices i (1 ≤ i ≤ m), that all balloons in the boxes with the indices from l[i] to r[i] are already bursted.
Please, help Sereja.
The first line contains numbers n and m — the number of the boxes and the number of the pair of numbers. The next line contains n integers a, a, ..., a[n].
The following m lines contain m pairs of numbers (l, r), (l, r), ..., (l[m], r[m]).
The next line contains number k — the number of times, when Sereja had his balloon bursted. The next k line contains integers x, x, ..., x[k]. Index of the box, in what Sereja bursted a balloon at the step number i (1 ≤ i ≤ k), is denoted as y[i]., which can be found as: y[i] = x[i] + ans[i - 1], wherein ans = 0, аnd ans[i] (i>0) — is the answer on the problem after ith bursting of the balloons.
For each test case, print k lines — the answers after every steps.
- 1 ≤ n, m ≤ 10^5
- 1 ≤ a[i] ≤ 100000
- 1 ≤ l[i] ≤ r[i] ≤ n
Input: 5 3 1 1 1 1 1 5 5 2 2 1 3 5 4 2 0 2 3 Output: 0 1 1 2 3Update:
You may assume that, y[i] <= n and k <= 100000
|Tags||aug13, bit, fenwick, medium, segment-tree, sereja|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.