[Codeforces] 854E. Boredom

題目連結:http://codeforces.com/contest/854/problem/E

---

賽中還有一個多小時時一看到這題就知道該怎麼做了，然而想太快有許多細節忽略掉就爛掉了(後來還因為沒開long long又de了約莫5個小時QQ)。
因為保證每一行每一列都只會有一個格子被塗黑，所以其實可以把整張網格壓成一個序列(如同他給的資料一樣)，那這樣詢問一個矩形內有幾個黑格子時其實就是詢問一個區間大於A小於B的數字有幾個，可能很多人直覺就直接持久話做掉，不過我是想到先前寫過的一個做法(歸併樹)：開一顆線段樹，樹上節點是一個排序好的序列，查詢那個比K大的數字時就直接二分搜一下就好了，而若要再查小於B的數字，其實可以用扣掉比B+1大的做法做就好了。
這樣我們就會做查詢一個矩形內黑色的數量了，剩下該怎麼算的問題了。仔細想想(其實好像根本就是高一組合題)後，發現可以用扣的，那問題轉化為給你一個中間挖掉一塊的矩形，問你可以湊出幾個矩形，那顯然就是挖掉那塊矩形的上下左右一大塊都是不能用的，但是扣掉這些後左上、左下、右上、右下會被多扣，再加回來就好了。

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define ALL(x) (x).begin(), (x).end()
typedef long long lld;
const int N = 200000 + 5;

class SegTree{
	private:
		vector<int> nodes[4*N];
		inline int lc(int x){return 2*x+1;}
		inline int rc(int x){return 2*x+2;}
		int size;
		void build(int l, int r, int arr[], int id){
			if(r-l > 1){
				int mid=(l+r)>>1;
				build(l, mid, arr, lc(id));
				build(mid, r, arr, rc(id));
			}
			for(int i=l;i<r;i++) nodes[id].PB(arr[i]);
			sort(ALL(nodes[id]));
		}
		lld query(int l, int r, int ql, int qr, int v, int id){
			// [l, r) >= v
			if(qr <= l or r <= ql) return 0;
			if(ql <= l and r <= qr){
				return distance(lower_bound(ALL(nodes[id]), v), nodes[id].end());
			}
			int mid = (l+r)>>1;
			return query(l, mid, ql, qr, v, lc(id)) + query(mid, r, ql, qr, v, rc(id));
		}
	public:
		void build(int n, int arr[]){
			size=n;
			build(0, n, arr, 0);
		}
		lld query(int l, int r, int x){
			return query(0, size, l, r, x, 0);
		}
} seg;

int arr[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, q;cin>>n>>q;
	for(int i=0;i<n;i++){
		// (i, arr[i])
		cin>>arr[i];
	}
	seg.build(n, arr);
	while(q--){
		//(l, d)~(r, u)
		int l, d, r, u; cin>>l>>d>>r>>u;
		l--;
		lld ans = (lld)n*(n-1)/2;
		lld dd = seg.query(0, n, 1) - seg.query(0, n, d);
		ans -= dd*(dd-1)/2;
		lld tt = seg.query(0, n, u+1);
		ans -= tt*(tt-1)/2;
		lld ll = seg.query(0, l, 1);
		ans -= ll*(ll-1)/2;
		lld rr = seg.query(r, n, 1);
		ans -= rr*(rr-1)/2;
		// ------------------
		lld lb = seg.query(0, l, 1) - seg.query(0, l, d);
		ans += lb*(lb-1)/2;
		lld rb = seg.query(r, n, 1) - seg.query(r, n, d);
		ans += rb*(rb-1)/2;
		lld la = seg.query(0, l, u+1);
		ans += la*(la-1)/2;
		lld ra = seg.query(r, n, u+1);
		ans += ra*(ra-1)/2;

		cout<<ans<<'\n';
	}
	return 0;
}