ACdream 1101　线段树

题目链接

瑶瑶想要玩滑梯

Time Limit: 10000/5000MS (Java/Others)Memory Limit: 512000/256000KB (Java/Others)

SubmitStatistic Next Problem

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组数据。

第一种操作是常规的区间修改。

第二种操作求区间的LCIS, 显然有三种情况，完全来自左孩子，完全来自右孩子，或者由左孩子和右孩子共同组成。

最体的实现可以参考下面代码。　

Accepted Code:

 /*************************************************************************

     > File Name: 1101.cpp

     > Author: Stomach_ache

     > Mail: sudaweitong@gmail.com

     > Created Time: 2014年08月02日 星期六 13时32分34秒

     > Propose:

  ************************************************************************/

 //线段树

 #include <cmath>

 #include <string>

 #include <cstdio>

 #include <fstream>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define lson(x) (x<<1)

 #define rson(x) ((x<<1)|1)

 const int maxn = ;

 int a[maxn];

 struct node {

       int l, r; //结点区间范围

     //maxo维护区间LCIS长度

     //maxl维护从区间最左开始的上升子序列长度(最左必取)

     //maxr维护以区间最右为止的上升子序列长度(最右必取)

     int maxo, maxl, maxr;

     //区间最左端和最右端的值

     int numl, numr;

     //区间是否完全相同, 也就是LCIS长度为１

     bool s;

     void set(int ll, int rr) {

           l = ll; r = rr; s = false;

     }

 }Tr[maxn<<];

 void pushup(int o) {

       Tr[o].maxo = max(Tr[lson(o)].maxo, Tr[rson(o)].maxo);

     Tr[o].maxl = Tr[lson(o)].maxl;

     Tr[o].maxr = Tr[rson(o)].maxr;

     Tr[o].numl = Tr[lson(o)].numl;

     Tr[o].numr = Tr[rson(o)].numr;

     //是否可合并左孩子和右孩子

     if (Tr[lson(o)].numr < Tr[rson(o)].numl) {

           Tr[o].maxo = max(Tr[o].maxo, Tr[lson(o)].maxr+Tr[rson(o)].maxl);

         //是否可更新maxl

         if (Tr[o].maxl == Tr[lson(o)].r-Tr[lson(o)].l+) {

               Tr[o].maxl += Tr[rson(o)].maxl;

         }

         //是否可更新maxr

         if (Tr[o].maxr == Tr[rson(o)].r-Tr[rson(o)].l+) {

               Tr[o].maxr += Tr[lson(o)].maxr;

         }

     }

 }

 void build(int o, int l, int r) {

       Tr[o].set(l, r);

     if (l == r) {

           Tr[o].maxo = Tr[o].maxr = Tr[o].maxl = ;

         Tr[o].numl = Tr[o].numr = a[l];

         Tr[o].s = true;

         return ;

     }

     int mid = (l + r) / ;

     build(lson(o), l, mid);

     build(rson(o), mid+, r);

     pushup(o);

 }

 void pushdown(int o) {

       if (Tr[o].s) {

           Tr[o].s = false;

           Tr[lson(o)].maxo = Tr[lson(o)].maxl = Tr[lson(o)].maxr = ;

         Tr[lson(o)].numl = Tr[lson(o)].numr = Tr[o].numl;

           Tr[rson(o)].maxo = Tr[rson(o)].maxl = Tr[rson(o)].maxr = ;

         Tr[rson(o)].numl = Tr[rson(o)].numr = Tr[o].numl;

         Tr[lson(o)].s = Tr[rson(o)].s = true;

     }

 }

 void update(int o, int l, int r, int x) {

       if (Tr[o].l >= l && Tr[o].r <= r) {

           Tr[o].maxo = Tr[o].maxl = Tr[o].maxr = ;

         Tr[o].numl = Tr[o].numr = x;

         Tr[o].s = true;

         return ;

     }

     pushdown(o);

     int mid = Tr[lson(o)].r;

     if (l <= mid) update(lson(o), l, r, x);

     if (r > mid) update(rson(o), l, r, x);

     pushup(o);

 }

 int query(int o, int l, int r) {

       if (Tr[o].l >= l && Tr[o].r <= r) {

           return Tr[o].maxo;

     }

     pushdown(o);

     int mid = Tr[lson(o)].r;

     //三种可能构成最优解的情况

     int ansl(), ansr(), anso();

     if (l <= mid) ansl = query(lson(o), l, r);

     if (r > mid) ansr = query(rson(o), l, r);

     if (l <= mid && r > mid) {

         if (Tr[lson(o)].numr < Tr[rson(o)].numl) {

               anso = Tr[lson(o)].maxr + Tr[rson(o)].maxl;

         }

     }

     return max(anso, max(ansl, ansr));

 }

 int main(void) {

       int n, m;

       scanf("%d %d", &n, &m);

     for (int i = ; i <= n; i++) scanf("%d", a + i);

     build(, , n);

     while (m--) {

           char t[];

         //注意输入

         scanf("%s", t);

         if (t[] == 'U') {

               int l, r, x;

             scanf("%d %d %d", &l, &r, &x);

               update(, l, r, x);

         } else {

               int l, r;

             scanf("%d %d", &l, &r);

               printf("%d\n", query(, l, r));

         }

     }

     return ;

 }

巴特西

ACdream 1101　线段树

瑶瑶想要玩滑梯

Problem Description

Input

Output

Sample Input

Sample Output

Hint

最新文章

热门文章

巴特西

ACdream 1101 线段树

瑶瑶想要玩滑梯

Problem Description

Input

Output

Sample Input

Sample Output

Hint

最新文章

热门文章

ACdream 1101　线段树