Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.io.BufferedReader;
- import java.io.OutputStream;
- import java.io.PrintWriter;
- import java.util.Random;
- import java.io.Writer;
- import java.util.StringTokenizer;
- import java.io.InputStream;
- /**
- * Built using CHelper plug-in
- * Actual solution is at the top
- * @author niyaznigmatul
- */
- public class Main {
- public static void main(String[] args) {
- InputStream inputStream = System.in;
- OutputStream outputStream = System.out;
- FastScanner in = new FastScanner(inputStream);
- FastPrinter out = new FastPrinter(outputStream);
- Task2310 solver = new Task2310();
- solver.solve(1, in, out);
- out.close();
- }
- }
- class Task2310 {
- static final int MAXY = 1000000000;
- static final Random rand = new Random(123123L);
- static class Node {
- Node left;
- Node right;
- long sum;
- int x;
- int y;
- Node(int x, int y) {
- this.x = x;
- this.y = y;
- sum = x;
- }
- void collect() {
- sum = x;
- if (left != null) {
- sum += left.sum;
- }
- if (right != null) {
- sum += right.sum;
- }
- }
- }
- static Node merge(Node first, Node second) {
- if (first == null) {
- return second;
- }
- if (second == null) {
- return first;
- }
- Node ret;
- if (first.y > second.y) {
- first.right = merge(first.right, second);
- ret = first;
- } else {
- second.left = merge(first, second.left);
- ret = second;
- }
- ret.collect();
- return ret;
- }
- static Node[] split(Node v, int x) {
- if (v == null) {
- return new Node[2];
- }
- Node[] ret;
- if (v.x <= x) {
- ret = split(v.right, x);
- v.right = ret[0];
- ret[0] = v;
- } else {
- ret = split(v.left, x);
- v.left = ret[1];
- ret[1] = v;
- }
- v.collect();
- return ret;
- }
- static Node add(Node v, int x, int y) {
- if (v == null) {
- return new Node(x, y);
- }
- if (v.y < y) {
- Node[] t = split(v, x);
- Node ret = new Node(x, y);
- ret.left = t[0];
- ret.right = t[1];
- ret.collect();
- return ret;
- }
- if (v.x < x) {
- v.right = add(v.right, x, y);
- } else {
- v.left = add(v.left, x, y);
- }
- v.collect();
- return v;
- }
- static boolean contains(Node v, int x) {
- if (v == null) {
- return false;
- }
- if (v.x == x) {
- return true;
- } else if (v.x < x) {
- return contains(v.right, x);
- } else {
- return contains(v.left, x);
- }
- }
- static Node root;
- static long getSum(int l, int r) {
- if (l > r) {
- return 0;
- }
- Node[] t1 = split(root, r);
- Node[] t2 = split(t1[0], l - 1);
- long ret = t2[1] == null ? 0 : t2[1].sum;
- root = merge(merge(t2[0], t2[1]), t1[1]);
- return ret;
- }
- public void solve(int testNumber, FastScanner in, FastPrinter out) {
- int n = in.nextInt();
- long y = 0;
- for (int i = 0; i < n; i++) {
- if (in.next().equals("+")) {
- int x = in.nextInt();
- x = (int) ((x + y) % MAXY);
- if (!contains(root, x)) {
- root = add(root, x, rand.nextInt());
- }
- y = 0;
- } else {
- int l = in.nextInt();
- int r = in.nextInt();
- y = getSum(l, r);
- out.println(y);
- }
- }
- }
- }
- class FastScanner {
- BufferedReader br;
- StringTokenizer st;
- IOException happened;
- public FastScanner(InputStream is) {
- br = new BufferedReader(new InputStreamReader(is));
- }
- public String next() {
- while (st == null || !st.hasMoreTokens()) {
- try {
- String line = br.readLine();
- st = new StringTokenizer(line);
- } catch (IOException e) {
- happened = e;
- return null;
- }
- }
- return st.nextToken();
- }
- public int nextInt() {
- return Integer.parseInt(next());
- }
- }
- class FastPrinter extends PrintWriter {
- public FastPrinter(OutputStream out) {
- super(out);
- }
- public FastPrinter(Writer out) {
- super(out);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment