线段树的单log,2e6,4s,竟然被卡了？？？

虽说线段树里套了个广义矩阵乘法，但是我只留下了有值的位置啊，一次也就5次加法。

2e6 * 线段树的log * 线段树的8倍常数 * 矩阵乘法5倍常数也只有8e8，感觉4s还是比较轻松的啊？？？

搞得最后我跟暴力同分。

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int n,q;
int a[N],lst[N],pos[N];
const int inf=-1000000000;
struct querys
{
    int l,r,id;
}ask[N];
int ans[N];
inline bool cmp(querys x,querys y)
{
    return x.r<y.r;
}
struct Vector
{
    int one,two,thr;
    inline Vector(){one=two=thr=0;}
    inline Vector(int x,int y,int z){one=x,two=y,thr=z;}
    inline Vector operator +(const Vector& y) const
    {
        return (Vector){max(one,y.one),max(two,y.two),max(thr,y.thr)};
    }
}t[N<<2];
struct Matrix
{
    int a00,a11,a21,a22;
    inline Matrix(){a00=a11=a22=0,a21=-1e9;}
    inline void clear(){a00=a11=a22=0,a21=-1e9;}
    inline Vector operator *(const Vector& y) const
    {
        return (Vector){a00+y.one,a11+y.two,max(inf,max(a21+y.two,a22+y.thr))};
    }
    inline Matrix operator *(const Matrix& y) const
    {
        Matrix ans;
        ans.a00=a00+y.a00;
        ans.a11=a11+y.a11;
        ans.a21=max(a21+y.a11,a22+y.a21);
        ans.a22=a22+y.a22;
        ans.a21=ans.a21<0?inf:ans.a21;
        ans.a22=ans.a22<0?inf:ans.a22;
        return ans;
    }
}tag[N<<2];
bitset<N<<2> book;
inline void pushdown(int x)
{
    if(!book[x]) return ;
    book[x<<1]=book[x<<1|1]=1;
    tag[x<<1]=tag[x]*tag[x<<1],tag[x<<1|1]=tag[x]*tag[x<<1|1];
    t[x<<1]=tag[x]*t[x<<1],t[x<<1|1]=tag[x]*t[x<<1|1];
    book[x]=0;
    tag[x].clear();
}
void update(int x,int l,int r,int L,int R,Matrix v)
{
    if(L<=l&&r<=R)
    {
        tag[x]=v*tag[x];
        t[x]=v*t[x];
        book[x]=1;
    }
    else
    {
        pushdown(x);
        int mid=(l+r)>>1;
        if(L<=mid) update(x<<1,l,mid,L,R,v);
        if(mid+1<=R) update(x<<1|1,mid+1,r,L,R,v);
        t[x]=t[x<<1]+t[x<<1|1];
    }
}
int queryc(int x,int l,int r,int pos)
{
    if(l==r) return t[x].one;
    else
    {
        pushdown(x);
        int mid=(l+r)>>1;
        if(pos<=mid) return queryc(x<<1,l,mid,pos);
        else return queryc(x<<1|1,mid+1,r,pos);
    }
}
int queryhis(int x,int l,int r,int L,int R)
{
    if(L<=l&&r<=R) return t[x].thr;
    else
    {
        pushdown(x);
        int mid=(l+r)>>1,k=0;
        if(L<=mid) k=max(k,queryhis(x<<1,l,mid,L,R));
        if(mid+1<=R) k=max(k,queryhis(x<<1|1,mid+1,r,L,R));
        return k;
    }
}
int querymax(int x,int l,int r,int k)
{
    if(t[x].one<k) return t[x].two;
    if(l==r) return 0;
    pushdown(x);
    int mid=(l+r)>>1;
    if(t[x<<1|1].one>=k) return querymax(x<<1|1,mid+1,r,k);
    else return max(t[x<<1|1].two,querymax(x<<1,l,mid,k));
}
signed main()
{
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        lst[i]=pos[a[i]];
        pos[a[i]]=i;
    }
    for(int i=1;i<=q;i++)
        cin>>ask[i].l>>ask[i].r,ask[i].id=i;
    sort(ask+1,ask+1+q,cmp);
    int p=1;
    for(int i=1;i<=n;i++)
    {
        Matrix v;
        v.a11=1;
        if(lst[i]) update(1,1,n,1,lst[i],v);
        v.clear();
        v.a00=v.a11=1,v.a21=0,v.a22=-1e9;
        update(1,1,n,lst[i]+1,i,v);
        while(p<=q&&ask[p].r==i) 
        {
            ans[ask[p].id]=max(queryhis(1,1,n,ask[p].l,ask[p].r),querymax(1,1,n,queryc(1,1,n,ask[p].l)));
            p++;
        }
    }
    for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
    return 0;
}