poj2528 Mayor's posters（线段树的离散化）

本文主要是介绍poj2528 Mayor's posters（线段树的离散化），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

题目链接：http://poj.org/problem?id=2528

分析：其实离散化就是将一个很大的区间映射为一个很小的区间，而不改变原有的大小覆盖关系。但是注意简单的离散化可能  会出现错误，给出下面两个简单的例子应该能体现普通离散化的缺陷: 例子一:1-10 1-4 5-10 例子二:1-10 1-4 6-10 普通离散化后都变成了[1,4][1,2][3,4] 线段2覆盖了[1,2],线段3覆盖了[3,4],那么线段1是否被完全覆盖掉了呢? 例子一是完全被覆盖掉了,而例子二没有被覆盖  解决的办法则是对于距离大于1的两相邻点，中间再插入一个点，本题还用到了Lazy标记的思想。

代码：

 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e4+10;
int s[maxn],e[maxn],lisan[4*maxn],t,n,tmp,vis[maxn],ans;
struct node{int l,r,v;
}tree[16*maxn];int bin(int x){int l=1,r=tmp-1;while(l<=r){int mid=(l+r)>>1;if(lisan[mid]==x) return mid;else if(x<lisan[mid]) r=mid-1;else l=mid+1;}
}void build(int l,int r,int id){tree[id].l=l,tree[id].r=r,tree[id].v=-1;if(l==r) return ;int mid=(l+r)>>1;build(l,mid,2*id);build(mid+1,r,2*id+1);
}void update(int l,int r,int id,int col){if(l<=tree[id].l && tree[id].r<=r){tree[id].v=col;return ;}if(tree[id].v!=-1) {tree[2*id].v=tree[2*id+1].v=tree[id].v;tree[id].v=-1;}int mid=(tree[id].l+tree[id].r)>>1;if(r<=mid) update(l,r,2*id,col);else if(l>mid) update(l,r,2*id+1,col);else update(l,mid,2*id,col),update(mid+1,r,2*id+1,col);
}void query(int l,int r,int id){if(tree[id].v!=-1){if(!vis[tree[id].v]){ans++;vis[tree[id].v]=1;}return ;}if(l==r) return ;int mid=(l+r)>>1;query(l,mid,2*id);query(mid+1,r,2*id+1);
}int main(){///std::ios::sync_with_stdio(false);cin>>t;while(t--){memset(vis,0,sizeof(vis));cin>>n;for(int i=1;i<=n;i++) cin>>s[i]>>e[i];for(int i=1;i<=n;i++) lisan[i]=s[i];for(int i=n+1;i<=2*n;i++) lisan[i]=e[i-n];///离散化sort(lisan+1,lisan+2*n+1);int tot=1;lisan[tot++]=lisan[1];for(int i=1;i<2*n;i++)if(lisan[i+1]!=lisan[i]) lisan[tot++]=lisan[i+1];tmp=tot-1;for(int i=1;i<tot;i++)if(lisan[i+1]-lisan[i]!=1) lisan[++tmp]=lisan[i]+1;sort(lisan+1,lisan+tmp);build(1,tmp-1,1);for(int i=1;i<=n;i++){int L=bin(s[i]),R=bin(e[i]); //二分update(L,R,1,i);}query(1,tmp-1,1);cout<<ans<<endl;ans=0;}
}

线段树的应用

维护区间最大值

void pushup( ll r ) {root[r] = max(root[ls],root[rs]);
}void updata( ll r, ll le, ll ri, ll pos, ll w ) {if( le == ri ) {root[r] = w;return;}ll mid = (le+ri)/2;if( pos <= mid ) {updata(ls,le,mid,pos,w);}if( mid < pos ) {updata(rs,mid+1,ri,pos,w);}pushup(r);
}

 

去重+离散化

//一个n*n的图中有效贡献点有限，可这样离散，注意要写行列贡献相同需去重for( ll i = 1; i <= n; i ++ ) {scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].w);dis[i] = 0, num[i] = a[i].y;}sort(num+1,num+n+1);sz = unique(num+1,num+n+1) - (num+1);  //去重sort(a+1,a+n+1,cmp);a[n+1].x = a[n].x + 1;build(1,1,sz);    //建树

 

 求图贡献最大

//一段区间最大贡献
ll query( ll r, ll le, ll ri, ll L, ll R ) {if( R < le || ri < L ) {return 0;}if( L <= le && ri <= R ) {return root[r];}ll MAX = 0;ll mid = (le+ri)/2;if( L <= mid ) {MAX = max(MAX,query(ls,le,mid,L,R));}if( mid < R ) {MAX = max(MAX,query(rs,mid+1,ri,L,R));}return MAX;
}

dis[i] = query(1,1,sz,1,le-1) + a[i].w;if( a[i].x != a[i+1].x ) {if( dis[i] > root[pos[le]] ) {updata(1,1,sz,le,dis[i]);}for( ll i = 1; i <= cnt; i ++ ) {if( dt[i] > root[pos[st[i]]] ) {updata(1,1,sz,st[i],dt[i]);}}cnt = 0;} else {cnt ++;st[cnt] = le, dt[cnt] = dis[i];}ans = max(ans,dis[i]);

 

 

 区间最大值

void build(int l, int r, int n)
{s[n].l = l;s[n].r = r;s[n].maxx = 0;s[n].minn = N;if(l == r){s[n].maxx = s[n].minn = a[l];return;}int mid = (l + r) >> 1;build(l, mid, n<<1);build(mid + 1, r, n<<1|1);s[n].maxx = max(s[n<<1].maxx, s[n<<1|1].maxx);s[n].minn = min(s[n<<1].minn, s[n<<1|1].minn);
}
void query(int l, int r, int n)
{if(s[n].l == l && s[n].r == r){ans_x = max(ans_x, s[n].maxx);ans_y = min(ans_y, s[n].minn);return;}int mid = (s[n].l + s[n].r) >> 1;if(r <= mid)query(l, r, n<<1);else if(l > mid)query(l, r, n<<1|1);else{query(l, mid, n<<1);query(mid+1, r, n<<1|1);}
}

 

 

这篇关于poj2528 Mayor's posters（线段树的离散化）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---