【bzoj4491】【我也不知道题目名字是什么】【线段树】-白红宇的个人博客

【bzoj4491】【我也不知道题目名字是什么】【线段树】

发布日期：2021-11-16 15:38:42 浏览次数：11 分类：技术文章

本文共 1475 字，大约阅读时间需要 4 分钟。

Description

给定一个序列A[i]，每次询问l,r，求[l,r]内最长子串，使得该子串为不上升子串或不下降子串

Input

第一行n，表示A数组有多少元素

接下来一行为n个整数A[i]

接下来一个整数Q，表示询问数量

接下来Q行，每行2个整数l，r

Output

对于每个询问，求[l,r]内最长子串，使得该子串为不上升子串或不下降子串

Sample Input

9
1 2 3 4 5 6 5 4 3
5
1 6
1 7
2 7
1 9
5 9

Sample Output

6
6
5
6
4

样例解释
五个询问分别对应
[1,6][1,6][2,6][1,6][6,9]

HINT

N,Q<=50000

题解：线段树维护左边上升,下降,权值和右边上升,下降,权值以及区间长,最大值即可。

代码：

#include
    
     #include
     
      #include
      
       #define N 50010using namespace std;struct use{int lup,rup,ldown,rdown,lv,rv,len,mxup,mxdown;}t[N<<2];int n,x,y,a[N],q;use update(use a,use b){  use c;  c.len=a.len+b.len;  c.lv=a.lv;c.rv=b.rv;  c.lup=a.lup;  if (a.lup==a.len&&a.rv<=b.lv) c.lup=a.len+b.lup;  c.ldown=a.ldown;   if (a.ldown==a.len&&a.rv>=b.lv) c.ldown=a.len+b.ldown;  c.rup=b.rup;  if (b.rup==b.len&&b.lv>=a.rv) c.rup=b.len+a.rup;  c.rdown=b.rdown;  if (b.rdown==b.len&&b.lv<=a.rv) c.rdown=b.len+a.rdown;  c.mxup=max(a.mxup,b.mxup);  if (a.rv<=b.lv) c.mxup=max(c.mxup,a.rup+b.lup);  c.mxdown=max(a.mxdown,b.mxdown);  if (a.rv>=b.lv) c.mxdown=max(c.mxdown,a.rdown+b.ldown);  return c;}void build(int k,int l,int r){  int mid=(l+r)>>1;  if (l==r){    t[k].lv=t[k].rv=a[l];    t[k].lup=t[k].rup=t[k].ldown=t[k].rdown=t[k].len=t[k].mxup=t[k].mxdown=1;    return;  }  build(k<<1,l,mid);  build(k<<1|1,mid+1,r);  t[k]=update(t[k<<1],t[k<<1|1]);}use query(int k,int l,int r,int ll,int rr){   if (l==ll&&r==rr){return t[k];}  int mid=(l+r)>>1;  if (rr<=mid) return query(k<<1,l,mid,ll,rr);  else if (mid

转载地址：https://blog.csdn.net/sunshinezff/article/details/51078316 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：【bzoj1877】【SDOI2009】【晨跑】【费用流】

下一篇：【bzoj3990】【SDOI2015】【排序】【dfs】

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！