脚本宝典收集整理的这篇文章主要介绍了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("%lldn", ans);
    }
}

脚本宝典总结

以上是脚本宝典为你收集整理的HDU6943_二维树状数组解决三维偏序问题全部内容，希望文章能够帮你解决HDU6943_二维树状数组解决三维偏序问题所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。