POJ 2528 离散化+线段树染色

九野的博客，转载请注明出处：http://blog.csdn.net/acmmmm/article/details/12027811

题意：

T个测试数据

n个操作

i.th line [u, v] 表示给区间 [u,v] 染上i色

问最后有几种颜色

区间范围很大，所以先离散化

注意区间更新的操作

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <math.h>
#include <queue>
#include <set>
#define N 10100*2
#define ll int
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) (x+y)>>1
using namespace std;
inline ll Min(ll a,ll b){return a>b?b:a;}
inline ll Max(ll a,ll b){return a>b?a:b;}
int n;
int len[N][2];
struct p{
ll num,id;
}line[N];
bool cmp(p a,p b){return a.num<b.num;}
struct node{
int l,r;
ll sum;
}tree[N*4];
void build(int l,int r,int id){
tree[id].l=l , tree[id].r=r;
tree[id].sum=0;
if(l==r)return ;
int mid = MID(l,r);
build(l,mid,L(id));
build(mid+1,r,R(id));
}
void updata(int data,int l,int r,int id){
if( l==tree[id].l && tree[id].r == r)
{ tree[id].sum=data; return ; }
if(tree[id].sum!=0 && tree[id].sum!=data)
{
tree[L(id)].sum=tree[id].sum;//注意当 当前区间有颜色且和要染的颜色不相同时：先把子区间染原色，再更新当前涂的颜色
tree[R(id)].sum=tree[id].sum;
tree[id].sum=0;
}
int mid=MID(tree[id].l,tree[id].r);
if(r<=mid)updata(data, l, r, L(id));
else if(mid<l)updata(data, l, r, R(id));
else
{
updata(data, l, mid, L(id));
updata(data, mid+1, r, R(id));
}
}
int query(int pos,int id){
if(tree[id].l == tree[id].r)return tree[id].sum;
int mid = MID(tree[id].l,tree[id].r);
if(pos<=mid)return query(pos, L(id));
return query(pos, R(id));
}
set<ll>myset;
void find_ans(int id){
if(tree[id].sum!=0){
myset.insert(tree[id].sum);
return ;
}
if(tree[id].l == tree[id].r)return ;
find_ans(L(id));
find_ans(R(id));
}
int main(){
int T,Cas=1,a,b,i;scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(i = 0;i < n;++i){//离散化
scanf("%d%d",&len[i][0],&len[i][1]);
line[2*i].num = len[i][0];
line[2*i].id = -(i+1);//用负数表示 线段起点
line[2*i+1].num = len[i][1];
line[2*i+1].id = i+1;
}
sort(line,line+2*n,cmp);
int temp = line[0].num, tp=1;
for(i=0;i < 2*n;i++)
{
if(line[i].num != temp)
{
tp++;
temp = line[i].num;
}
if(line[i].id < 0)
len[-line[i].id-1][0] = tp;
else
len[ line[i].id-1][1] = tp;
}
build(1,tp,1);
for(i=0;i<n;i++)
{
//
updata(i+1,len[i][0],len[i][1],1);
updata(i+1,len[i][0],len[i][1],1);
}
myset.clear();
find_ans(1);
printf("%dn",myset.size());
}
return 0;
}
/*
99
4
2 4
3 5
1 3
5 7
5
1 4
2 6
8 10
3 4
7 10
3
1 10
1 3
6 10
2
1 10
1 4
4
6 10
1 10
1 4
5 10
ans:
3
4
3
2
2
*/

最后

以上就是舒心板栗为你收集整理的POJ 2528 离散化+线段树染色的全部内容，希望文章能够帮你解决POJ 2528 离散化+线段树染色所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。