code1083免費版，Codeforces 853C - Boredom

853C - Boredom

題意

給出一個矩陣，每行每列有且僅有一個點。每次詢問一個子矩形，問這些點構成的矩形有多少個與給定的矩形相交（兩個處于對角線上的點可以組成矩形）。

分析

考慮矩形周圍 8 個方向，答案其實就是這些方向上的點的組合。直接去算相交比較麻煩，我們可以考慮去算不相交的矩形的個數，例如上方有 \(x\) 個點，則要減去矩形的個數 \(\frac{x * (x - 1)}{2}\) ，下左右同理，但是這樣會多減去左下角、左上角、右上角、右下角四個區域的點組成的矩形的個數，考慮再加回來，那我們實際上就要高效算出這些區域內點的個數。二維平面統計點的個數，上主席樹。

code1083免費版？再講講主席樹查詢的那部分，和線段樹很類似（廢話）。為什么它可以統計縱軸方向上某個區間點的個數呢？注意到在插入數據的時候我們是根據值的大小去決定走左邊還是右邊的，在查詢的時候，同樣根據值的大小決定走左還是走右（這個值此時是區間端點的值）。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lson l, m
#define rson m + 1, r
const int MAXN = 2e5 + 10;
int L[MAXN << 5], R[MAXN << 5], sum[MAXN << 5];
int tot;
int f[MAXN];
int build(int l, int r) {int rt = ++tot;sum[rt] = 0;if(l < r) {int m = l + r >> 1;L[rt] = build(lson);R[rt] = build(rson);}return rt;
}
int update(int pre, int l, int r, int x) {int rt = ++tot;L[rt] = L[pre]; R[rt] = R[pre]; sum[rt] = sum[pre] + 1;if(l < r) {int m = l + r >> 1;if(x <= m) L[rt] = update(L[pre], lson, x);else R[rt] = update(R[pre], rson, x);}return rt;
}
ll query(int ql, int qr, int l_, int r_, int l, int r) {if(l >= l_ && r <= r_) return sum[qr] - sum[ql];int m = (l + r) / 2;ll res = 0;if(m >= l_) res += query(L[ql], L[qr], l_, r_, lson);if(m < r_) res += query(R[ql], R[qr], l_, r_, rson);return res;
}
ll cal(ll x) { return x * (x - 1) / 2; }
int main() {tot = 0;int n, q;scanf("%d%d", &n, &q);f[0] = build(1, n);for(int i = 1; i <= n; i++) {int x;scanf("%d", &x);f[i] = update(f[i - 1], 1, n, x);}while(q--) {int l, d, r, u;scanf("%d%d%d%d", &l, &d, &r, &u);ll res = cal(n) - cal(l - 1) - cal(n - r) - cal(d - 1) - cal(n - u);if(d > 1) {res += cal(query(f[0], f[l - 1], 1, d - 1, 1, n));res += cal(query(f[r], f[n], 1, d - 1, 1, n));}if(u < n) {res += cal(query(f[0], f[l - 1], u + 1, n, 1, n));res += cal(query(f[r], f[n], u + 1, n, 1, n));}printf("%I64d\n", res);}return 0;
}