题解区没有 cdq 分治，自己写的分治运行时间有亿点长。

几种实现中，直接移动结构体比记录编号快 7s，然而总用时都在 8s 以上。快读快写、手动归并替换 inplace_merge 都能减少大约 2s 运行时间。

想知道有没有方法能大幅降低常数，或者另一份效率更高的 cdq 分治代码，这里是我的评测记录。

以下代码删除了输入输出部分的优化。

#include<bits/stdc++.h>
using namespace std;
struct Change{int i,pre,opt;}s[3000001],t[3000001];//opt==0 元素 opt<0 容斥减 opt>0 容斥加 i:元素位置
int ans[1000001],pre[1000001];
//给出序列a,询问[l,r]内满足pre[i]<=l-1的i的个数
//差分询问,对[0,l-1][0,r]统计答案后容斥
bool cdq(const Change &x,const Change &y){return x.pre<y.pre;}
inline int abs(int x){return x<0 ? -x:x;}
void cdqsort(int l,int r){
    if(l==r) return;
    int j=l,pos=l,sum=0,mid=l+r>>1;//j:左区间归并进度 sum:左区间已统计元素数量
    cdqsort(l,mid),cdqsort(mid+1,r);
    for(int i=mid+1;i<=r;i++){
        while(j<=mid&&s[j].pre<=s[i].pre) t[pos]=s[j],sum+=s[j].opt==0,++j,++pos;
        if(s[i].opt) ans[abs(s[i].opt)]+=s[i].opt<0 ? -sum:sum;
        t[pos]=s[i],++pos;
    }
    for(int i=j;i<=mid;i++) t[pos]=s[i],++pos;
    for(int i=l;i<=r;i++) s[i]=t[i];
}
bool cmp(const Change &x,const Change &y){return x.i<y.i;}
int main(){
    int n=read();
    for(int i=1;i<=n;i++){
        int x=read();//统计过程和元素值无关
        s[i].pre=pre[x];
        s[i].i=pre[x]=i;
    }
    int m=read();
    for(int i=1;i<=m;i++){
        int l=read(),r=read();
        s[++n].i=l-1;
        s[n].opt=-i,s[n].pre=l-1;
        s[++n].i=r;
        s[n].opt=i,s[n].pre=l-1;
    }
    stable_sort(s+1,s+n+1,cmp);//排序需要稳定
    cdqsort(1,n);
    for(int i=1;i<=m;i++) write(ans[i]);
    if(ob!=ouf) fwrite(ouf,1,ob-ouf,stdout);
    return 0;
}