HDU6943_二维树状数组解决三维偏序问题

本文主要是介绍HDU6943_二维树状数组解决三维偏序问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

传送门

题意

给定一个 \(N \times M\) 的矩阵 \(A\)，规定：点 \((x_{1}, y_{1})\) 控制 \((x_{2}, y_{2})\) 当且仅当 \(A[x_1][y_1] > A[x_2][y_2] + |x_1-x_2| + |y_1-y_2|\)

问满足上述控制条件的有序对 \(((x_1,y_1),(x_2,y_2))\) 的个数

\(N, M \le 10^3, 1 \le A[i][j] \le N + M\)

题解

将矩阵旋转三次，在四种形态中每次只考虑 \(x_1 \ge x_2, y_1 > y_2\) 的点对（后面那个不能取等，不然会重复计算）；

然后就可以把绝对值拆开，就得到了 \(A[x_1][y_1] - x_1 - y_1 > A[x_2][y_2] - x_2 - y_2\) ；

不妨将每个点的权值定为 \(v = A[x][y] - x - y\) ，那么问题就转化成了一个淳朴的三维偏序问题：对于每个坐标点，求 \(x\) 小于等于它、\(y\) 小于它、\(v\) 也小于它的点的个数。

这里采用二维树状数组的做法，树状数组维护 \(y, v\) 确定的区间上出现的点的个数。由于 \(v\) 很小，不用离散化。

先按照 \(x\) 从小到大，再按照 \(y\) 从小到大的顺序遍历所有点，每次先查询 \(y, v\) 都小于它的点（加入顺序保证这些点的 \(x\) 都小于等于当前点）的个数贡献到答案，然后再把自己扔进树状数组里面。

代码

#include <bits/stdc++.h>
#define ll long long
#define MS(arr, val) memset(arr, val, sizeof(arr))
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define PI pair<int, int>
#define lll __int128
#define ull unsigned long long
#define Kases int T; rd(T); rep(kase, 1, T)
#define rep(i, a, b) for(int i = (a), __ ## i = (b); i <= __ ## i; ++i)
#define per(i, b, a) for(int i = (b), __ ## i = (a); i >= __ ## i; --i)
using namespace std;
inline void rd(char* x){scanf("%s", x);}
inline void rd(double &x){scanf("%lf", &x);}
template<typename T> inline void rd(T &x){
    x = 0; bool is = 0; char ch = getchar();
    while(!isdigit(ch)) is |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    is && (x = -x);
}
template<typename T, typename ...U> inline void rd(T &x, U &...y){rd(x), rd(y...);}
template<typename T> inline void write(T x){
    if(x >= 10) write(x / 10);
    putchar('0' + x % 10);
}
const int maxn = 1145;
int t[maxn][maxn << 2], n, m;
inline int lb(int x){return x & (-x);}
void upd(int y, int val)
{
    for(; y <= m; y += lb(y))
        for(int i = val; i <= 2 * (n + m); i += lb(i))
            t[y][i]++;
}
ll ans = 0;
void ask(int y, int val)
{
    for(; y; y -= lb(y))
        for(int i = val; i; i -= lb(i))
            ans += t[y][i];
}
int a[maxn][maxn], b[maxn][maxn];
void rotate()
{
    rep(i, 1, n) rep(j, 1, m) b[j][n - i + 1] = a[i][j];
    swap(n, m);
    rep(i, 1, n) rep(j, 1, m) a[i][j] = b[i][j];
}
int main()
{
    while(scanf("%d%d", &n, &m) == 2)
    {
        ans = 0;
        rep(i, 1, n) rep(j, 1, m) rd(a[i][j]);
        rep(_, 0, 3)
        {
            if(_) rotate();
            rep(i, 1, n) rep(j, 1, m)
            {
                ask(j - 1, a[i][j] - i - j + n + m - 1); // v 有负数，加个偏移量
                upd(j, a[i][j] - i - j + n + m);
            }
            rep(i, 1, m) fill_n(t[i], 2 * (n + m) + 3, 0);
        }
        printf("%lld\n", ans);
    }
}

这篇关于HDU6943_二维树状数组解决三维偏序问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！