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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
| #include <bits/stdc++.h>
#define mp(x, y) std::make_pair(x, y)
#define eb emplace_back
#define fi first
#define se second
#define il inline
#define file(name) \
freopen(name ".in", "r", stdin); \
freopen(name ".out", "w", stdout);
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
const int N = 2e5 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3f;
int n, q, b[N], t[N], res[N][10];
il void add(int p, int v) {
for (; p <= n; p += p & -p) t[p] += v;
return ;
}
il int ask(int p) {
int res = 0;
for (; p; p -= p & -p) res += t[p];
return res;
}
struct query {
int x, y, id, type;
} qu[10 * N];
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::cin >> n >> q;
for (int i = 1; i <= n; ++i) {
int x;
std::cin >> x;
b[x] = i;
}
int cnt = 0;
for (int i = 1; i <= q; ++i) {
int l, d, r, u;
std::cin >> l >> d >> r >> u;
qu[++cnt] = {n, l - 1, i, 1};
qu[++cnt] = {u, l - 1, i, 2};
qu[++cnt] = {d - 1, l - 1, i, 3};
qu[++cnt] = {n, r, i, 4};
qu[++cnt] = {u, r, i, 5};
qu[++cnt] = {d - 1, r, i, 6};
qu[++cnt] = {n, n, i, 7};
qu[++cnt] = {u, n, i, 8};
qu[++cnt] = {d - 1, n, i, 9};
}
for (int i = 1; i <= n; ++i) qu[++cnt] = {i, b[i], 0, 0};
std::sort(qu + 1, qu + 1 + cnt, [](query x, query y) {
return x.x ^ y.x ? x.x < y.x : x.id < y.id;
});
for (int i = 1; i <= cnt; ++i) {
if (!qu[i].id) add(qu[i].y, 1);
else res[qu[i].id][qu[i].type] = ask(qu[i].y);
}
for (int i = 1; i <= q; ++i) {
int s1 = res[i][1] - res[i][2];
int s2 = res[i][2] - res[i][3];
int s3 = res[i][3];
int s4 = res[i][4] - res[i][1] - res[i][5] + res[i][2];
int s5 = res[i][5] - res[i][2] - res[i][6] + res[i][3];
int s6 = res[i][6] - res[i][3];
int s7 = res[i][7] - res[i][4] - res[i][8] + res[i][5];
int s8 = res[i][8] - res[i][5] - res[i][9] + res[i][6];
int s9 = res[i][9] - res[i][6];
ll ans = 0;
ans += 1ll * s1 * (s5 + s6 + s8 + s9);
ans += 1ll * s2 * (s5 + s6 + s8 + s9 + s4 + s7);
ans += 1ll * s3 * (s4 + s5 + s7 + s8);
ans += 1ll * s4 * (s5 + s6 + s8 + s9);
ans += 1ll * s5 * (s6 + s7 + s8 + s9);
ans += 1ll * s6 * (s7 + s8);
ans += 1ll * s5 * (s5 - 1) / 2;
std::cout << ans << '\n';
}
return 0;
}
|
