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
#include <iostream>
#include <string.h>
const int N = 100100;
int tree[N];
int id[N];
int lowbit(int x) {
    return x & -x;
}
void modify(int x, int pos, int n) {
    while (pos <= n) {
        tree[pos] += x;
        pos += lowbit(pos);
    }
}
int query(int pos, int n) {
    int sum = 1;
    while (pos > 0) {
        sum += tree[pos];
        pos -= lowbit(pos);
    }
    return pos == 0 || pos == n + 1 ? sum + 1 : sum;
}
bool check(int L, int R, int n) {
    if (L < 0 || R > n + 1)  return false;
    int sum = query(R - 1, n) - query(L, n);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX