题目链接：https://www.nowcoder.com/acm/contest/158/B

给你一个长度为 n 的序列 a ，求最长的连续的严格上升区间的长度。
同时会进行 m 次修改，给定 x , y ，表示将 ax 修改为 y ,每次修改之后都要求输出答案。、

思路：开始拿到题准备用线段树的，维护区间的最长连续上升区间，但是区间合并时无法维护。后来NYX在网上找到了模板，线段树做的, (还是要多做题)，当时这道题A了，自己也准备研究别人怎么维护的，因为中间去学习莫比乌斯反演了，所以一直拖到今天。

今天认真研究了别人的代码（看没有注释的代码简直是程序员的***），看懂了大概思路，维护左端为开头的最长连续上升区间的长度ls，右端为结尾的最长连续上升区间的长度rs，本区间的最长连续上升区间的长度s

思考：每做一道题，就觉得对线段树的理解多了一层，自己觉得无法维护的，也是可以维护的，还是题做的太少了，努力刷题，努力进步

//区间合并维护的核心代码
node[1].s=max(node[2].s, node[3].s);
node[1].ls=node[2].ls;
node[1].rs=node[3].rs;

if(a<b)//区间合并处可能产生新的连续上升区间
{

	node[1].s=(node[1].s, node[2].rs+node[3].ls);//新产生连续区间的长度 node[2].rs+node[3].ls

	
	//因为node[2], node[3]都可能是整体连续上升的
	//所以要判断是否更新node[1].ls, node[1].rs
	
	int len=node[fi].r-node[fi].l+1;//本区间长度
    int len_r=len/2;                //右子区间长度
    int len_l=len-len_r;            //左子区间长度
    
	if(node[1].ls==len_l)//左子区间整体上升 
        node[1].ls+=node[3].ls;    

    if(node[fi].rs==len_r)//右子区间整体上升 
        node[1].rs+=node[2].rs;

}

因为我的模板把区间的元素存在结构体中，所以还要维护区间最左边，最右边的元素，所以就重新写了模板，把元素存在一个数组中，这样就可以直接访问了

int mid=(node[i].l+node[i].r)/2;
a[mid]   //左子区间的最右元素a
a[mid+1] //右子区间的最左元素b

代码查询还写了区间查询，而这题查询整个区间，推荐另外一题查询区间的最长的连续的严格上升区间：http://acm.hdu.edu.cn/showproblem.php?pid=3308

#include <bits/stdc++.h>
using namespace std;
#define MAX_NODE 800000
#define MAX 200000
int Max=1<<31;

struct NODE{

    int s, ls, rs;//信息
    int l, r;//区间[l, r]

}node[MAX_NODE];

int f[MAX];//记录节点i的node结构体数组下标f[i]
int a[MAX];

void js(int i, int l, int r)
{
    node[i].l=l;
    node[i].r=r;
    node[i].ls=1;
    node[i].rs=1;
    node[i].s=1;
    if(l==r)
    {
        f[l]=i;
        return;
    }
    int mid=(l+r)/2;

    js(i*2, l, mid);
    js(i*2+1, mid+1, r);
}

void gx(int ri)
{
    if(ri==1)
        return;

    int fi=ri/2;

    node[fi].s=max(node[fi*2].s, node[fi*2+1].s);
    node[fi].ls=node[fi*2].ls;
    node[fi].rs=node[fi*2+1].rs;

    int mid=(node[fi].l+node[fi].r)/2;

    int len=node[fi].r-node[fi].l+1;//本区间长度
    int len_r=len/2;                //右子区间长度
    int len_l=len-len_r;            //左子区间长度

    if(a[mid]<a[mid+1])             //区间合并产生新区间
    {
        node[fi].s=max(node[fi].s, node[fi*2].rs+node[fi*2+1].ls);

        if(node[fi].ls==len_l)
            node[fi].ls+=node[fi*2+1].ls;

        if(node[fi].rs==len_r)
            node[fi].rs+=node[fi*2].rs;

    }
    gx(fi);

}

//len上个区间的最大最长连续上升区间 
//len_r上个区间以右端为结尾的最长连续上升区间
int len, len_r;

void cx(int i, int l, int r)//查询：模拟区间合并操作
{
    if(l==node[i].l&&r==node[i].r)
    {
        len=max(len, node[i].s);

        if(len_r!=0&&a[l-1]<a[l])
        {
            len=max(len, node[i].ls+len_r);
            if(node[i].rs==node[i].r-node[i].l+1)
            {
                len_r=node[i].rs+len_r;
            }
            else
            {
                len_r=node[i].rs;
            }
        }
        else
        {
            len_r=node[i].rs;
        }

        return;
    }

    int mid=(node[i].l+node[i].r)/2;

    if(r<=mid)
        cx(i*2, l, r);
    else if(l>mid)
        cx(i*2+1, l, r);
    else
    {
        cx(i*2, l, mid);
        cx(i*2+1, mid+1, r);
    }

}

int main()
{
    int n, m;
    scanf("%d %d",&n, &m);
    js(1, 1, n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        gx(f[i]);
    }

    len=0, len_r=0;
    cx(1, 1, n);
    cout<<len<<endl;
    while(m--)
    {
        len=0, len_r=0;
        int x, y;
        scanf("%d%d",&x,&y);
        a[x]=y;
        gx(f[x]);
        cx(1, 1, n);
        cout<<len<<endl;
    }

    return 0;
}