题目链接1：https://www.lydsy.com/JudgeOnline/problem.php?id=5168
题目链接2：https://www.lydsy.com/JudgeOnline/problem.php?id=5029
bzoj喜加二！
一眼看上去就很水，但是最开始想的是线段树，由于空间不够，也懒得写线段树，所以又思考一番，发现其实很水
将每个海报拆成两个点，记录下id，代表它是第几个被贴上去的
按照下标从小到大排个序
然后每次一口气把当前下标上的操作全都处理完，再统计下当前的答案
当前的答案就是目前还贴着的海报当中id最大的那个，这个可以用一个set来维护
注意：需要把右端点的值+1，因为是闭区间
|
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 |
#include<bits/stdc++.h> #define MAXM 1010 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct node{ int p,id; bool w; node(int a,int b,int c){p=a,id=b,w=c;} node(){} friend bool operator < (node a,node b){ return a.p<b.p; } }a[MAXM*2]; bool see[MAXM]; int n,m,ans; set<int>s; int main(){ n=rd(),m=rd(); for(int i=1; i<=m; i++){ int l=rd(),r=rd(); a[i*2-1]=node(l,i,1); a[i*2]=node(r+1,i,0); } m*=2; sort(a+1,a+m+1); int p,w,id; for(int i=1; i<=m;){ p=a[i].p; while(p==a[i].p){ w=a[i].w; id=a[i].id; if(w)s.insert(id); else s.erase(id); i++; } if(s.size()){ int x=*(s.rbegin()); if(!see[x])ans++,see[x]=true; } } printf("%d\n",ans); return 0; } |
《bzoj 5168: [HAOI2014]贴海报 & 5029: 贴小广告 离散化+扫描线+set》有1个想法