Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.OutputStream;
- import java.io.FileOutputStream;
- import java.io.IOException;
- import java.io.FileInputStream;
- import java.io.InputStream;
- import java.io.OutputStream;
- import java.io.PrintWriter;
- import java.io.BufferedWriter;
- import java.io.Writer;
- import java.io.OutputStreamWriter;
- import java.util.InputMismatchException;
- import java.io.IOException;
- import java.io.InputStream;
- /**
- * Built using CHelper plug-in
- * Actual solution is at the top
- *
- * @author Hippskill (Hippskill@gmail.com)
- */
- public class Main {
- public static void main(String[] args) {
- InputStream inputStream;
- try {
- inputStream = new FileInputStream("sum.in");
- } catch (IOException e) {
- throw new RuntimeException(e);
- }
- OutputStream outputStream;
- try {
- outputStream = new FileOutputStream("sum.out");
- } catch (IOException e) {
- throw new RuntimeException(e);
- }
- InputReader in = new InputReader(inputStream);
- OutputWriter out = new OutputWriter(outputStream);
- Task solver = new Task();
- solver.solve(1, in, out);
- out.close();
- }
- static class Task {
- long[][] tree;
- public void init(long[] a) {
- tree = new long[a.length * 4][2];
- for (int i = 0; i < a.length * 4; i++) {
- tree[i][1] = -1;
- }
- build_tree(a, 1, 0, a.length - 1);
- }
- public void build_tree(long[] a, int v, int tl, int tr) {
- if (tl == tr)
- tree[v][0] = a[tl];
- else {
- int mid = (tl + tr) >> 1;
- build_tree(a, v * 2, tl, mid);
- build_tree(a, v * 2 + 1, mid + 1, tr);
- tree[v][0] = tree[v * 2][0] + tree[v * 2 + 1][0];
- }
- }
- public void push(int v) {
- if (tree[v][1] != -1) {
- tree[v * 2][1] = tree[v * 2 + 1][1] = tree[v][1];
- tree[v][1] = -1;
- }
- }
- public void update(int v, int tl, int tr, int l, int r, long value) {
- if (l > r)
- return;
- if (tl == l && tr == r) {
- tree[v][1] = value;
- } else {
- int mid = (tl + tr) >> 1;
- push(v);
- update(2 * v, tl, mid, l, Math.min(r, mid), value);
- update(2 * v + 1, mid + 1, tr, Math.max(l, mid + 1), r, value);
- }
- }
- public long get_sum(int v, int tl, int tr, int l, int r) {
- if (l > r)
- return 0;
- if (tl == tr) {
- if (tree[v][1] != -1) {
- tree[v][0] = tree[v][1];
- tree[v][1] = -1;
- }
- return tree[v][0];
- } else {
- push(v);
- int mid = (tl + tr) >> 1;
- long ans = get_sum(2 * v, tl, mid, l, Math.min(r, mid)) + get_sum(2 * v + 1, mid + 1, tr, Math.max(l, mid + 1), r);
- if (tree[v][1] != -1)
- tree[v][0] = tree[v][1] * (r - l);
- else
- tree[v][0] = tree[2 * v][0] + tree[2 * v + 1][0];
- return ans;
- }
- }
- public void solve(int testNumber, InputReader in, OutputWriter out) {
- int n = in.readInt(), q = in.readInt();
- long[] a = new long[n];
- init(a);
- for (int i = 0; i < q; i++) {
- if (in.readCharacter() == 'A') {
- int l = in.readInt() - 1, r = in.readInt() - 1;
- long value = in.readLong();
- update(1, 0, n - 1, l, r, value);
- } else {
- int l = in.readInt() - 1, r = in.readInt() - 1;
- out.printLine(get_sum(1, 0, n, l, r));
- }
- }
- }
- }
- static class InputReader {
- private InputStream stream;
- private byte[] buf = new byte[1024];
- private int curChar;
- private int numChars;
- private InputReader.SpaceCharFilter filter;
- public InputReader(InputStream stream) {
- this.stream = stream;
- }
- public int read() {
- if (numChars == -1)
- throw new InputMismatchException();
- if (curChar >= numChars) {
- curChar = 0;
- try {
- numChars = stream.read(buf);
- } catch (IOException e) {
- throw new InputMismatchException();
- }
- if (numChars <= 0)
- return -1;
- }
- return buf[curChar++];
- }
- public int readInt() {
- int c = read();
- while (isSpaceChar(c))
- c = read();
- int sgn = 1;
- if (c == '-') {
- sgn = -1;
- c = read();
- }
- int res = 0;
- do {
- if (c < '0' || c > '9')
- throw new InputMismatchException();
- res *= 10;
- res += c - '0';
- c = read();
- } while (!isSpaceChar(c));
- return res * sgn;
- }
- public long readLong() {
- int c = read();
- while (isSpaceChar(c))
- c = read();
- int sgn = 1;
- if (c == '-') {
- sgn = -1;
- c = read();
- }
- long res = 0;
- do {
- if (c < '0' || c > '9')
- throw new InputMismatchException();
- res *= 10;
- res += c - '0';
- c = read();
- } while (!isSpaceChar(c));
- return res * sgn;
- }
- public boolean isSpaceChar(int c) {
- if (filter != null)
- return filter.isSpaceChar(c);
- return isWhitespace(c);
- }
- public static boolean isWhitespace(int c) {
- return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
- }
- public char readCharacter() {
- int c = read();
- while (isSpaceChar(c))
- c = read();
- return (char) c;
- }
- public interface SpaceCharFilter {
- public boolean isSpaceChar(int ch);
- }
- }
- 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 close() {
- writer.close();
- }
- public void printLine(long i) {
- writer.println(i);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement