[Codeforces Round #737 (Div. 2)] D. Ezzat and Grid T2 D1
2021/8/12 6:07:46
本文主要是介绍[Codeforces Round #737 (Div. 2)] D. Ezzat and Grid T2 D1,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Codeforces Round #737 (Div. 2) D. Ezzat and Grid T2 D1
思路:
将2m个点离散化处理后,从第1行依次往下处理。处理每一行时,线段树维护上一行每个点可以更新的最大值,遍历这一行每个区间,更新最大值。
#include<bits/stdc++.h> #define ll long long #define ls (p<<1) #define rs ((p<<1)|1) #define mid ((t[p].l+t[p].r)>>1) #define pb push_back #define pii pair<int,int> #define mk make_pair #define fi first #define se second using namespace std; int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline void Prin(int x){ //__int128x if(x < 0){ putchar('-'); x = -x; } if(x > 9) Prin(x / 10); putchar(x % 10 + '0'); } const int qs=6e5+7; struct Tree{ int l,r,val,add,Max; #define l(x) t[x].l #define r(x) t[x].r #define val(x) t[x].val #define add(x) t[x].add #define Max(x) t[x].Max }t[qs<<2]; void build(int p,int l,int r){ l(p)=l,r(p)=r; add(p)=0; Max(p)=0; val(p)=0; if(l==r) { return; } build(ls,l,mid); build(rs,mid+1,r); } void down(int p){ if(add(p)==0) return; val(ls)=val(p); val(rs)=val(p); Max(ls)=Max(p); Max(rs)=Max(p); add(ls)=add(p); add(rs)=add(p); add(p)=0; } void update(int p,int l,int r,int ma,int pe){ // cout<<"p="<<p<<" l="<<l(p)<<" r="<<r(p)<<" k="<<k<<"\n"; if(l<=l(p)&&r>=r(p)){ Max(p)=ma; val(p)=pe; add(p)=1; return; } down(p); if(l<=mid) update(ls,l,r,ma,pe); if(r>mid) update(rs,l,r,ma,pe); if(Max(ls)>Max(rs)) val(p)=val(ls); else val(p)=val(rs); Max(p)=max(Max(ls),Max(rs)); } Tree ask(int p,int l,int r){ if(l<=l(p)&&r>=r(p)){ // cout<<"p=="<<p<<" l=="<<l<<" r=="<<r<<" max="<<Max(p)<<" val="<<val(p)<<"\n"; return t[p]; } down(p); Tree te; Tree ml,mr; ml.Max=mr.Max=-1; if(l<=mid) ml=ask(ls,l,r); if(r>mid) mr=ask(rs,l,r); if(ml.Max>mr.Max) te=ml; else te=mr; return te; } int n,m,b[qs],pre[qs],u[qs]; vector<pii> v[qs]; //vector<pii>::iterator it; int main(){ n=read(),m=read(); int h,l,r,cnt=0; for(int i=1;i<=m;++i){ h=read(),l=read(),r=read(); v[h].pb(mk(l,r)); b[++cnt]=l; b[++cnt]=r; } sort(b+1,b+1+cnt); cnt=unique(b+1,b+1+cnt)-b-1; for(int i=1;i<=n;++i){ for(int j=0;j<v[i].size();++j){ pii &it=v[i][j]; it.fi=lower_bound(b+1,b+1+cnt,it.fi)-b; it.se=lower_bound(b+1,b+1+cnt,it.se)-b; } } build(1,1,cnt); int ans=0,ns=0; for(int i=1;i<=n;++i){ int mx=-1; for(int j=0;j<v[i].size();++j){ pii it=v[i][j]; Tree te=ask(1,it.fi,it.se); //cout<<"I="<<i<<" fi="<<it.fi<<" se="<<it.se<<"\n"; if(te.Max>mx) mx=te.Max,pre[i]=te.val; // cout<<"max="<<te.Max<<" val="<<te.val<<"\n"; } if(mx+1>ans) ans=mx+1,ns=i; //cout<<"i="<<i<<" ans="<<ans<<"\n"; for(int j=0;j<v[i].size();++j){ pii it=v[i][j]; update(1,it.fi,it.se,mx+1,i); } } for(int i=ns;i;i=pre[i]){ u[i]=1; // cout<<"i="<<i<<" \n"; } ans=n-ans; Prin(ans); puts(""); for(int i=1;i<=n;++i){ if(!u[i]) Prin(i),putchar(' '); } return 0; }
这篇关于[Codeforces Round #737 (Div. 2)] D. Ezzat and Grid T2 D1的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-30Fetch / Axios学习:新手入门教程
- 2024-09-30Pre-commit 自动化测试学习:从入门到实践
- 2024-09-29document对象教程:新手入门指南
- 2024-09-29端到端的 AWS DevOps 项目:使用 ECR 和 RDS 的 ECS Fargate 的 CI/CD 管道
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享