POJ 2528 Mayor's posters 线段树（成段更新+离散化） - c++编程基础

题意：
给出N个海报，每个海报有一个长度区间（a,b）.按顺序贴在墙上。
问最后可以看到几张海报。
思路：
一想到的就是线段树，对每个区间进行染色，最后查找一共有多少种颜色。
第一次写玩没看数据大小。MLE了。。仔细一看，海报长度1QW。
然后写了个离散化的，300MS+。
又去看了别人的离散化。。神多了。。60MS。。
优化后的离散
[cpp]?
#include ?
#include ?
#include ?
#include ?
#include ?
#include ?
#include ?
#include ?
#include ?
#include ?
#include ?
#include ?
#define PI acos(-1.0)?
#define Max 20005?
#define inf 1<<28?
#define LL(x) (x<<1)?
#define RR(x)(x<<1|1)?
using namespace std;?
?
struct kdq?
{?
??? int l,r,flag;?
} tree[Max*4];?
?
struct kdq1?
{?
??? int num,id;?
} poster[Max];?
?
int aa[Max][2];?
void build_tree(int l,int r,int u)?
{?
??? tree[u].l=l;?
??? tree[u].r=r;?
??? tree[u].flag=0;?
??? if(l==r)return ;?
??? int mid=(l+r)>>1;?
??? build_tree(l,mid,LL(u));?
??? build_tree(mid+1,r,RR(u));?
}?
?
void update(int l,int r,int u,int i)?
{?
??? if(l>tree[u].r||r ??? if(l==tree[u].l&&r==tree[u].r)?
??? {?
??????? tree[u].flag=i;?
??????? return ;?
??? }?
??? if(tree[u].flag > 0 && tree[u].flag != i)?
??? {?
??????? tree[LL(u)].flag = tree[u].flag;?
??????? tree[RR(u)].flag= tree[u].flag;?
??????? tree[u].flag = 0;?
??? }?
??? int mid=(tree[u].l+tree[u].r)>>1;?
??? if(r<=mid)?
??????? update(l,r,LL(u),i);?
??? else if(l>mid)?
??????? update(l,r,RR(u),i);?
??? else?
??? {?
??????? update(l,mid,LL(u),i);?
??????? update(mid+1,r,RR(u),i);?
??? }?
??? if(tree[LL(u)].flag==tree[RR(u)].flag)?
??????? tree[u].flag=tree[LL(u)].flag;?
??? else?
??????? tree[u].flag=0;?
}?
?
int ans;?
bool visit1[20005];?
?
void query(int l,int r,int u)?
{?
??? if(tree[u].flag&&!visit1[tree[u].flag])?
??????? return ;?

??? if(tree[u].flag)?
??? {?
??????? ans+=visit1[tree[u].flag];?
??????? visit1[tree[u].flag]=0;?
??????? return ;?
??? }?
??? int mid=(l+r)>>1;?
??? query(l,mid,LL(u));?
??? query(mid+1,r,RR(u));?
}?
bool cmp(kdq1 &a,kdq1 &b)?
{?
??? return a.num }?
int main()?
{?
??? int i,j,k,l,n,m,T;?
??? scanf("%d",&T);?
??? int a,b;?
??? while(T--)?
??? {?
??????? memset(visit1,1,sizeof(visit1));?
??????? scanf("%d",&n);?
??????? for(i=0; i ??????? {?
??????????? scanf("%d%d",&aa[i][0],&aa[i][1]);?
??????????? poster[2*i].num=aa[i][0];?
??????????? poster[2*i].id=-(i+1);?
??????????? poster[2*i+1].num=aa[i][1];?
??????????? poster[2*i+1].id=i+1;?
??????? }?
??????? sort(poster,poster+2*n,cmp);?
??????? int temp=poster[0].num;?
??????? int tp=1;?
??????? for(i=0; i<2*n; i++)?
??????? {?
??????????? if(temp!=poster[i].num)?
??????????? {?
??????????????? tp++;?
??????????????? temp=poster[i].num;?
??????????? }?
??????????? if(poster[i].id<0)?
??????????? {?
??????????????? aa[-poster[i].id-1][0]=tp;?
??????????? }?
??????????? else?
??????????? {?
??????????????? aa[poster[i].id-1][1]=tp;?
??????????? }?
??????? }?
??????? build_tree(1,tp,1);?
??????? for(i=0; i ??????????? update(aa[i][0],aa[i][1],1,i+1);?
??????? ans=0;?
??????? query(1,tp,1);?
??????? printf("%d\n",ans);?
??? }?
??? return 0;?
}?
第一次写的离散
[cpp]
#include ?
#include ?
#include ?
#include ?
#include ?
#include ?
#include ?
#include ?
#include ?
#include ?
#include ?
#include ?
#define PI acos(-1.0)?
#define Max 20005?
#define inf 1<<28?
#define LL(x) (x<<1)?
#define RR(x)(x<<1|1)?
using namespace std;?
?
struct kdq?
{?
??? int l,r,flag;?
} tree[Max*4];?
?
int aa[Max],bb[Max];?
?
void build_tree(int l,int r,int u

POJ 2528 Mayor's posters 线段树（成段更新+离散化）(一)