如题，复杂度 $O(n \log n)$ 但是在第 $6$ 个点被卡常了

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define lowbit(x) (x&-(x))
using namespace std;
namespace IO{
	const int SIZE=1<<21;
	static char ibuf[SIZE],obuf[SIZE],*iS,*iT,*oS=obuf,*oT=oS+SIZE-1;
    int qr;
    char qu[55],c;
    bool f;
	#define getchar() (IO::iS==IO::iT?(IO::iT=(IO::iS=IO::ibuf)+fread(IO::ibuf,1,IO::SIZE,stdin),(IO::iS==IO::iT?EOF:*IO::iS++)):*IO::iS++)
	#define putchar(x) *IO::oS++=x,IO::oS==IO::oT?flush():0
	#define flush() fwrite(IO::obuf,1,IO::oS-IO::obuf,stdout),IO::oS=IO::obuf
	#define puts(x) IO::Puts(x)
	template<typename T>
    inline void read(T&x){
    	for(f=1,c=getchar();c<48||c>57;c=getchar())f^=c=='-';
    	for(x=0;c<=57&&c>=48;c=getchar()) x=(x<<1)+(x<<3)+(c&15); 
    	x=f?x:-x;
    }
    template<typename T>
    inline void write(T x){
        if(!x) putchar(48); if(x<0) putchar('-'),x=-x;
        while(x) qu[++qr]=x%10^48,x/=10;
        while(qr) putchar(qu[qr--]);
    }
    inline void Puts(const char*s){
    	for(int i=0;s[i];i++)
			putchar(s[i]);
		putchar('\n');
	}
	struct Flusher_{~Flusher_(){flush();}}io_flusher_;
}
using IO::read;
using IO::write;
const int maxn = 1e6+14;
const int inf = 1e9+7;
int tr[maxn*3+1],tag[maxn*3+1]; 
inline void pushdown(int cur){
    tr[cur<<1]=min(tr[cur<<1],tag[cur]);
    tr[cur<<1|1]=min(tr[cur<<1|1],tag[cur]);
    tag[cur<<1]=min(tag[cur<<1],tag[cur]);
    tag[cur<<1|1]=min(tag[cur<<1|1],tag[cur]);
    tag[cur]=inf;
}
inline void pushup(int cur){
    tr[cur]=min(tr[cur<<1],tr[cur<<1|1]);
}
inline void update(int cur,int lt,int rt,int l,int r,int v){
    if(lt>rt) return ;
    if(l>rt||r<lt) return;
    if(l<=lt&&rt<=r){
        tr[cur]=min(tr[cur],v);
        tag[cur]=min(tag[cur],v);
        return ;
    }
    int mid=(lt+rt)>>1;
    pushdown(cur);
    update(cur<<1,lt,mid,l,r,v);
    update(cur<<1|1,mid+1,rt,l,r,v);
    pushup(cur);
}
inline int query(int cur,int lt,int rt,int l,int r){
    if(l>rt||r<lt) return inf;
    if(l<=lt&&rt<=r) return tr[cur];
    int mid=(lt+rt)>>1;
    pushdown(cur);
    return min(query(cur<<1,lt,mid,l,r),query(cur<<1|1,mid+1,rt,l,r));
}
int Tr[maxn*3+1],Tag[maxn*3+1]; 
inline void Pushdown(int cur){
    Tr[cur<<1]=max(Tr[cur<<1],Tag[cur]);
    Tr[cur<<1|1]=max(Tr[cur<<1|1],Tag[cur]);
    Tag[cur<<1]=max(Tag[cur<<1],Tag[cur]);
    Tag[cur<<1|1]=max(Tag[cur<<1|1],Tag[cur]);
    Tag[cur]=0;
}
inline void Pushup(int cur){
    Tr[cur]=max(Tr[cur<<1],Tr[cur<<1|1]);
}
inline void Update(int cur,int lt,int rt,int l,int r,int v){
    if(lt>rt) return ;
    if(l>rt||r<lt) return;
    if(l<=lt&&rt<=r){
        Tr[cur]=max(Tr[cur],v);
        Tag[cur]=max(Tag[cur],v);
        return ;
    }
    int mid=(lt+rt)>>1;
    Pushdown(cur);
    Update(cur<<1,lt,mid,l,r,v);
    Update(cur<<1|1,mid+1,rt,l,r,v);
    Pushup(cur);
}
inline int Query(int cur,int lt,int rt,int l,int r){
    if(l>rt||r<lt) return 0;
    if(l<=lt&&rt<=r) return Tr[cur];
    int mid=(lt+rt)>>1;
    Pushdown(cur);
    return max(Query(cur<<1,lt,mid,l,r),Query(cur<<1|1,mid+1,rt,l,r));
}
int w[maxn],a[maxn],n,q;
int lst[maxn];
int b[maxn];
int L[maxn],R[maxn];
vector<int> col[maxn];
int cnt;
int answer[maxn];
struct Node{
	Node(int L,int R,int ID,int OP){
		l=L,r=R,id=ID,op=OP;
	}
	int l,r,id,op;
};
int tree[maxn];
inline void add(int x){
	while(x<=n) tree[x]++,x+=lowbit(x);
}
inline int pre(int x){
	int res=0;
	while(x>0) res+=tree[x],x-=lowbit(x);
	return res;
}
vector<Node> Q[maxn];
int f[maxn];
int main(){
	read(n);
	read(q);
	for(int i=1;i<=n;i++){
		read(a[i]);	
	}
	for(int i=1;i<=n;i++){
		col[a[i]].push_back(i);
		if(lst[a[i]]==0){
			w[i]=0;
		}
		else{
			w[i]=-1;
		}
		lst[a[i]]=i;
	}
	for(int i=1;i<=n;i++){
		int lst=0;
		for(int x:col[i]){
			if(lst==0) w[x]=0;
			else{
				w[x]=Query(1,1,n,lst,x);
				if(w[x]==0) w[x]=-1;
			}
			lst=x;
			
		}
		for(int x:col[i]) Update(1,1,n,x,x,a[x]);
	}
	for(int i=1;i<=n;i++){
		if(col[i].size()==0){
			L[i]=n+1;
			R[i]=0;
			continue;
		}
		L[i]=cnt+1;
		for(int x:col[i]) b[++cnt]=w[x],f[cnt]=x;
		R[i]=cnt;
	}
	for(int i=0;i<(maxn*3);i++) tr[i]=tag[i]=inf;
	for(int i=0;i<(maxn*3);i++) Tr[i]=Tag[i]=0;	
	for(int i=1;i<=n;i++){
		update(1,1,n,i,i,L[i]);
		Update(1,1,n,i,i,R[i]);
	}
	for(int i=1;i<=q;i++){
		int cl,cr;
		read(cl);
		read(cr);
		int L=query(1,1,n,cl,cr),R=Query(1,1,n,cl,cr);
		if(L>R) continue;
		Q[L-1].push_back(Node(cl,cr,i,-1));
		Q[R].push_back(Node(cl,cr,i,1));
	}
	int sum=0;
	for(int i=1;i<=n;i++){
		if(w[f[i]]==0) sum++;
		else if(w[f[i]]==-1) sum=sum;
		else add(w[f[i]]);
		for(Node now:Q[i]){
			answer[now.id]+=now.op*(sum+(pre(now.r)-pre(now.l-1)));
		}
	}
	for(int i=1;i<=q;i++) write(answer[i]),putchar('\n');
	return 0;
}
/*
10 1
1 6 2 3 2 6 3 10 1 2
3 6
*/