853C - Boredom - CodeForces Solution

#include<bits/stdc++.h>

using namespace std;
using INT = long long;
const int NN = 2e5 + 100;

int A[NN], L[NN], R[NN], l[NN], r[NN];
vector <int> pre[NN], suf[NN];
int n, B[NN];
void add(int u, int x){
	for(; u < NN; u += u&-u) B[u] += x;
}
int calc(int u, int ans = 0){
	for(; u; u -= u&-u) ans += B[u];
	return ans;
}
INT CNK(int n){
	return 1ll * n * (n - 1) / 2;
}
INT ans[NN];
int main() {
#ifndef ONLINE_JUDGE
	freopen("in.in", "r", stdin);
	freopen("out.out", "w", stdout);
#endif
	int n, q; cin >> n >> q;
	for(int i = 1; i <= n; i ++) scanf("%d", A + i);
	for(int i = 1; i <= q; i ++){
		scanf("%d%d%d%d", L + i, l + i, R + i, r + i);
		ans[i] = CNK(n) - CNK(L[i] - 1) - CNK(n - R[i]) - CNK(l[i] - 1) - CNK(n - r[i]);
		swap(L[i], l[i]), swap(R[i], r[i]);
		pre[l[i] - 1].push_back(i);
		suf[r[i] + 1].push_back(i);
	}
	for(int i = 1; i <= n; i ++){
		add(A[i], 1);
		for(int id : pre[i]){
			ans[id] += CNK(calc(L[id] - 1));
			ans[id] += CNK(calc(n) - calc(R[id]));
		}
	}
	memset(B, 0, sizeof(B));
	for(int i = n; i >= 1; i --){
		add(A[i], 1);
		for(int id : suf[i]){
			ans[id] += CNK(calc(L[id] - 1));
			ans[id] += CNK(calc(n) - calc(R[id]));
		}
	}
	for(int i = 1; i <= q; i ++) printf("%I64d\n", ans[i]);
	return 0;
}