做网站的相关协议,vmware云平台,wordpress企业博客主题,怎么做淘宝客导购网站推广题面#xff1a;P2894 [USACO08FEB]酒店Hotel 题解#xff1a;和基础的线段树操作差别不是很大#xff0c;就是在传统的线段树基础上多维护一段区间最长的合法前驱#xff08;h_#xff09;#xff0c;最长合法后驱#xff08;t_#xff09;#xff0c;一段中最长的合… 题面P2894 [USACO08FEB]酒店Hotel 题解和基础的线段树操作差别不是很大就是在传统的线段树基础上多维护一段区间最长的合法前驱h_最长合法后驱t_一段中最长的合法区间mx。询问时由于查询的是最左边的合法端点所以要从左到中间到右边依次考虑情况。 代码 1 #includecstdio2 #includecstring3 #includeiostream4 #define max(a,b) ((a)(b)?(a):(b))5 using namespace std;6 const int maxn500005,maxm500005;7 int N,M,o,D,X,ans;8 inline int rd(){9 int x0;char cgetchar();
10 while(c0||c9)cgetchar();
11 while(c0c9){xx*10c-0;cgetchar();}
12 return x;
13 }
14 struct Tree{
15 int l,r,lazy,h_,t_,mx;
16 }t[maxn2];
17 inline void Pushup(int x){
18 int lsx1,rsx1|1;
19 if(t[ls].r-t[ls].l1t[ls].mx)t[x].h_t[ls].mxt[rs].h_;else t[x].h_t[ls].h_;
20 if(t[rs].r-t[rs].l1t[rs].mx)t[x].t_t[rs].mxt[ls].t_;else t[x].t_t[rs].t_;
21 t[x].mxmax(t[ls].mx,t[rs].mx);
22 t[x].mxmax(t[x].mx,t[ls].t_t[rs].h_);
23 return;
24 }
25 inline void Build(int x,int l,int r){
26 t[x].ll;t[x].rr;t[x].lazy-1;
27 if(lr){
28 t[x].h_t[x].t_t[x].mx1;
29 return;
30 }
31 int mid(lr)1;
32 Build(x1,l,mid);Build(x1|1,mid1,r);
33 Pushup(x);
34 return;
35 }
36 inline void Pushdown(int x){
37 if(t[x].lazy0){
38 int kt[x].lazy,lsx1,rsx1|1;t[x].lazy-1;
39 if(k1){
40 t[ls].h_t[ls].t_t[ls].mx0;
41 t[rs].h_t[rs].t_t[rs].mx0;
42 }
43 else{
44 t[ls].h_t[ls].t_t[ls].mxt[ls].r-t[ls].l1;
45 t[rs].h_t[rs].t_t[rs].mxt[rs].r-t[rs].l1;
46 }
47 t[ls].lazyt[rs].lazyk;
48 }
49 return;
50 }
51 inline int Solve(int x,int d){
52 int lsx1,rsx1|1,lt[x].l,rt[x].r;
53 if(r-l1t[x].mxt[x].mxd)return l;
54 Pushdown(x);
55 if(t[ls].mxd)return Solve(ls,d);
56 if(t[ls].t_t[rs].h_d)return (t[ls].r-t[ls].t_1);
57 if(t[rs].mxd)return Solve(rs,d);
58 return 0;
59 }
60 inline void Update(int x,int ql,int qr,int o){
61 int lt[x].l,rt[x].r;
62 if(qllrqr){
63 if(o1)t[x].h_t[x].t_t[x].mx0;
64 else t[x].h_t[x].t_t[x].mxr-l1;
65 t[x].lazyo;
66 return;
67 }
68 int mid(lr)1,lsx1,rsx1|1;
69 Pushdown(x);
70 if(qlmid)Update(ls,ql,qr,o);
71 if(qrmid)Update(rs,ql,qr,o);
72 Pushup(x);
73 return;
74 }
75 inline void write(int x){
76 char a[12];int len0;
77 for(;x;x/10)a[len]x%10;
78 if(!len)putchar(0);
79 else while(len)putchar(a[--len]0);
80 putchar(\n);
81 }
82 int main(){
83 Nrd();Mrd();
84 Build(1,1,N);
85 while(M--){
86 ord();
87 if(o1){
88 Drd();
89 ansSolve(1,D);
90 write(ans);
91 if(ans)Update(1,ans,ansD-1,1);//1表示有住人
92 }
93 else{
94 Xrd();Drd();
95 Update(1,X,XD-1,0);
96 }
97 }
98 return 0;
99 } //我为了卡常加入了快速读入和快速输出实际食用代码时完全可以无视。 ByAlenaNuna 转载于:https://www.cnblogs.com/AlenaNuna/p/10357986.html
