Frequent values 倍增

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn=1e5+10;
int a[maxn];
int l[maxn],r[maxn],cnt[maxn]; // 存第i种数字的在原区间左右位置,和出现次数
int pos[maxn]; // 存原区间第i位对应第几种数字
struct note
{
    int left, right, maxx, sum;
} tree[maxn*4];
void pushup(int id)
{
    tree[id].maxx=max(tree[id<<1].maxx,tree[id<<1|1].maxx);
}
void build(int id, int l, int r)
{
    tree[id].left=l;
    tree[id].right=r;
    if(l==r)
        tree[id].maxx=cnt[l];
    else
    {
        int mid=(l+r)/2;
        build(id<<1, l, mid);
        build(id<<1|1, mid+1, r);
        pushup(id);
    }
}
int query(int id, int l, int r)
{
    if(l<=tree[id].left && tree[id].right<=r)
        return tree[id].maxx;
    else
    {
        int maxx=-1e5;
        int mid=(tree[id].left+tree[id].right)/2;
        if(l<=mid) maxx=max(maxx,query(id<<1, l, r));
        if(r>mid) maxx=max(maxx,query(id<<1|1, l, r));
        return maxx;
    }
}
void update(int id, int pos, int val)
{
    if(tree[id].left==tree[id].right)
        tree[id].maxx=val;
    else
    {
        int mid=(tree[id].left+tree[id].right)/2;
        if(pos<=mid)    update(id<<1, pos, val);
        else    update(id<<1|1, pos, val);
        pushup(id);
    }
}

int main()
{
    int n,q;
    while(scanf("%d%d",&n,&q)&&n!=0)
    {
        a[0]=0x3f3f3f3f;
        memset(tree,0,sizeof(tree));
        memset(cnt,0,sizeof(cnt));
        int cntt=0;
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
            if(a[i]!=a[i-1])
            {
                r[cntt]=i-1;
                cnt[++cntt]++;
                l[cntt]=i;
            }
            else
                cnt[cntt]++;
            pos[i]=cntt;
        }
        r[cntt]=n;
        build(1,1,cntt);
//    printf("%d??\n",query(1,3,3));
//    for(int i=1;i<=cntt;i++)
//        printf("%d ",cnt[i]);
//    printf("\n");
        while(q--)
        {
            int left,right;
            scanf("%d%d",&left,&right);
            if(pos[left]==pos[right])
            {
                printf("%d\n",right-left+1);
                continue;
            }
            int maxx;
            maxx=max(r[pos[left]]-left+1,right-l[pos[right]]+1);
            int z1=pos[left];
            int z2=pos[right];
//        printf("%d %d\n",r[pos[left]]-left+1,right-l[pos[right]]+1);
            if((z2-z1)>1)
            {
                maxx=max(maxx,query(1,z1+1,z2-1));
//            printf("z%d %d %d\n",z1+1,z2-1,query(1,z1+1,z2-1));
            }
            printf("%d\n",maxx);
        }
    }
}