SHARE
TWEET

Untitled

a guest Sep 15th, 2019 110 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top