HihoCoder - 1710

给定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。

Input

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

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

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

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

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

Output

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

Sample Input

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

Sample Output

4  
3

思路：

一下这么多查询操作大概就是线段树题吧。这里假设 $m a x l [i]$ 是第以 $i$ 个数结尾的 $1$ ~ $i$ 最长连续等差序列长度。

那么求 $[l ， r]$ 中最大连续等差序列长度可以用下列方式来求。

找 $[l ， r]$ 中 $m a x l$ 最大的值并记录其对应的id.
如果$ maxl[id]>(id-l+1) $的长度，说明该$ id $的贡献只能为$ (id-l+1)$,然后将该贡献与[id,r]中的最大值比较后取其中最大的即可。
否则 $m a x l [i d] < = (i d - l + 1)$ ，且 $m a x l [i d]$ 就是 $[l, r]$ 的最大连续等差序列长度。

r如果你对上面有疑问可以看下面的解释。

咱们先想一下普通的求解 $[l, r]$ 区间最长连续等差序列长度怎么算的，是不是暴力出在 $[l ， r]$ 区间中每个 $i d$ 所对应的贡献值（在 $[l, i d]$ 的以 $i d$ 为结尾的最长等差序列的长度）。

那么我们上面的两个if else也是利用了这样的规律。

上面的第一种情况即表示贡献值过剩，其对 $[l ， r]$ 区间有效贡献值为 $(i d - l + 1)$ ，那么我们只需找出 $i d$ 右边的最大贡献长度两者取最大值即可。（因为 $i d$ 右边的长度比 $i d$ 小，故id右边的长度一定不跟id左边的数成等差数列。所以 $[i d, r]$ 的 $m a x l$ 一定就是 $i d$ 右区间的最大贡献）。

第二种情况则更容易理解，因为其中最大的贡献都在 $[l ， r]$ 内，故该 $m a x l$ 就是答案。

故我们只需用维护区间所有区间的等差序列最大长度 $m a x l$ 和对应的 $i d$ 即可。

#include<queue>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#define mset(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int maxn=1e5+200;//顶点数量
const int inf=0x3f3f3f3f;
/* 维护以第i个数字结尾的等差数列的最大长度maxl 3.bulid树，pushUp 2.query(l,r)只需查询最大长度的信息即可 如果贡献部分，与右边的做比较 1.线段树每个节点维护区间最大值信息 */
int maxl[maxn],val[maxn],num[maxn];
struct node{
    int maxl,id;
    node(){}
    node(int maxl,int id):maxl(maxl),id(id){}
}maxnode[maxn<<2];
void push_up(int rt){
    if(maxnode[rt<<1].maxl>maxnode[rt<<1|1].maxl)
        maxnode[rt]=maxnode[rt<<1];
    else
        maxnode[rt]=maxnode[rt<<1|1];
}
void bulidTree(int l,int r,int rt){
    if(l==r){
        maxnode[rt].id=l;
        maxnode[rt].maxl=maxl[l];
        return ;
    }
    int m=(l+r)>>1;
    bulidTree(lson);
    bulidTree(rson);
    push_up(rt);
    return ;
}
node query(int L,int R,int l,int r,int rt){
    if(L<=l&&R>=r){
        return maxnode[rt];
    }
    int m=(l+r)>>1;
    node ans(0,0);
    if(L<=m){
        node mid=query(L,R,lson);
        if(mid.maxl>ans.maxl)
            ans=mid;
    }
    if(R>m){
        node mid=query(L,R,rson);
        if(mid.maxl>ans.maxl)
            ans=mid;
    }
    return ans;
}
int main(){
    int n,q;
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;++i) scanf("%d",val+i);
    maxl[1]=1;num[1]=inf;
    for(int i=2;i<=n;++i){
        num[i]=val[i]-val[i-1];
        maxl[i]=num[i]==num[i-1]?maxl[i-1]+1:2;
    }
    bulidTree(1,n,1);
    while(q--){
        int l,r,ans;
        scanf("%d %d",&l,&r);
        node nowAns=query(l,r,1,n,1);
        if(nowAns.maxl<=nowAns.id-l+1){
            ans=nowAns.maxl;
        }
        else{
            ans=nowAns.id-l+1;
            ans=max(ans,query(nowAns.id+1,r,1,n,1).maxl);
        }
        printf("%d\n",ans);
    }
    return 0;
}

最长等差序列长度，线段树

HihoCoder - 1710

思路：