本文主要是介绍POJ 3067 Japan 二维树状数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
是一个比较不错的题目。
题目大意是，在一张地图上，西边从上到下均匀排了一列点，东边也是这样，然后给出若干个边，都是从西边的点连到东边的点上。问最后这些边的交点，所谓交点，就是两个边交叉得到的交点，如果交点在结点上，是不算数的。
首先思考一下基本做法，很容易想到，跟某条边相交的边数，跟其在东边和西边的编号有关系。然后就发现，如果某条边在西边的编号大于这条边，并且东边的编号小于这条边，就会出现交叉，当然如果某条边在西边的编号小于这条边，并且东边的编号大于这条边，也会出现交叉。但是，如果两种都计算，显然是会重复计算的，我们就取前一种来计算。
那么就从西边结点，从上到下，对每一条边，观察符合条件的边，然后求和，但是题目给出的边数可能高达一百万。如果直接枚举显然是不靠谱的。
这时，我们再转换一下模型，想象一下以西边顶点为x轴，东边顶点为y轴，建立直角坐标系，那么问题就转化成了，对于每个点，看其右下方点的个数，然后求和，
这时候就不难想到要用到树状数组了。
树状数组要用到二维的，对于每条边呢，用坐标插入时，第一维的x应该是递减的，第二维的y是递增的，表示插入这个坐标后，比其x小，并且y大的在统计的时候都能统计到这个坐标。然后求和的时候就是反过来了。
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <map>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 100007
#define INF 1000000000
#define eps 1e-7
using namespace std;
int a[1005][1005];
int xx[1000005], yy[1000005];
int n, m;
int lowbit(int x)
{return x & -x;
}
void modify(int x, int y)
{for(int i = x; i >= 1; i -= lowbit(i))for(int j = y; j <= m; j += lowbit(j))a[i][j]++;
}
long long get_sum(int x, int y)
{long long sum = 0;for(int i = x + 1; i <= n; i += lowbit(i))for(int j = y - 1; j >= 1; j -= lowbit(j))sum += a[i][j];return sum;
}
int main()
{int T, k, cas = 0;scanf("%d", &T);while(T--){scanf("%d%d%d", &n, &m, &k);for(int i = 0; i <= n; i++)for(int j = 0; j <= m; j++)a[i][j] = 0;for(int i = 0; i < k; i++){scanf("%d%d", &xx[i], &yy[i]);modify(xx[i], yy[i]);}long long ans = 0;for(int i = 0; i < k; i++)ans += get_sum(xx[i], yy[i]);printf("Test case %d: %I64d\n", ++cas, ans);}return 0;
}
这篇关于POJ 3067 Japan 二维树状数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
