【链接】h在这里写链接
【题意】
给你一个n*n的矩阵。
其中每一列都有一个点。
任意两个点构成了矩形的两个对角点
->即任意两个点确定了一个矩形。
->总共能确定n*(n-1)/2个矩形。
现在,给你一个圈出来的矩形区域。
问你有多少个矩形,是在这个矩形之内.或和矩形相交。
【题解】
找和询问矩形相交的矩形不好找。
我们可以反过来.
求出不和询问的矩形相交的矩形的个数。
具体的。
我们找出询问的矩形的上方,左方,下方,右方的整个矩形区域的点的个数。
显然,假设这个区域里面的点的个数为x;
则能够构成x*(x-1)/2个矩形。
用总的矩形个数n*(n-1)/2,减去这4个大矩形区域的矩形个数。就是和它相交的矩形个数了。
但是,我们会把左上方,左下方,右上方,右下方的区域多算一次。
得把它加上去。
->维护矩形区域的点的个数。
这个东西能用树状数组。
在排序的基础上,离线做出来。
具体的,只要记录一下几个点的(1,1)~(x,y)的矩形区域前缀和就好。
然后把每个询问需要的前缀和按顺序算出来。
(↓下面是8个需要离线处理的位置。)
这样就能处理出来4个方向以及4个角落的区域内的点的个数了。
【错的次数】
0
【反思】
排序之后,用树状数组,能够离线处理二维区间和问题。
【代码】
#include <bits/stdc++.h>
using namespace std;
const int M = 2e5;
int n, m;
vector <tuple<int, int, int, int> > a;
long long num[M * 10 + 10],ans[M+10][9];
struct BI {
int a[M + 10];
int lowbit(int x) {
return x&(-x);
}
void add(int x, int y) {
while (x <= M) {
a[x] += y;
x += lowbit(x);
}
}
int sum(int x) {
int now = 0;
while (x > 0) {
now += a[x];
x -= lowbit(x);
}
return now;
}
int get_sum(int l, int r) {
return sum(r) - sum(l - 1);
}
}b;
long long C(long long x) {
return x*(x - 1) / 2;
}
int main() {
//freopen("F:\\rush.txt", "r", stdin);
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for (int i = 1,p; i <= n; i++) {
cin >> p;
a.push_back(make_tuple(i,p,0,0));
}
for (int i = 1,l,d,r,u; i <= m; i++) {
cin >> l >> d >> r >> u;
a.push_back(make_tuple(l-1,d-1,i,1));
a.push_back(make_tuple(l - 1, u, i, 2));
a.push_back(make_tuple(l - 1, n, i, 3));
a.push_back(make_tuple(n, u, i, 4));
a.push_back(make_tuple(n, d-1, i, 5));
a.push_back(make_tuple(r, n, i, 6));
a.push_back(make_tuple(r, d - 1, i, 7));
a.push_back(make_tuple(r, u, i, 8));
}
sort(a.begin(), a.end());
for (int i = 0; i <= (int)a.size() - 1; i++) {
int x, y, j, id;
tie(x, y, j, id) = a[i];
if (j == 0) {
b.add(y, 1);
}
else
ans[j][id] = b.get_sum(1, y);
}
vector <long long> v;
v.resize(9);
for (int i = 1; i <= m; i++) {
v[1] = ans[i][1];
v[2] = ans[i][3];
v[3] = ans[i][5];
v[4] = n - ans[i][4];
v[5] = ans[i][3] - ans[i][2];
v[6] = n - ans[i][6];
v[7] = ans[i][5] - ans[i][7];
v[8] = n - ans[i][6] - ans[i][4] + ans[i][8];
long long temp = 0;
temp += C(v[2]) + C(v[4]) + C(v[6]) + C(v[3]) - C(v[5]) - C(v[1]) - C(v[7]) - C(v[8]);
cout << C(n) - temp << endl;
}
return 0;
}