Adding intervals asking for sum of special segments

Revision en7, by DeadlyCritic, 2020-04-25 12:04:17

We have an array( $$$a$$$ ) of length $$$n$$$, all the elements are less than or equal to $$$n$$$, then we have to answer $$$q$$$ queries, each will be three numbers $$$x$$$, $$$l$$$, $$$r$$$, then you have to print $$$\displaystyle\sum\limits_{l \le i mod x \le r}a_i$$$, i.e print the sum of all $$$a_i$$$ for $$$1 \le i \le n$$$ and $$$i$$$ mod $$$x$$$ is in range $$$[l \cdot \cdot r]$$$.

$$$0 \le l \le r < x \le n$$$

Then what if we had queries to add a range?

The first query can be changed a little bit, it can be like we have $$$k$$$, $$$x$$$, $$$l$$$, $$$r$$$, then print the same number but with $$$i > k$$$.

$$$0 \le k < n$$$

Please share the solutions.

Tags query, help, problem

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English DeadlyCritic 2020-04-25 12:04:17 55
en6 English DeadlyCritic 2020-04-25 12:01:55 2 Tiny change: ' n$ and $i mod x$ is in r' -> ' n$ and $i$ mod $x$ is in r'
en5 English DeadlyCritic 2020-04-25 12:01:11 8 Tiny change: 'ut with \n\n$i > k$.\n$\le 0 \le k < ' -> 'ut with \n$i > k$.\n\n$0 \le k < '
en4 English DeadlyCritic 2020-04-25 12:00:27 110
en3 English DeadlyCritic 2020-04-25 11:58:28 18 Tiny change: ' $O(n^2+q\radical{q}+q\radical{n})$, how' -> ' $O(n^2+q\sqrt{q}+q\sqrt{n})$, how' (published)
en2 English DeadlyCritic 2020-04-25 11:55:24 0 (saved to drafts)
en1 English DeadlyCritic 2020-04-25 11:54:40 706 Initial revision (published)