HDU 3308 LCIS

Problem Description

Given n integers.
You have two operations:
U A B: replace the Ath number by B. (index counting from 0)
Q A B: output the length of the longest consecutive increasing subsequence (LCIS) in [a, b].

Input

T in the first line, indicating the case number.
Each case starts with two integers n , m(0<n,m<=10 ⁵).
The next line has n integers(0<=val<=10 ⁵).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=10 ⁵)
OR
Q A B(0<=A<=B< n).

Output

For each Q, output the answer.

Sample Input

1
10 10
7 7 3 3 5 9 9 8 1 8 
Q 6 6
U 3 4
Q 0 1
Q 0 5
Q 4 7
Q 3 5
Q 0 2
Q 4 6
U 6 10
Q 0 9

Sample Output

1
1
4
2
3
1
2
5

线段树单点修改区间合并

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 400005;
int n, m, T, l, r;
char s[2];

struct node
{
  int l, lr, lf, r, rl, rf, m;
};

struct ST
{
  int y;
  node f[maxn], ans;
  void merge(node &x, node &lx, node &rx)
  {
    x.lf = lx.lf; x.rf = rx.rf;
    if (lx.lr == lx.r&&lx.rf < rx.lf) x.lr = rx.lr; else x.lr = lx.lr;
    if (rx.rl == rx.l&&rx.lf > lx.rf) x.rl = lx.rl; else x.rl = rx.rl;
    x.m = max(lx.m, rx.m);
    if (lx.rf < rx.lf) x.m = max(x.m, rx.lr - lx.rl + 1);
  }
  void build(int x, int l, int r)
  {
    f[x].l = l;   f[x].r = r;
    if (l == r)
    {
      scanf("%d", &y);
      f[x].lr = f[x].r;
      f[x].rl = f[x].l;
      f[x].lf = f[x].rf = y;
      f[x].m = 1;
    }
    else
    {
      int mid = (l + r) >> 1;
      build(x + x, l, mid);
      build(x + x + 1, mid + 1, r);
      merge(f[x], f[x + x], f[x + x + 1]);
    }
  }
  void insert(int x, int l, int r, int u, int v)
  {
    if (l == r) f[x].lf = f[x].rf = v;
    else
    {
      int mid = (l + r) >> 1;
      if (u <= mid) insert(x + x, l, mid, u, v);
      else insert(x + x + 1, mid + 1, r, u, v);
      merge(f[x], f[x + x], f[x + x + 1]);
    }
  }
  void find(int x, int l, int r, int ll, int rr)
  {
    if (ll <= l&&r <= rr)
    {
      if (ans.l == 0) ans = f[x];
      else
      {
        node t = ans;
        merge(ans, t, f[x]);
      }
    }
    else
    {
      int mid = (l + r) >> 1;
      if (ll <= mid) find(x + x, l, mid, ll, rr);
      if (rr > mid) find(x + x + 1, mid + 1, r, ll, rr);
    }
  }
  int solve(int l, int r)
  {
    ans.l = 0;
    find(1, 1, n, l, r);
    return ans.m;
  }
}st;

int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d%d", &n, &m);
    st.build(1, 1, n);
    while (m--)
    {
      scanf("%s%d%d", s, &l, &r);
      if (s[0] == 'Q') printf("%d\n", st.solve(l + 1, r + 1));
      else st.insert(1, 1, n, l + 1, r);
    }
  } 
  return 0;
}