Mayor's posters POJ - 2528
2021/5/20 10:30:48
本文主要是介绍Mayor's posters POJ - 2528,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
原题链接
考察:线段树
线段树染色问题
思路:
每次张贴海报都是一次区间修改.而染色区间l,r范围过大.需要离散化.离散化后就可以定义线段树了.
struct Node{ int l,r,c;//l,r左右端点.c为该区间的颜色,同时也是懒标记 }tr[N<<3];
这里定义c为该区间颜色种类是不可取的,无法用子节点更新父节点信息.定义
- c = 0表示未染色;
- c = i(i>0)表示该区间颜色为i;
- c = -1表示该区间有多种颜色.
关键是如何计数.我们利用线段树query查询时,遇到该区间颜色确定时即可返回.时间复杂度大概是O(log2N)
然后是如何push_up,这个比较简单
void push_up(int u) { if(tr[u<<1].c==tr[u<<1|1].c) tr[u].c = tr[u<<1].c; else tr[u].c = -1; }
然后比较关键的是Push_down.很直观的感受就是当父节点是-1时,不能简单地push_down.注意这点就可以了.
最后的一个关键点是,本来不相邻的区间,离散化后会变成相邻的.此时计数可能会少一个.eg:
1 3 1 10 1 4 6 10
离散化后为:
1 4
1 2
3 4
合并会记录两个.实际上有3个.这时需要再4与6之间插入一个数,使其为不相邻.
Code:
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #include <vector> using namespace std; const int N = 100010; int n; vector<int> v; bool st[N]; struct Node{ int l,r,c; }tr[N<<3]; struct Segment{ int l,r,op; }seg[N]; int get(int x) { return lower_bound(v.begin(),v.end(),x)-v.begin()+1; } void push_up(int u) { if(tr[u<<1].c==tr[u<<1|1].c) tr[u].c = tr[u<<1].c; else tr[u].c = -1; } void build(int u,int l,int r) { tr[u].l = l,tr[u].r = r; if(l==r) return; int mid = l+r>>1; build(u<<1,l,mid),build(u<<1|1,mid+1,r); } void push_down(int u) { if(tr[u].c!=-1) tr[u<<1].c = tr[u<<1|1].c = tr[u].c; tr[u].c = 0; } void modify(int u,int l,int r,int x) { if(tr[u].l>=l&&tr[u].r<=r) { tr[u].c = x; return; } push_down(u); int mid = tr[u].l+tr[u].r>>1; if(l<=mid) modify(u<<1,l,r,x); if(mid<r) modify(u<<1|1,l,r,x); push_up(u); } void query(int u,int l,int r) { if(tr[u].l>=l&&tr[u].r<=r&&tr[u].c!=-1) { st[tr[u].c] = 1; return; } // push_down(u); int mid = tr[u].l+tr[u].r>>1; if(l<=mid) query(u<<1,l,r); if(mid<r) query(u<<1|1,l,r); } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d",&n); v.clear(); memset(tr,0,sizeof tr); for(int i=1;i<=n;i++) { int l,r; scanf("%d%d",&l,&r); seg[i].l = l,seg[i].r = r,seg[i].op = i; v.push_back(l),v.push_back(r); } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); int sz = v.size()-1; for(int i=0;i<sz;i++) { int a = v[i],b = i+1>=v.size()?a:v[i+1]; if(b-a>1) v.push_back(a+1); } sort(v.begin(),v.end()); build(1,1,v.size()); for(int i=1;i<=n;i++) { int l = get(seg[i].l),r = get(seg[i].r); modify(1,l,r,seg[i].op); } query(1,1,v.size()); int ans = 0; for(int i=1;i<=n;i++) ans+=st[i],st[i] = 0; printf("%d\n",ans); } return 0; }
这篇关于Mayor's posters POJ - 2528的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?