fork download 
  1. import java.io.*;
  2. import java.util.*;
  3. class horrible_queries
  4. {
  5. 	static FasterScanner sc=new FasterScanner(System.in);
  6. 	static PrintWriter out=new PrintWriter(System.out);
  7. 	static long[] tree,lazy;
  8.  
  9. 	static void build(int node,int l,int r)
  10. 	{
  11. 		if(l>r)
  12. 		{
  13. 			return;
  14. 		}
  15. 		if(l==r)
  16. 		{
  17. 			tree[node]=0;
  18. 		}
  19. 		else
  20. 		{
  21. 			int mid=(l+r)/2;
  22. 			build(2*node,l,mid);
  23. 			build((2*node)+1,mid+1,r);
  24. 			tree[node]=tree[2*node]+tree[(2*node)+1];
  25. 		}
  26. 	}
  27.  
  28. 	static long getSum(int node,int s,int e,int l,int r)
  29. 	{
  30. 		if(lazy[node]!=0)
  31. 		{
  32. 			tree[node]+=(e-s+1)*lazy[node];
  33. 			if(s!=e)
  34. 			{
  35. 				lazy[2*node]+=lazy[node];
  36. 				lazy[(2*node)+1]+=lazy[node];
  37. 			}
  38. 			lazy[node]=0;
  39. 		}
  40. 		if(s>e || l>e || r<s)
  41. 		{
  42. 			return 0;
  43. 		}
  44. 		if(l<=s && r>=e)
  45. 		{
  46. 			return tree[node];
  47. 		}
  48. 		else
  49. 		{
  50. 			int mid=(s+e)/2;
  51. 			long q1=getSum(2*node,s,mid,l,r);
  52. 			long q2=getSum((2*node)+1,mid+1,e,l,r);
  53. 			return q1+q2;
  54. 		}
  55. 	}
  56.  
  57. 	static void update(int node,int s,int e,int l,int r,long val)
  58. 	{
  59. 		if(lazy[node]!=0)
  60. 		{
  61. 			tree[node]+=(e-s+1)*lazy[node];
  62. 			if(s!=e)
  63. 			{
  64. 				lazy[2*node]+=lazy[node];
  65. 				lazy[(2*node)+1]+=lazy[node];
  66. 			}
  67. 			lazy[node]=0;
  68. 		}
  69. 		if(s>e || l>e || r<s)
  70. 		{
  71. 			return;
  72. 		}
  73. 		if(l<=s && r>=e)
  74. 		{
  75. 			tree[node]+=(e-s+1)*val;
  76. 			if(s!=e)
  77. 			{
  78. 				lazy[2*node]+=val;
  79. 				lazy[(2*node)+1]+=val;
  80. 			}
  81. 		}
  82. 		else
  83. 		{
  84. 			int mid=(s+e)/2;
  85. 			update(2*node,s,mid,l,r,val);
  86. 			update((2*node)+1,mid+1,e,l,r,val);
  87. 			tree[node]=tree[2*node]+tree[(2*node)+1];
  88. 		}
  89. 	}
  90.  
  91. 	public static void main(String args[]) throws Exception
  92. 	{
  93. 		int t=sc.nextInt();
  94. 		while(t>0)
  95. 		{
  96. 			int n=sc.nextInt();
  97. 			int q=sc.nextInt();
  98. 			tree=new long[4*n];
  99. 			lazy=new long[4*n];
  100. 			build(1,0,n-1);
  101. 			while(q>0)
  102. 			{
  103. 				int op=sc.nextInt();
  104. 				int l=sc.nextInt()-1;
  105. 				int r=sc.nextInt()-1;
  106. 				if(op==0)
  107. 				{
  108. 					long val=sc.nextLong();
  109. 					update(1,0,n-1,l,r,val);
  110. 				}
  111. 				else
  112. 				{
  113. 					long ans=getSum(1,0,n-1,l,r);
  114. 					System.out.println(ans);
  115. 				}
  116. 				q--;
  117. 			}
  118. 			t--;
  119. 		}
  120. 		out.close();
  121. 	}
  122. }
  123. class FasterScanner 
  124. {
  125. 	private InputStream mIs;
  126. 	private byte[] buf = new byte[1024];
  127. 	private int curChar;
  128. 	private int numChars;
  129.  
  130. 	public FasterScanner() {
  131. 		this(System.in);
  132. 	}
  133.  
  134. 	public FasterScanner(InputStream is) {
  135. 		mIs = is;
  136. 	}
  137.  
  138. 	public int read() {
  139. 		if (numChars == -1)
  140. 			throw new InputMismatchException();
  141. 		if (curChar >= numChars) {
  142. 			curChar = 0;
  143. 			try {
  144. 				numChars = mIs.read(buf);
  145. 			} catch (IOException e) {
  146. 				throw new InputMismatchException();
  147. 			}
  148. 			if (numChars <= 0)
  149. 				return -1;
  150. 		}
  151. 		return buf[curChar++];
  152. 	}
  153.  
  154. 	public String nextLine() {
  155. 		int c = read();
  156. 		while (isSpaceChar(c))
  157. 			c = read();
  158. 		StringBuilder res = new StringBuilder();
  159. 		do {
  160. 			res.appendCodePoint(c);
  161. 			c = read();
  162. 		} while (!isEndOfLine(c));
  163. 		return res.toString();
  164. 	}
  165.  
  166. 	public String next() {
  167. 		int c = read();
  168. 		while (isSpaceChar(c))
  169. 			c = read();
  170. 		StringBuilder res = new StringBuilder();
  171. 		do {
  172. 			res.appendCodePoint(c);
  173. 			c = read();
  174. 		} while (!isSpaceChar(c));
  175. 		return res.toString();
  176. 	}
  177.  
  178. 	public long nextLong() {
  179. 		int c = read();
  180. 		while (isSpaceChar(c))
  181. 			c = read();
  182. 		int sgn = 1;
  183. 		if (c == '-') {
  184. 			sgn = -1;
  185. 			c = read();
  186. 		}
  187. 		long res = 0;
  188. 		do {
  189. 			if (c < '0' || c > '9')
  190. 				throw new InputMismatchException();
  191. 			res *= 10;
  192. 			res += c - '0';
  193. 			c = read();
  194. 		} while (!isSpaceChar(c));
  195. 		return res * sgn;
  196. 	}
  197.  
  198. 	public int nextInt() {
  199. 		int c = read();
  200. 		while (isSpaceChar(c))
  201. 			c = read();
  202. 		int sgn = 1;
  203. 		if (c == '-') {
  204. 			sgn = -1;
  205. 			c = read();
  206. 		}
  207. 		int res = 0;
  208. 		do {
  209. 			if (c < '0' || c > '9')
  210. 				throw new InputMismatchException();
  211. 			res *= 10;
  212. 			res += c - '0';
  213. 			c = read();
  214. 		} while (!isSpaceChar(c));
  215. 		return res * sgn;
  216. 	}
  217.  
  218. 	public boolean isSpaceChar(int c) {
  219. 		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  220. 	}
  221.  
  222. 	public boolean isEndOfLine(int c) {
  223. 		return c == '\n' || c == '\r' || c == -1;
  224. 	}
  225.  
  226. }
Runtime error #stdin #stdout #stderr 0.1s 320576KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
Exception in thread "main" java.util.InputMismatchException
	at FasterScanner.read(Main.java:140)
	at FasterScanner.nextInt(Main.java:201)
	at horrible_queries.main(Main.java:93)
https://ideone.com/w48jeU
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!