POJ3067 Japan 线段树 || 树状数组

多数人使用了树状数组，这道题目其实还可以暴力打表，题意就是日本东边有N个城市，西边有M个，左右之间需要高速公路连起来，连接题目已经给出，问高速公路的交点个数，题目已经声明 三条及三条以上的高速路 绝对不会相交于同一点

打表举个例子：

1，2，3，4表示东边城市标号，1，2，3，4，5，表示西边的，如果题目给出东边3与西边3相连，下面表中的 ** 号表示已经连接，那么影响高速交点 个数的 连接  就是下面表中的 # 部分，随便一个草图一画，就能够轻易找到规律，这样多对已知连接出现时，其实是有一个包含叠加的关系，所以直接暴力打表就可以了

我是使用了线段树，乱搞搞出来的，自己也是WA了很多次，最后迷迷糊糊的 写出来了，也是利用了 画草图 ，多画画就有思路了

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>

#define ll long long

#define eps 1e-7

#define inf 0xfffffff
const ll INF = 1ll<<61;

using namespace std;

//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;
//

typedef struct {
	int l;
	int r;
	int w;
}Node;

Node tree[1000000 + 5];

struct node {
	int x;
	int y;
}p[1000000 + 5];


void clear() {
	memset(tree,0,sizeof(tree));
	memset(p,0,sizeof(p));
}

bool cmp(node x,node y) {
	if(x.x == y.x)
		return x.y>y.y;
	return x.x>y.x;
}

void build(int root,int left,int right) {
	tree[root].l = left;
	tree[root].r = right;
	if(tree[root].l == tree[root].r - 1)
		return ;
	int mid = (left + right)/2;
	build(root * 2,left,mid);
	build(root * 2 + 1,mid,right);
}

int find(int root,int left,int right) {
	if(tree[root].l >= left && tree[root].r <=right)
		return tree[root].w;
	if(tree[root].l == tree[root].r - 1)
		return 0;
	int ans = 0;
	int mid = (tree[root].l + tree[root].r)/2;
	if(left <= mid)
		ans += find(root * 2,left,right);
	if(right > mid)
		ans += find(root * 2 + 1,left,right);
	return ans;
}

void update(int root,int left,int right) {
	if(tree[root].l >= left && tree[root].r <= right) {
		tree[root].w++;
		return;
	}
	if(tree[root].l == tree[root].r - 1)
		return;
	int mid =(tree[root].l + tree[root].r)/2;
	if(left <= mid)
		update(root *2,left,right);
	if(right > mid)
		update(root * 2 + 1,left,right);
	tree[root].w = tree[root * 2 + 1].w + tree[root * 2].w;
}

int main() {
	int Case = 0;
	ll ans;
	int n,m,k,t;
	scanf("%d",&t);
	while(t--) {
		clear();
		ans = 0;
		scanf("%d %d %d",&n,&m,&k);
		int maxn = max(n,m);
		for(int i=0;i<k;i++)
			scanf("%d %d",&p[i].x,&p[i].y);
		sort(p,p+k,cmp);
		build(1,1,maxn);
		for(int i=0;i<k;i++) {
			ans += find(1,1,p[i].y);
			update(1,p[i].y,p[i].y + 1);
		}
		printf("Test case %d: %I64d\n",++Case,ans);
	}
	return EXIT_SUCCESS;
}

POJ3067 Japan 线段树 || 树状数组

原文：http://blog.csdn.net/yitiaodacaidog/article/details/18461293