HDU - 3308 LCIS

传送门：HDU - 3308

思路分析

一个节点维护5个主要的值

1. ma 区间最长
2. lma 从左端点开始的最长
3. rma 从右端点开始的最长
4. lsum 左端点的值
5. rsum 右端点的值

样例输入

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

样例输出

1
1
4
2
3
1
2
5

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int N=1e5+10;

struct node {
    int l,r,mid,len,ma,lma,rma,lsum,rsum;
} tree[N<<2];

int a[N];

void merge(node &ans,node &lson,node &rson) {
    ans.ma=max(rson.ma,lson.ma);
    ans.lsum=lson.lsum;
    ans.rsum=rson.rsum;
    if(lson.rsum<rson.lsum)
        ans.ma=max(ans.ma,lson.rma+rson.lma);
    ans.lma=lson.lma;
    if(lson.rsum<rson.lsum && lson.lma==lson.len)
        ans.lma+=rson.lma;
    ans.rma=rson.rma;
    if(lson.rsum<rson.lsum && rson.lma==rson.len)
        ans.rma+=lson.rma;
}

void pp(int x) {
    merge(tree[x],tree[ls],tree[rs]);
}

void build(int x,int l,int r) {
    tree[x].l=l;
    tree[x].r=r;
    tree[x].mid=l+r>>1;
    tree[x].len=r-l+1;
    if(l==r) {
        tree[x].ma=tree[x].lma=tree[x].rma=1;
        tree[x].lsum=tree[x].rsum=a[l];
        return ;
    }
    int mid=tree[x].mid;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pp(x);
}

void change(int x,int pos,int v) {
    if(tree[x].l==pos && tree[x].r==pos) {
        tree[x].lsum=tree[x].rsum=v;
        return ;
    }
    int mid=tree[x].mid;
    if(pos<=mid)
        change(ls,pos,v);
    if(pos>mid)
        change(rs,pos,v);
    pp(x);
}

node query(int x,int l,int r) {
    if(l<=tree[x].l&&tree[x].r<=r) {
        return tree[x];
    }
    int mid=tree[x].mid;
    if(r<=mid) {
        return query(ls,l,r);
    } else if(l>mid) {
        return query(rs,l,r);
    } else {
        node lson,rson,ans;
        lson=query(ls,l,r);
        rson=query(rs,l,r);
        merge(ans,lson,rson);
        return ans;
    }
}


int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int t;
    cin>>t;
    while(t--) {
        int n,m;
        cin>>n>>m;
        for(int i=1; i<=n; i++)
            cin>>a[i];
        build(1,1,n);
        while(m--) {
            char a;
            int l,r;
            cin>>a>>l>>r;
            if(a=='U')
                change(1,l+1,r);
            else
                cout<<query(1,l+1,r+1).ma<<endl;

        }
    }




    return 0;
}