锐客网

  1. 首页 > it技术 > >

线段树|191024省选测试题解

线段树树形dp平面图

【线段树|191024省选测试题解】T1：有n个不相交矩形障碍，求从原点走到某个目标点的最短路，目标点在x轴上
显然矩形的右端点是没用的，我们保留左边即可
显然不会往左走，dp一下是 n 2 n^2 n2的，用扫描线优化一下即可

#include #define pb push_back #define ll long long using namespace std; inline int read(){ int res=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48); ch=getchar(); } return res*f; } const int N=5e5+5,INF=1e9; inline int D(int x1,int y1,int x2,int y2){return abs(x1-x2)+abs(y1-y2); } int n,aim; struct sqr{ int lx,rx,ly,ry; inline bool operator < (const sqr &rhs)const{return lxs; int main(){ n=read(); aim=read(); for(int i=1; i<=n; i++){ int lx=read(),ly=read(),rx=read(),ry=read(); if(lx>rx) swap(lx,rx); if(ly>ry) swap(ly,ry); p[i].lx=lx,p[i].rx=rx,p[i].ly=ly,p[i].ry=ry; } s.insert(info(0,0,0)); sort(p+1,p+n+1); for(int i=1; i<=n; i++){ set::iterator l=s.lower_bound(info(0,p[i].ly,0)); set::iterator r=s.upper_bound(info(0,p[i].ry,0)); int L=INF,R=INF; while(l!=r){ L=min(L,l->dis+D(p[i].lx,p[i].ry,l->x,l->y)); R=min(R,l->dis+D(p[i].lx,p[i].ly,l->x,l->y)); s.erase(l++); } s.insert(info(p[i].lx,p[i].ry,L)); s.insert(info(p[i].lx,p[i].ly,R)); } int ans=INF; for(set::iterator it=s.begin(); it!=s.end(); it++) ans=min(ans,it->dis+D(aim,0,it->x,it->y)); cout<

T2：LOJ火锅盛宴
一个优先队列维护没熟的，一个线段树维护熟的，然后模拟就完了
#include #define pii pair #define pb push_back #define mp make_pair #define ll long long #define fi first #define se second #define db double using namespace std; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline int read(){ char ch=nc(); int sum=0; while(!(ch>='0'&&ch<='9'))ch=nc(); while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc(); return sum; } struct info{ int x,id; info(){} info(int _x,int _id):x(_x),id(_id){} inline bool operator > (const info &rhs)const{return x>rhs.x; } }; int n; const int N=1e5+5; namespace segtree{ struct seg{int l,r,sum; }tr[N<<2]; #define ls tr[k].l #define rs tr[k].r #define mid (ls+rs>>1) inline void build(int k,int l,int r){ ls=l; rs=r; tr[k].sum=0; if(l==r) return; build(k<<1,l,mid); build(k<<1|1,mid+1,r); } inline void modify(int k,int pos){//op 0 ++tr[k].sum; if(ls==rs) return; if(pos<=mid) modify(k<<1,pos); else modify(k<<1|1,pos); } inline int query_min(int k){//op 1 if(!tr[k].sum) return 0; --tr[k].sum; if(ls==rs) return ls; if(tr[k<<1].sum) return query_min(k<<1); else return query_min(k<<1|1); } inline int query_pos(int k,int pos){//op 2 if(!tr[k].sum) return 0; if(ls==rs){--tr[k].sum; return 1; } int res=0; if(pos<=mid) res=query_pos(k<<1,pos); else res=query_pos(k<<1|1,pos); tr[k].sum-=res; return res; } inline int query_seq(int k,int ql,int qr){ //op 3 if(ql>rs || qrmid) return query_seq(k<<1|1,ql,qr); else return query_seq(k<<1,ql,mid)+query_seq(k<<1|1,mid+1,qr); } } using namespace segtree; int w[N]; priority_queue,greater >q; dequeson[N]; inline void file(){freopen("b.in","r",stdin); freopen("b.out","w",stdout); } int main(){ int t=read(); while(t--){ n=read(); build(1,1,n); for(int i=1; i<=n; i++) w[i]=read(),son[i].clear(); while(!q.empty()) q.pop(); int Q=read(); while(Q--){ int t=read(),op=read(); while(q.size() && q.top().x<=t){ int y=q.top().id; modify(1,y); son[y].pop_front(); q.pop(); } if(op==0){ int x=read(); son[x].push_back(t+w[x]); q.push(info(t+w[x],x)); } else if(op==1){ if(!tr[1].sum) puts("Yazid is angry."); else cout<dp[1]) dp[1]=h[y]; } ans=max(ans,val+1); ans=max(ans,dp[0]+val+1); ans=max(ans,dp[0]+dp[1]+val+1); for(int i=head[v]; i; i=nxt[i]){ int y=vis[i]; if(y==fa) continue; if(h[y]!=dp[0]) dfs2(y,v,max(val,dp[0])+1); else dfs2(y,v,max(val,dp[1])+1); } } int main(){ n=read(); for(int i=0; i

    推荐阅读


    上一篇：线段树|[CF377D][线段树][扫描线]Developing Game

    下一篇：杜教筛|191106CSP（NOI（）模拟及NOI（CSP？）模拟题解）