hdu 5116 计数

题目大意：给你n个点， n个点的坐标都在200以内，让你统计不相交的两个L形的种数，且L形的两条边长的gcd = 1。

思路：用二维树状数组维护点的信息，然后划分区块进行统计，题解是用总的减去相交的，不需要用到二维树状数组。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define pii pair<int, int>

using namespace std;

const int N =  + ;

const int M = 1e4 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 +;

const double eps=1e-;

const double pi=acos(-);

int n, m, up[N][N], rt[N][N];

LL cnt[N][N], num[N][N];

bool Map[N][N];

struct BIT  {

    LL a[N][N];

    void modify(int x, int y, LL v) {

        for(int i = x; i < N; i += i & -i)

            for(int j = y; j < N; j += j & -j)

                a[i][j] += v;

    }

    LL sum(int x, int y) {

        LL ans = ;

        for(int i = x; i; i -= i & -i)

            for(int j = y; j; j -= j & -j)

                ans += a[i][j];

        return ans;

    }

    void init() {

        memset(a, , sizeof(a));

    }

}bit1, bit2;

void init() {

    for(int i = ; i < N; i++) {

        for(int j = ; j < N; j++) {

            cnt[i][j] = cnt[i][j - ] + (__gcd(i, j) == );

        }

    }

    for(int i = ; i < N; i++) {

        for(int j = ; j < N; j++) {

            for(int k = ; k <= i; k++) {

                num[i][j] += cnt[k][j];

            }

        }

    }

}

int main() {

    init();

    int T; scanf("%d", &T);

    for(int cas = ; cas <= T; cas++) {

        bit1.init(); bit2.init();

        memset(rt, , sizeof(rt));

        memset(up, , sizeof(up));

        memset(Map, , sizeof(Map));

        scanf("%d", &n);

        for(int i = ; i <= n; i++) {

            int x, y; scanf("%d%d", &x, &y);

            Map[x][y] = true;

        }

        for(int i = ; i >= ; i--) {

            for(int j = ; j >= ; j--) {

                if(Map[i][j]) {

                    up[i][j] = up[i + ][j] + ;

                    rt[i][j] = rt[i][j + ] + ;

                }

            }

        }

        LL ans = ;

        for(int i = ; i >= ; i--) {

            for(int j = ; j <= ; j++) {

                if(!Map[i][j] || up[i][j] <=  || rt[i][j] <= ) continue;

                ans += num[up[i][j] - ][rt[i][j] - ] * (bit2.sum(, ) - bit2.sum(i + up[i][j] - , j));

                int q = i + up[i][j] - ;

                for(int k = i + ; k <=  && k <= q; k++) {

                    ans += cnt[k - i][rt[i][j] - ] * (bit2.sum(q, j) - bit2.sum(k, j));

                    ans += cnt[k - i][rt[i][j] - ] * (bit1.sum(k, j - ));

                }

                bit2.modify(i, j, num[up[i][j] - ][rt[i][j] - ]);

                for(int k = j + ; k <=  && k < j + rt[i][j]; k++) {

                    bit1.modify(i, k, cnt[k - j][up[i][j] - ]);

                }

            }

        }

        printf("Case #%d: %lld\n", cas,  * ans);

    }

    return ;

}

/*

*/