Advertisement
Guest User

Untitled

a guest
Jul 31st, 2015
221
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.34 KB | None | 0 0
  1. import java.io.OutputStream;
  2. import java.io.FileOutputStream;
  3. import java.io.IOException;
  4. import java.io.FileInputStream;
  5. import java.io.InputStream;
  6. import java.io.OutputStream;
  7. import java.io.PrintWriter;
  8. import java.io.BufferedWriter;
  9. import java.io.Writer;
  10. import java.io.OutputStreamWriter;
  11. import java.util.InputMismatchException;
  12. import java.io.IOException;
  13. import java.io.InputStream;
  14.  
  15. /**
  16. * Built using CHelper plug-in
  17. * Actual solution is at the top
  18. *
  19. * @author Hippskill (Hippskill@gmail.com)
  20. */
  21. public class Main {
  22. public static void main(String[] args) {
  23. InputStream inputStream;
  24. try {
  25. inputStream = new FileInputStream("sum.in");
  26. } catch (IOException e) {
  27. throw new RuntimeException(e);
  28. }
  29. OutputStream outputStream;
  30. try {
  31. outputStream = new FileOutputStream("sum.out");
  32. } catch (IOException e) {
  33. throw new RuntimeException(e);
  34. }
  35. InputReader in = new InputReader(inputStream);
  36. OutputWriter out = new OutputWriter(outputStream);
  37. Task solver = new Task();
  38. solver.solve(1, in, out);
  39. out.close();
  40. }
  41.  
  42. static class Task {
  43. long[][] tree;
  44.  
  45. public void init(long[] a) {
  46. tree = new long[a.length * 4][2];
  47. for (int i = 0; i < a.length * 4; i++) {
  48. tree[i][1] = -1;
  49. }
  50. build_tree(a, 1, 0, a.length - 1);
  51. }
  52.  
  53. public void build_tree(long[] a, int v, int tl, int tr) {
  54. if (tl == tr)
  55. tree[v][0] = a[tl];
  56. else {
  57. int mid = (tl + tr) >> 1;
  58. build_tree(a, v * 2, tl, mid);
  59. build_tree(a, v * 2 + 1, mid + 1, tr);
  60. tree[v][0] = tree[v * 2][0] + tree[v * 2 + 1][0];
  61. }
  62. }
  63.  
  64. public void push(int v) {
  65. if (tree[v][1] != -1) {
  66. tree[v * 2][1] = tree[v * 2 + 1][1] = tree[v][1];
  67. tree[v][1] = -1;
  68. }
  69. }
  70.  
  71. public void update(int v, int tl, int tr, int l, int r, long value) {
  72. if (l > r)
  73. return;
  74. if (tl == l && tr == r) {
  75. tree[v][1] = value;
  76. } else {
  77. int mid = (tl + tr) >> 1;
  78. push(v);
  79. update(2 * v, tl, mid, l, Math.min(r, mid), value);
  80. update(2 * v + 1, mid + 1, tr, Math.max(l, mid + 1), r, value);
  81. }
  82. }
  83.  
  84. public long get_sum(int v, int tl, int tr, int l, int r) {
  85. if (l > r)
  86. return 0;
  87. if (tl == tr) {
  88. if (tree[v][1] != -1) {
  89. tree[v][0] = tree[v][1];
  90. tree[v][1] = -1;
  91. }
  92. return tree[v][0];
  93. } else {
  94. push(v);
  95. int mid = (tl + tr) >> 1;
  96. 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);
  97. if (tree[v][1] != -1)
  98. tree[v][0] = tree[v][1] * (r - l);
  99. else
  100. tree[v][0] = tree[2 * v][0] + tree[2 * v + 1][0];
  101. return ans;
  102. }
  103. }
  104.  
  105. public void solve(int testNumber, InputReader in, OutputWriter out) {
  106. int n = in.readInt(), q = in.readInt();
  107. long[] a = new long[n];
  108. init(a);
  109. for (int i = 0; i < q; i++) {
  110. if (in.readCharacter() == 'A') {
  111. int l = in.readInt() - 1, r = in.readInt() - 1;
  112. long value = in.readLong();
  113. update(1, 0, n - 1, l, r, value);
  114. } else {
  115. int l = in.readInt() - 1, r = in.readInt() - 1;
  116. out.printLine(get_sum(1, 0, n, l, r));
  117. }
  118. }
  119. }
  120.  
  121. }
  122.  
  123. static class InputReader {
  124. private InputStream stream;
  125. private byte[] buf = new byte[1024];
  126. private int curChar;
  127. private int numChars;
  128. private InputReader.SpaceCharFilter filter;
  129.  
  130. public InputReader(InputStream stream) {
  131. this.stream = stream;
  132. }
  133.  
  134. public int read() {
  135. if (numChars == -1)
  136. throw new InputMismatchException();
  137. if (curChar >= numChars) {
  138. curChar = 0;
  139. try {
  140. numChars = stream.read(buf);
  141. } catch (IOException e) {
  142. throw new InputMismatchException();
  143. }
  144. if (numChars <= 0)
  145. return -1;
  146. }
  147. return buf[curChar++];
  148. }
  149.  
  150. public int readInt() {
  151. int c = read();
  152. while (isSpaceChar(c))
  153. c = read();
  154. int sgn = 1;
  155. if (c == '-') {
  156. sgn = -1;
  157. c = read();
  158. }
  159. int res = 0;
  160. do {
  161. if (c < '0' || c > '9')
  162. throw new InputMismatchException();
  163. res *= 10;
  164. res += c - '0';
  165. c = read();
  166. } while (!isSpaceChar(c));
  167. return res * sgn;
  168. }
  169.  
  170. public long readLong() {
  171. int c = read();
  172. while (isSpaceChar(c))
  173. c = read();
  174. int sgn = 1;
  175. if (c == '-') {
  176. sgn = -1;
  177. c = read();
  178. }
  179. long res = 0;
  180. do {
  181. if (c < '0' || c > '9')
  182. throw new InputMismatchException();
  183. res *= 10;
  184. res += c - '0';
  185. c = read();
  186. } while (!isSpaceChar(c));
  187. return res * sgn;
  188. }
  189.  
  190. public boolean isSpaceChar(int c) {
  191. if (filter != null)
  192. return filter.isSpaceChar(c);
  193. return isWhitespace(c);
  194. }
  195.  
  196. public static boolean isWhitespace(int c) {
  197. return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  198. }
  199.  
  200. public char readCharacter() {
  201. int c = read();
  202. while (isSpaceChar(c))
  203. c = read();
  204. return (char) c;
  205. }
  206.  
  207. public interface SpaceCharFilter {
  208. public boolean isSpaceChar(int ch);
  209.  
  210. }
  211.  
  212. }
  213.  
  214. static class OutputWriter {
  215. private final PrintWriter writer;
  216.  
  217. public OutputWriter(OutputStream outputStream) {
  218. writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  219. }
  220.  
  221. public OutputWriter(Writer writer) {
  222. this.writer = new PrintWriter(writer);
  223. }
  224.  
  225. public void close() {
  226. writer.close();
  227. }
  228.  
  229. public void printLine(long i) {
  230. writer.println(i);
  231. }
  232.  
  233. }
  234. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement