CompetitiveProgramming/codeforces/100490/E.cpp at master · phonglnDEV/CompetitiveProgramming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;

struct SegmentTree
{
  int low, mid, high, value;
  SegmentTree *l, *r;

  SegmentTree(int low, int high): low(low), high(high)
  {
    mid = (low + high) / 2;
    value = 0;
    l = r = NULL;
  }

  void add(int x)
  {
    value++;
    if (low == high)
      return;
    if (x <= mid)
    {
      if (!l)
        l = new SegmentTree(low, mid);
      l -> add(x);
    }
    else
    {
      if (!r)
        r = new SegmentTree(mid + 1, high);
      r -> add(x);
    }
  }

  int get(int x, int y)
  {
    if (low == x && high == y)
      return value;
    int u = x <= mid && l ? l -> get(x, min(y, mid)) : 0;
    int v = mid < y && r ? r -> get(max(x, mid + 1), y) : 0;
    return u + v;
  }
};

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  freopen("environment.in", "r", stdin);
  freopen("environment.out", "w", stdout);
  int d = 0, type, x, y, n;
  cin >> n;
  SegmentTree *lTree = new SegmentTree(0, 1000000000);
  SegmentTree *rTree = new SegmentTree(0, 1000000000);
  while (n--)
  {
    cin >> type >> x;
    if (type == 1)
    {
      cin >> y;
      lTree -> add(x + d);
      rTree -> add(y + d);
    }
    else
    {
      d = lTree -> get(0, x);
      if (x)
        d -= rTree -> get(0, x - 1);
      cout << d << '\n';
    }
  }
}