程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ3067 Japan 樹狀數組的應用

POJ3067 Japan 樹狀數組的應用

編輯：C++入門知識

這題以前做過，用的線段樹，現在用樹狀數組做一次，

題意：給你n個城市在日本左邊，m個城市在日本右邊，然後k條路，問你這k條路有幾個交點，注意城市的序號其實就是一維坐標所在位置，所以就是兩條平行的數軸，上面有點，而且之間有連線，問你有多少交點

一開始不好想把，這種題目也就排排序來試試看了，先對要修建的公路進行排序，然後再看這樣是否可以更加方便的求出交點的數論，取路的左邊點為先決條件從小到大排列，若相等則按照右邊點來升序排列，然後以左邊點為序號和value值為1進行插入樹狀數組，先求出當前已經插入樹狀數組中的點和當前的這個點有多少個交點，然後累加求和就是最後的答案了

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long
#define LL __int64
#define eps 1e-8

//const ll INF=9999999999999;

#define inf 0xfffffff

using namespace std;


//vector > G;
//typedef pair P;
//vector> ::iterator iter;
//
//mapmp;
//map::iterator p;

const int n = 1000 + 5;

int c[10000 + 5];

typedef struct Node {
	int l,r;
};

Node node[1000000 + 5];

void clear() {
	memset(c,0,sizeof(c));
	memset(node,0,sizeof(node));
}

bool cmp(Node x,Node y) {
	return x.l < y.l || (x.l == y.l && x.r < y.r);
}

int lowbit(int x) {
	return x&(-x);
}

void add(int i,int value) {
	while(i <= n) {
		c[i] += value;
		i += lowbit(i);
	}
}

int get_sum(int i) {
	int sum = 0;
	while(i > 0) {
		sum += c[i];
		i -= lowbit(i);
	}
	return sum ;
}

int main() {
	int t;
	int Case = 0;
	scanf("%d",&t);
	while(t--) {
		clear();
		int n,m,k;
		scanf("%d %d %d",&n,&m,&k);
		int maxn = -1;
		for(int i=0;i