【链接】h在这里写链接

【题意】

给你一个n*n的矩阵。

其中每一列都有一个点。

任意两个点构成了矩形的两个对角点

->即任意两个点确定了一个矩形。

->总共能确定n*(n-1)/2个矩形。

现在,给你一个圈出来的矩形区域。

问你有多少个矩形,是在这个矩形之内.或和矩形相交。

【题解】

找和询问矩形相交的矩形不好找。

我们可以反过来.

求出不和询问的矩形相交的矩形的个数。

具体的。

我们找出询问的矩形的上方,左方,下方,右方的整个矩形区域的点的个数。

显然,假设这个区域里面的点的个数为x;

则能够构成x*(x-1)/2个矩形。

用总的矩形个数n*(n-1)/2,减去这4个大矩形区域的矩形个数。就是和它相交的矩形个数了。

但是,我们会把左上方,左下方,右上方,右下方的区域多算一次。

得把它加上去。

->维护矩形区域的点的个数。

这个东西能用树状数组。

在排序的基础上,离线做出来。

具体的,只要记录一下几个点的(1,1)~(x,y)的矩形区域前缀和就好。

然后把每个询问需要的前缀和按顺序算出来。

(↓下面是8个需要离线处理的位置。)

这样就能处理出来4个方向以及4个角落的区域内的点的个数了。

【错的次数】

【反思】

排序之后,用树状数组,能够离线处理二维区间和问题。

【代码】

#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;

}

巴特西

【Codeforces Round #433 (Div. 1) C】Boredom(树状数组)