1
#include <vector>
2
#include <algorithm>
3
 
4
#define all(x) (x).begin(), (x).end()
5
 
6
// author: @noisegain
7
 
8
using namespace std;
9
 
10
const int K = 1288; // eq sqrt(nlogn) where n = 10^5
11
// because of O(sqrt(n * log(n))) instead of O(sqrt(n) * log(n))
12
 
13
// [L; R) invariant for all type of queries and variables
14
 
15
struct sqrt_decompose {
16
    vector<vector<int>> a;
17
    vector<vector<int>> blocks;
18
    vector<int> promise;
19
    int changes = 0;
20
    int n;
21
 
22
    explicit sqrt_decompose(const vector<int> &init) {
23
        n = init.size();
24
        a.push_back(init);
25
        rebuild();
26
    }
27
 
28
    void rebuild() {
29
        vector<int> init;
30
        init.reserve(n);
31
        for (auto &x : a) {
32
            init.insert(init.end(), x.begin(), x.end());
33
        }
34
        a.clear();
35
        blocks.clear();
36
        changes = 0;
37
        int size = (n + K - 1) / K;
38
        a.resize(size);
39
        blocks.resize(size);
40
        for (int i = 0; i < size; ++i) {
41
            a[i].reserve(K);
42
            blocks[i].reserve(K);
43
        }
44
        promise.resize(size, 0);
45
        for (int i = 0; i < n; ++i) {
46
            a[i / K].push_back(init[i]);
47
            blocks[i / K].push_back(init[i]);
48
        }
49
        for (auto &x : blocks) {
50
            sort(all(x));
51
        }
52
    }
53
 
54
    void apply(int i) {
55
        blocks[i].clear();
56
        for (auto &x : a[i]) {
57
            x += promise[i];
58
            blocks[i].push_back(x);
59
        }
60
        promise[i] = 0;
61
        sort(all(blocks[i]));
62
    }
63
 
64
    void erase(int ind) {
65
        for (int i = 0, l = 0; i < blocks.size(); ++i) {
66
            int r = l + blocks[i].size();
67
            if (ind < r) {
68
                auto it = lower_bound(all(blocks[i]), a[i][ind - l]);
69
                a[i].erase(a[i].begin() + (ind - l));
70
                blocks[i].erase(it);
71
                break;
72
            }
73
            l = r;
74
        }
75
        --n;
76
        if (++changes == K) {
77
            rebuild();
78
        }
79
    }
80
 
81
    void insert(int ind, int v) {
82
        for (int i = 0, l = 0, r; i < blocks.size(); ++i) {
83
            r = l + blocks[i].size();
84
            if (ind <= r) {
85
                auto it = upper_bound(all(blocks[i]), v);
86
                a[i].insert(a[i].begin() + (ind - l), v);
87
                blocks[i].insert(it, v);
88
                break;
89
            }
90
            l = r;
91
        }
92
        ++n;
93
        if (++changes == K) {
94
            rebuild();
95
        }
96
    }
97
 
98
    void update(int l_q, int r_q, int x) {
99
        for (int i = 0, l = 0, r; i < blocks.size(); i++, l = r) {
100
            r = l + blocks[i].size();
101
            if (r <= l_q || r_q <= l) {
102
                continue;
103
            }
104
            if (l >= l_q && r <= r_q) {
105
                promise[i] += x;
106
                continue;
107
            }
108
            for (int j = max(l, l_q); j < min(r, r_q); ++j) {
109
                a[i][j - l] += x;
110
            }
111
            apply(i);
112
        }
113
    }
114
 
115
    int get(int l_q, int r_q, int x, int y) {
116
        int l = 0, r, cnt = 0;
117
        for (int i = 0; i < blocks.size(); ++i, l = r) {
118
            r = l + blocks[i].size();
119
            int nx = x - promise[i];
120
            int ny = y - promise[i];
121
            if (r <= l_q || r_q <= l) {
122
                continue;
123
            }
124
            if (l >= l_q && r <= r_q) {
125
                cnt += static_cast<int>(upper_bound(all(blocks[i]), ny) - lower_bound(all(blocks[i]), nx));
126
                continue;
127
            }
128
            for (int j = max(l, l_q); j < min(r, r_q); ++j) {
129
                if (a[i][j - l] <= ny && a[i][j - l] >= nx) {
130
                    ++cnt;
131
                }
132
            }
133
        }
134
        return cnt;
135
    }
136
};