poj2528 离散化+线段树区间更新

就是看区间内有多少张不同的海报，唯一的问题是墙太长，需要离散化一下海报的宽度；

最好的理解方式就是阅读代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<climits>
#define LL long long
using namespace std;
#define maxn 500010
#define ls o*2,l,m
#define rs o*2+1,m+1,r
#define GETM (l+r)/2
using namespace std;
int _set[maxn*2];
bool vis[11000];
int fin_ans;
void pushdown(int o,int l,int r)
{
if(_set[o]!=-1)
{
_set[o*2]=_set[o];
_set[o*2+1]=_set[o];
_set[o]=-1;
}
}
void updata(int o,int l,int r,int tl,int tr,int setv)
{
if(tl<=l && r<=tr)
{
_set[o]=setv;
return ;
}
int m=GETM;
pushdown(o,l,r);
if(tl<=m)
updata(ls,tl,tr,setv);
if(m<tr)
updata(rs,tl,tr,setv);
}
//void query(int o,int l,int r)//不必一直pushdown
//{
//
if(l==r){
//
if(!vis[_set[o]]) {
//
fin_ans++;
//
vis[_set[o]]=true;
//
}
//
return ;
//
}
//
pushdown(o,l,r);
//
int m=(l+r)/2;
//
query(o*2,l,m);
//
query(o*2+1,m+1,r);
//}
void query(int o,int l,int r) {
if (_set[o] != -1) {
if (!vis[_set[o]]) fin_ans ++;
vis[_set[o] ] = true;
return ;
}
if (l == r) return ;
int m = GETM;
query(ls);
query(rs);
}
int arr_l[11000];
int arr_r[11000];
int temp[41000];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
int i,pos=0;
for(i=0;i<n;++i)
{
scanf("%d%d",&arr_l[i],&arr_r[i]);
temp[pos++]=arr_l[i];
temp[pos++]=arr_r[i];
}
int t=1;
sort(temp,temp+pos);
int tt=unique(temp,temp+pos)-temp;
memset(_set,-1,sizeof(_set));
memset(vis,false,sizeof(vis));
for(i=0;i<n;++i)
{
int l=lower_bound(temp,temp+tt,arr_l[i])-temp;
int r=lower_bound(temp,temp+tt,arr_r[i])-temp;
updata(1,0,tt-1,l,r,i);
}
fin_ans=0;
query(1,0,tt-1);
printf("%dn",fin_ans);
}
}

最后

以上就是任性钢笔为你收集整理的poj2528 离散化+线段树区间更新的全部内容，希望文章能够帮你解决poj2528 离散化+线段树区间更新所遇到的程序开发问题。

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