我是靠谱客的博主 迷你心情,这篇文章主要介绍POJ-2528(线段树+离散化)Mayor's posters,现在分享给大家,希望可以做个参考。

Mayor's posters

POJ-2528

  • 本题是线段树的区间更新和离散化的结合。
  • 代码中需要注意的就是这里要加入一个去重的操作。而且我这里建树的时候是从1开始的,所以下标的问题要注意。
  • 还有一个需要注意的地方就是根据题目的意思在离散化之后,可能会出现一个问题,就是[1,10],[1, 4],[6,10]这种情况会发生错误。这里直接将4-6看成是连续的,但是实际上着中间还有一个5是属于第一个区间的。所以针对这种情况需要额外加一个点。
  • 还有一个数据量的问题也需要注意。数组尽量开大一点,要不然不是报RE就是WA(亲测)。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
//离散化+线段树 #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<cmath> using namespace std; const int maxn=100014; int n,m; int lazy[maxn<<2]; int num[maxn<<1]; int left1[maxn]; int right1[maxn]; bool vis[maxn]; int ans=0; void build(int id,int l,int r){ if(l==r) return; int lc=id<<1; int rc=id<<1|1; int mid=(l+r)>>1; build(lc,l,mid); build(rc,mid+1,r); } void pushdown(int id,int l,int r){ if(lazy[id]==0)//这里要注意,不然这些lazy数组都会被赋值为0 return; int lc=id<<1; int rc=id<<1|1; lazy[lc]=lazy[id]; lazy[rc]=lazy[id]; lazy[id]=0; } void update(int id,int l,int r,int p,int q,int v){ if(p<=l&&q>=r){ lazy[id]=v; return; } pushdown(id,l,r); int mid=(l+r)>>1; int lc=id<<1; int rc=id<<1|1; if(p<=mid) update(lc,l,mid,p,q,v); if(q>mid) update(rc,mid+1,r,p,q,v); } void query(int id,int l,int r){ if(lazy[id]&&!vis[lazy[id]]){ ans++; vis[lazy[id]]=1; return; } if(l==r) return; pushdown(id,l,r); int lc=id<<1; int rc=id<<1|1; int mid=(l+r)>>1; query(lc,l,mid); query(rc,mid+1,r); } int main(){ ios::sync_with_stdio(false); cin.tie(0); int t; cin>>t; while(t--){ ans=0; memset(lazy,0,sizeof(lazy)); memset(vis,0,sizeof(vis)); cin>>n; int cnt=1; for(int i=1;i<=n;i++){ int a,b; cin>>left1[i]>>right1[i]; num[cnt++]=left1[i]; num[cnt++]=right1[i]; } sort(num+1,num+cnt); m=unique(num+1,num+cnt)-(num+1); //cout<<m<<endl; //在所有相隔距离大于1的点之间都插入一个单点(让它充当那段被裸露区间) int an=m; for(int i=2;i<=m;i++){ if(num[i]-num[i-1]>1){ num[++an]=num[i-1]+1; } } sort(num+1,num+an+1); build(1,1,an); // for(int i=1;i<=an;i++) // cout<<num[i]<<endl; for(int i=1;i<=n;i++){ int p=lower_bound(num+1,num+an+1,left1[i])-num; int q=lower_bound(num+1,num+an+1,right1[i])-num; //cout<<p<<" "<<q<<endl; update(1,1,an,p,q,i); } query(1,1,an); cout<<ans<<endl; } //system("pause"); return 0; }

转载于:https://www.cnblogs.com/GarrettWale/p/11448260.html

最后

以上就是迷你心情最近收集整理的关于POJ-2528(线段树+离散化)Mayor's posters的全部内容,更多相关POJ-2528(线段树+离散化)Mayor's内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(101)

评论列表共有 0 条评论

立即
投稿
返回
顶部