[Offer收割]编程练习赛51-等差子数列

题目3 : 等差子数列

时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB

描述

给定N个整数A1, A2, ... AN，小Hi会询问你M个问题。

对于每个问题小Hi给出两个整数L和R(L ≤ R)，请你找出[AL, AL+1, AL+2, ... AR]中最长的等差连续子数列，并输出其长度。  

例如[2, 3, 5, 7, 9]中最长的等差连续子数列是[3, 5, 7, 9]长度为4。

输入

第一行包含两个整数N和M。  

第二行包含N个整数A1, A2, ... AN。  

以下M行每行包含两个整数L和R，代表一次询问。

对于30%的数据，1 ≤ N, M ≤ 1000  

对于100%的数据，1 ≤ N, M ≤ 100000 0 ≤ Ai ≤ 10000000

输出

依次对于每个询问输出一个整数，代表答案。

样例输入

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

样例输出

4  
3      

/*
    线段树区间合并
    主要是up操作 和 查询操作
    在线段树中最长子序列可能在左子树也可能在右子树 ，也可能从左子树到右子树。
    所以我们要在树的结构体中增加三个变量(左边的最长区间，右边的最长区间，最长合区间)
    主要是理解左子树的右子树 和 右子树的左子树是如何影响区间的合区间。
    参考了大神代码，写的十分简洁明了。
*/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <queue>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int maxn=1e5+10;
int a[maxn];
struct node
{
    int l,r,mx,ls,rs,sum;
    node() {}
    node(int _l,int _r,int _mx,int _ls,int _rs,int _sum)
    {
        l=_l,r=_r,mx=_mx,ls=_ls,rs=_rs,sum=_sum;
    }
    node operator +(const node&p)const
    {
        node ret;
        ret.mx=max(mx,p.mx);
        ret.sum=sum+p.sum;
        ret.l=l;ret.r=p.r;
        ret.ls=ls;ret.rs=p.rs;
        int cha=a[p.l]-a[r];
        if(sum==ls){
            if(ls==1||(a[r]-a[r-1]==cha)){
                if(p.ls==1||(a[p.l+1]-a[p.l]==cha))
                    ret.ls+=p.ls;
                else
                    ret.ls++;
            }
        }
        if(p.sum==p.rs){
            if(p.rs==1||(a[p.r]-a[p.r-1]==cha)){
                if(rs==1||(a[r]-a[r-1]==cha))
                    ret.rs+=rs;
                else
                    ret.rs++;
            }
        }
        if((rs==1||(a[r]-a[r-1]==cha))&&(p.ls==1||(a[p.l+1]-a[p.l]==cha)))
            ret.mx=max(ret.mx,p.ls+rs);
        if((rs==1||(a[r]-a[r-1]==cha)))
            ret.mx=max(ret.mx,1+rs);
        if((p.ls==1||(a[p.l+1]-a[p.l]==cha)))
            ret.mx=max(ret.mx,1+p.ls);
        return ret;
    }
} st[maxn<<2];
void up(int rt)
{
    st[rt]=st[rt<<1]+st[rt<<1|1];
}
void build(int l,int r,int rt)
{
    if(l==r)
    {
        st[rt]=node(l,l,1,1,1,1);
        return;
    }
    int mid=l+r>>1;
    build(lson);
    build(rson);
    up(rt);
}
node query(int a,int b,int l,int r,int rt)
{
    if(a<=l&&r<=b)return st[rt];
    int mid=l+r>>1;
    node ret(-1,-1,1,1,1,1);
    if(a<=mid) ret=query(a,b,lson);
    if(mid+1<=b)
    {
        if(ret.l==-1) ret=query(a,b,rson);
        else ret=ret+query(a,b,rson);
    }
    return ret;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    build(1,n,1);
    while(m--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",query(l,r,1,n,1).mx);
    }
    return 0;
}