学步园

题目地址：

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3875

2011 年 台湾 新竹赛区的题目~~

简单的一道线段树，求区间最大覆盖次数。。。。

WA了一次~~    原因懒得再写Query，直接在Update的同时判断最大覆盖次数 ~   把子节点上的覆盖次数给忽略了。。。囧 ~

代码简单，方法简单，就不解释了~

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#define ll (v<<1)
#define rr (v<<1|1)
#define tmid ((l+r)>>1)

using namespace std;

const int maxn=30010;
int num[maxn*4],mx;
int a,b;

void make_tree(){
	memset(num,0,sizeof(num));
}

void update(int l,int r,int v){
	if(l>b || r<a) return;
	if(a<=l && r<=b){
		num[v]++;
		return ;
	}
	update(l,tmid,ll);
	update(tmid+1,r,rr);
}
void query(int l,int r,int v,int m){
	m+=num[v];
	if(l==r){
		if(mx<m) mx=m;
		return;
	}
	query(l,tmid,ll,m);
	query(tmid+1,r,rr,m);
}

int main(){
	int n,t,i;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		make_tree();
		while(n--){
			if(a>b) swap(a,b);
			scanf("%d%d",&a,&b);
			update(1,maxn,1);
		}
		mx=0;
		query(1,maxn,1,0);
		printf("%d\n",mx);
	}
    return 0;
}