洛谷AC学校OJ TLE求助

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
const int N=4e6+10,M=1e6,K=1e7+10;
int n,m,a[N],pre[N],lst[N],tot;
pair<int,int> ans[N];
int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;}
struct bitT{
	int t[N];
    void add(int x,int k){while(x<=M)t[x]+=k,x+=x&-x;}
	int sum(int x){int res=0;while(x)res+=t[x],x-=x&-x;return res;}
	int sum(int l,int r){return sum(r)-sum(l-1);}
}bitT;
struct ques{
	int k,a,b,x,p;
	bool operator<(ques b){return k<b.k;}
}q[N>>1];
struct segT{
    int rt[K],t[K],ls[K],rs[K],tot;
    void pushup(int p){t[p]=t[ls[p]]+t[rs[p]];}
    void update(int &p,int l,int r,int x,int v){
        if (!p) p=++tot;
        if (l==r){t[p]+=v;return;}
        int mid=l+r>>1;
        if (x<=mid)
            update(ls[p],l,mid,x,v);
        else
            update(rs[p],mid+1,r,x,v);
        pushup(p);
    }
    int query(int p,int l,int r,int ql,int qr){
        if (!p) return 0;
        if (ql<=l&&r<=qr) return t[p];
        int mid=l+r>>1;
        if (qr<=mid)
            return query(ls[p],l,mid,ql,qr);
        if (ql>mid)
            return query(rs[p],mid+1,r,ql,qr);
        return query(ls[p],l,mid,ql,qr)+query(rs[p],mid+1,r,ql,qr);
    }
}segT;
struct outT{
    void add(int x,int v){
        x++;
        while (x<=M)
            segT.update(segT.rt[x],0,M,v,1),
            x+=x&-x;
    }
    int sum(int x,int a,int b){
        x++;
        int res=0;
        while (x)
            res+=segT.query(segT.rt[x],0,M,a,b),
            x-=x&-x;
        return res;
    }
}outT;
signed main(){
    n=read();m=read();
	for (int i=1;i<=n;i++){
		a[i]=read();
		pre[i]=lst[a[i]];
        lst[a[i]]=i;
	}
	for (int i=1;i<=m;i++){
		int l=read(),r=read(),a=read(),b=read();
		q[++tot]={l-1,a,b,-i,l-1};
		q[++tot]={r,a,b,i,l-1};
	}
	sort(q+1,q+tot+1);
	int x=0;
	for (int i=1;i<=tot;i++){
		while (x<q[i].k)
            x++,
			bitT.add(a[x],1),
            outT.add(pre[x],a[x]);
        int t=abs(q[i].x),w=q[i].x/t;
		ans[t].fi+=w*bitT.sum(q[i].a,q[i].b);
		ans[t].se+=w*outT.sum(q[i].p,q[i].a,q[i].b);
	}
	for (int i=1;i<=m;i++)
        cout<<ans[i].fi<<' '<<ans[i].se<<'\n';
	return 0;
}