本文主要是介绍ACdream P1101 瑶瑶想要玩滑梯，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
瑶瑶想要玩滑梯
Problem Description
众所周知，瑶瑶（tsyao）是个贪玩的萌妹子，特别喜欢闹腾，恰好今天是一个风和日丽的日子，瑶瑶嚷着让姐姐带她去去公园玩滑梯，可是公园的滑梯比较独特，由单位积木搭成，积木是排成一排搭好，每列有xi个积木，共n列。小明能够对积木进行m次操作：
1.U L R yi ： 将[L,R]列的积木高度全都改为yi
2.Q L R ： 查询[L,R]列最长连续上升的列长度(LCIS)
知道[L,R]列最长连续上升的列长度过后，瑶瑶就可以开开心心地玩滑梯啦！
Ps：连续上升的列长度指对于一段合法区间,都有 
。
话说积木是平的，瑶瑶是怎么从高处滑到低处的呢？？作为姐姐也不知道，很想知道吧？你去问她吧。。
Input
第一行 两个整数n，m；
第二行 n个整数，分别为[1,n]区间每列积木个数；
接下来m行为m个操作
Output
输出x行，每行为每次操作2的查询结果。
Sample Input
5 4 2 1 2 3 1 Q 1 4 Q 2 5 U 2 4 3 Q 1 5
Sample Output
3 3 2
Hint
对于 100%的数据，有1 ≤ n ≤ 10^5 , 1 ≤ m ≤ 10^5 , 1 ≤ xi ≤ 10^8。
单组输入，共10组数据。
Source
Manager
不知你是否相信 这是我两年来做线段树第一次使用LAZY标记，以前虽然早就听说过LAZY标记对线段树修改时的优化，但一直以为太简单而没有去重视- -||| 这一次果断自己写了一个果然各种WA，不过最终结局是好的。
此题是一道经典维护线段树+LAZY标记的使用，说真的这题线段树题做的跟DP一样，各种蛋疼。线段树维护五个值，左右端点上的数值，左边这个数取了之后的LIS（最长连续上升子序列）（记为lv），右边这个数取了之后的LIS（rv），以及整条线段的LIS（v），更新区间时的过程相当麻烦，我怕越讲越烦就不赘述了，最好自己想通为什么要维护这五个值以及更新过程，或者看下面的代码~~~。
稍微讲一下LAZY标记的使用，当我们更新某段区间时，不可能把这段区间之下的所有子区间都更新，因为那样是n*n的复杂度，会超时，所以LAZY标记可以解决这一问题，更新大段时，大段先更新，并把lazy标记传递到它的两个子段中，等用到那两个子段时再更新，要用好LAZY标记尚需大量的实践，因为题目不是死的。
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<string>
#include<cstring>
#include<algorithm>
#include<fstream>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<iomanip>
#define rep(i,n) for(i=1;i<=n;i++)
#define MM(a,t) memset(a,t,sizeof(a))
#define INF 1e9
typedef long long ll;
#define mod 1000000007
using namespace std;
int n,m;
int a[100020];
struct aaa{int l,r,v,lv,rv;int lazy;
}xds[400020];
void update(int l,int r,int node,int num){xds[node].lazy=-1;if(l<r){xds[node*2].lazy=num; xds[node*2+1].lazy=num;}xds[node].l=xds[node].r=num;xds[node].v=xds[node].lv=xds[node].rv=1;
}
void pushup(int l,int r,int mid,int node){int v=1;if(l<r){if(xds[node*2].lazy!=-1) update(l,mid,node*2,xds[node*2].lazy);if(xds[node*2+1].lazy!=-1)update(mid+1,r,node*2+1,xds[node*2+1].lazy);} xds[node].l=xds[node*2].l; xds[node].r=xds[node*2+1].r;xds[node].rv=xds[node*2+1].rv; xds[node].lv=xds[node*2].lv;if(xds[node*2+1].l>xds[node*2].r){v=max(v,xds[node*2].rv+xds[node*2+1].lv);if(xds[node*2+1].v==r-mid) xds[node].rv=r-mid+xds[node*2].rv;if(xds[node*2].v==mid-l+1) xds[node].lv=mid-l+1+xds[node*2+1].lv;}v=max(v,max(xds[node*2].v,xds[node*2+1].v));xds[node].v=v;if(v==(r-l+1)){xds[node].lv=r-l+1;xds[node].rv=r-l+1; }
}
void build(int l,int r,int node){xds[node].lazy=-1;if(l==r){xds[node].v=1;xds[node].lv=1;xds[node].rv=1;xds[node].l=a[l];xds[node].r=a[l];}else{int mid=(l+r)/2;build(l,mid,node*2); build(mid+1,r,node*2+1);pushup(l,r,mid,node);}
}
void change(int l,int r,int node,int x,int y,int num){if(xds[node].lazy!=-1) update(l,r,node,xds[node].lazy);if(l==x && r==y){xds[node].lazy=num;update(l,r,node,num);} else{int mid=(l+r)/2;if(x>=mid+1) change(mid+1,r,node*2+1,x,y,num);else if(y<=mid) change(l,mid,node*2,x,y,num);else{change(l,mid,node*2,x,mid,num);change(mid+1,r,node*2+1,mid+1,y,num); } pushup(l,r,mid,node);}
}
aaa query(int l,int r,int node,int x,int y){aaa res;if(xds[node].lazy!=-1) update(l,r,node,xds[node].lazy);if(x==l && y==r){return xds[node];} else{int mid=(l+r)/2;if(x>=mid+1) return query(mid+1,r,node*2+1,x,y);if(y<=mid) return query(l,mid,node*2,x,y);aaa t1=query(l,mid,node*2,x,mid),t2=query(mid+1,r,node*2+1,mid+1,y);int v=1;res.l=t1.l; res.r=t2.r;res.rv=t2.rv; res.lv=t1.lv;if(t2.l>t1.r){v=max(v,t1.rv+t2.lv);if(t2.v==y-mid) res.rv=y-mid+t1.rv;if(t1.v==mid-x+1) res.lv=mid-x+1+t2.lv;}v=max(v,max(t1.v,t2.v));res.v=v;if(v==(y-x+1)){res.lv=y-x+1;res.rv=y-x+1; } return res;}
}
int main()
{int i,j;scanf("%d%d",&n,&m);rep(i,n) scanf("%d",&a[i]);build(1,n,1);getchar();rep(i,m){int l,r,num;char op[100];scanf("%s",op);if(op[0]=='Q'){scanf("%d%d",&l,&r); printf("%d\n",query(1,n,1,l,r).v);}else{scanf("%d%d%d",&l,&r,&num);change(1,n,1,l,r,num);}}return 0;
}
这篇关于ACdream P1101 瑶瑶想要玩滑梯的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
