Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- struct data {
- int l, r, k, t, id;
- };
- const int N = 30005;
- const int Q = 200005;
- int n, q;
- int bit[N];
- int res[Q];
- data v[N + Q];
- void update(int i, int v) {
- for (; i <= n; i += i & -i) {
- bit[i]++;
- }
- }
- int get(int i) {
- int v = 0;
- for (; i; i -= i & -i) {
- v += bit[i];
- }
- return v;
- }
- bool cmp(data a, data b) {
- return a.k == b.k ? a.t > b.t : a.k > b.k;
- }
- int main() {
- ios::sync_with_stdio(0); cin.tie(0);
- cin >> n;
- for (int i = 1; i <= n; i++) {
- cin >> v[i].k;
- v[i].l = i;
- }
- cin >> q;
- for (int i = 1; i <= q; i++) {
- cin >> v[n + i].l >> v[n + i].r >> v[n + i].k;
- v[n + i].t = 1;
- v[n + i].id = i;
- }
- sort(v + 1, v + n + q + 1, cmp);
- for (int i = 1; i <= n + q; i++) {
- if (v[i].t == 0) update(v[i].l, 1);
- else res[v[i].id] = get(v[i].r) - get(v[i].l - 1);
- }
- for (int i = 1; i <= q; i++) {
- cout << res[i] << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement