9pts线段树求调

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
int n;
int root;
struct kl{
    int l,r;
}b[N];
int c[N];
int a[N];
struct node{
    int l,r;
    long long sum,add,q;
    int size;
    node(){
        l=r=sum=add=size=q=0;
    }
    void init(int p){
        l=r=p;
        sum=a[p];
    }
}tree[N<<2];
node operator+(const node& l,const node &r){
    node res;
    res.l=l.l;
    res.r=r.r;
    res.sum=l.sum+r.sum;
    return res;
}
inline void bui(int rt){
    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}
inline void color(int l,int r,int rt,int v){
    tree[rt].add+=v;
    tree[rt].sum+=(r-l+1)*v;
}
inline void push_col(int l,int r,int rt){
    if (tree[rt].add!=0){
        int mid=(l+r)>>1;
        color(l,mid,rt<<1,tree[rt].add);
        color(mid+1,r,rt<<1|1,tree[rt].add);
        tree[rt].add=0;
    }
}
inline void change(int l,int r,int rt,int nowl,int nowr,long long v){
    if (nowl<=l&&r<=nowr){
        color(l,r,rt,v);
    }
    push_col(l,r,rt);
    int mid=(l+r)>>1;
    if (nowl<=mid) change(l,mid,rt<<1,nowl,nowr,v);
    if (mid<nowr) change(mid+1,r,rt<<1|1,nowl,nowr,v);
    bui(rt);
}
inline node query(int l,int r,int rt,int nowl,int nowr){
    if (nowl<=l&&r<=nowr){
        return tree[rt];
    }
    push_col(l,r,rt);
    int mid=(l+r)>>1;
    if (nowl<=mid){
        if (mid<nowr) return query(l,mid,rt<<1,nowl,nowr)+query(mid+1,r,rt<<1|1,nowl,nowr);
        else return query(l,mid,rt<<1,nowl,nowr);
    }else return query(mid+1,r,rt<<1|1,nowl,nowr);
}
inline void build(int l,int r,int rt){
    if (l==r){
        tree[rt].init(r);
        tree[rt].size=b[l].r-b[l].l+1;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    bui(rt);
    return;
}
int q;
int main(){
    scanf("%d%d",&n,&q);
    for (int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    int m=1;
    b[1].l=1;
    c[1]=1;
    for (int i=2;i<=n;++i){
        if (a[i]!=a[i-1]){
            b[m].r=i-1;
            b[++m].l=i;
        }
        c[i]=m;
    }
    b[m].r=n;
    build(1,m,1);
    while (q--){
        int x,y;
        scanf("%d%d",&x,&y);
        int l=c[x],r=c[y];
        int anssum=max(b[l].r-x+1,y-b[r].l+1);
        if (l==r){
            anssum=y-x+1;
        }
        if (l+1<=r){
            anssum=max(anssum,query(1,m,1,l+1,r-1).size);
        }
        cout<<anssum<<"\n";
    }
    return 0;
}