rt，一直 T 在第 11 个点，普通的历史和线段树，实在是想不到哪里能优化了/yun

#include<bits/stdc++.h>
#define ll long long
#define N 1500005
#define inf 0x3f3f3f3f
using namespace std;
inline char gc() {
	static const int IN_LEN = 1 << 18 | 1;
	static char buf[IN_LEN], *s, *t;
	return (s == t) && (t = (s = buf) + fread(buf, 1, IN_LEN, stdin)), s == t ? -1 : *s++;
}
ll read(){
    ll x=0,f=1;char ch=gc();
    while(ch<'0' || ch>'9')f=(ch=='-'?-1:f),ch=gc();
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=gc();
    return x*f;
}
void write(ll x){
    if(x<0)x=-x,putchar('-');
    if(x/10)write(x/10);
    putchar(x%10+'0');
}
ll a[N];
struct info{
    ll hissum,sum,t;
    info(ll hissum=0,ll sum=0,ll t=0):hissum(hissum),sum(sum),t(t){}
};
struct tag{
    ll cov,t,et,sum;
    tag(ll cov=0,ll t=0,ll et=0,ll sum=0):cov(cov),t(t),et(et),sum(sum){}
};
inline void apply(info &x,const tag &y,ll l,ll r){
    x.hissum+=x.sum*(y.et-x.t)+y.sum*(r-l+1);
    x.t=y.t;x.sum=(r-l+1)*y.cov;
}
inline info merge(info x,info y){
    if(x.t==inf)return y;
    if(x.t>y.t)swap(x,y);
    x.hissum+=(y.t-x.t)*x.sum;
    y.sum=x.sum+y.sum;y.hissum=x.hissum+y.hissum;return y;
}
inline void merge(tag &x,const tag &y){
    if(x.t==0)return x=y,void();
    if(y.t==0)return;
    x.sum+=x.cov*(y.et-x.t)+y.sum;x.t=y.t;x.cov=y.cov;
}
struct seg{
    ll ls[N<<2],rs[N<<2],tot,l[N<<2],r[N<<2];
    info v[N<<2];tag T[N<<2];
    void build(ll &x,ll L,ll R){
        x=++tot;v[x]=info(0,0,0);l[x]=L;r[x]=R;if(L==R)return;
        ll mid=(L+R)>>1;build(ls[x],L,mid);build(rs[x],mid+1,R);
    }
    void push_down(ll x){
        if(T[x].t==0)return;
        apply(v[ls[x]],T[x],l[ls[x]],r[ls[x]]);apply(v[rs[x]],T[x],l[rs[x]],r[rs[x]]);
        merge(T[ls[x]],T[x]);merge(T[rs[x]],T[x]);T[x].t=0;
    }
    void update(ll x,ll L,ll R,ll val,ll t){
        if(l[x]>=L && r[x]<=R)return apply(v[x],tag(val,t,t,0),l[x],r[x]),merge(T[x],tag(val,t,t,0)),void();
        ll mid=(l[x]+r[x])>>1;push_down(x);
        if(L<=mid)update(ls[x],L,R,val,t);
        if(R>mid)update(rs[x],L,R,val,t);
        v[x]=merge(v[ls[x]],v[rs[x]]);
    }
    ll ask(ll x,ll L,ll R,ll ti){
        if(l[x]>=L && r[x]<=R)return v[x].hissum+(ti+1-v[x].t)*v[x].sum;
        ll ans=0;ll mid=(l[x]+r[x])>>1;push_down(x);
        if(L<=mid)ans+=ask(ls[x],L,R,ti);
        if(R>mid)ans+=ask(rs[x],L,R,ti);
        return ans;
    }
}T;
struct Node{
    ll l,r,opt,num;
    Node(ll l=0,ll r=0,ll opt=0,ll num=0):l(l),r(r),opt(opt),num(num){}
};
vector<Node> Q[N];
ll ans[N],tp,las[N];
Node sta[N];
set<ll> p;
int main(){
    #ifdef EAST_CLOUD
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    #endif
    int n=read(),q=read(),st;
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=q;i++){
        int l=read(),r=read(),x=read(),y=read();
        Q[x-1].push_back(Node(l,r,-1,i));Q[y].push_back(Node(l,r,1,i));
    }
    ll rt;T.build(rt,1,n);p.insert(0);
    for(int i=1;i<=n;i++){
        T.update(rt,i,i,i,i);
        p.insert(i);
        if(las[a[i]]){
            auto it=p.lower_bound(las[a[i]]),itt=p.upper_bound(las[a[i]]);it--;
            T.update(rt,(*it)+1,las[a[i]],*itt,i);
            p.erase(las[a[i]]);
        }
        las[a[i]]=i;
        for(auto v:Q[i])ans[v.num]+=v.opt*T.ask(rt,v.l,v.r,i);
        if((clock()-st)*1.0/CLOCKS_PER_SEC>6.8)write(i);
    }
    for(ll i=1;i<=q;i++)write(ans[i]),putchar('\n');
}