# Untitled

a guest
Sep 15th, 2019
116
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2. #define MAX 1000005
3. #define MVAL 1000000005
4. #define mid (i+j)/2
5. #define F(i, n) for(int i = 1; i <= n; i++)
6. using namespace std;
7.
8. int n, q, arr[MAX], a, b, v, curNode=1, vs[MAX];
9. vector<int> le, ri, sum;
10.
11. int createnode(int soma) {
12. cout << ri[1] << "\n";
13. curNode++;
14. le.push_back(-1);
15. ri.push_back(-1);
16. sum.push_back(soma);
17. cout << curNode << " | " << ri[1] << "\n";
18. return curNode;
19. }
20.
21. int createnode(int idl, int idr) {
22. curNode++;
23. le.push_back(idl);
24. ri.push_back(idr);
25. sum.push_back(sum[idl] + sum[idr]);
26. return curNode;
27. }
28.
29. void emergency_son(int node) {
30. while ((int)le.size() - 1 < node) le.push_back(-1);
31. while ((int)ri.size() - 1 < node) ri.push_back(-1);
32. cout << "ES " << node << " " << le[node] << " " << ri[node] << " | " << (ri[node] == -1) << "\n";
33. cout << "The left was " << le[node] << "\n";
34. if (le[node] == -1) {int var = createnode(0); le[node] = var;}
35. cout << "The right is " << ri[node] << " and the node is " << node << " but at one it is " << ri[1] << "\n";
36. if (ri[node] == -1) {cout << "hello?\n"; ri[node] = createnode(0);}
37. cout << "EES " << node << "\n";
38. }
39.
40. int update(int node, int i, int j, int ind, int v) {
41. emergency_son(node);
42. cout << node << " " << i << " " << j << " " << ind << " " << v << " |> ";
43. cout << le[node] << " " << ri[node] << "\n";
44. if (ind < i || ind > j) return createnode(0);
45. else if (i == j) return createnode(1+sum[node]);
46. else if (mid + 1 <= ind) return createnode(le[node], update(ri[node], mid+1, j, ind, v));
47. else return createnode(update(le[node], i, mid, ind, v), ri[node]);
48. }
49.
50. int query(int node, int i, int j, int ind) {
51. emergency_son(node);
52. if (i > ind) return 0;
53. else if (j <= ind) return sum[node];
54. else if (ind >= mid + 1) return sum[le[node]] + query(ri[node], mid+1, j, ind);
55. else return query(le[node], i, mid, ind);
56. }
57.
58. int main() {
59. cin >> n >> q;
60. le.push_back(-1); ri.push_back(-1); sum.push_back(-1);
61. F(i, n) {
62. cin >> arr[i];
63. if (i > 1) vs[i] = update(vs[i-1], 1, MVAL, arr[i], 1);
64. else vs[1] = update(1, 1, MVAL, arr[i], 1);
65. cout << "resisti\n";
66. }
67. F(i, q) {
68. cin >> a >> b >> v;
69. cout << query(vs[b], 1, MVAL, v) - query(vs[a-1], 1, MVAL, v) << "\n";
70. }
71. }
RAW Paste Data