莫队

本质上是双指针加分块，可在 $O(n\sqrt{m})$ 的时间复杂度下解决大部分区间查询问题，比线段树好写。

板子部分：

//全局作用域该初始化的东西
const int MAXN=1e5+5;
struct Mo{
    int l,r,i;
}ask[MAXN];//用于记录询问
int pos[MAXN];//用于记录所属块（优化sort用的）
ll ans[MAXN];//用于记录答案
ll res;//用于传递当前查询的答案
void ADD(int x){//区间加入新元素时更新res用的函数
    
}
void SUB(int x){//区间删除元素时更新res用的
    
}

//solve()函数内该写的东西
void solve(){
    CIN(n);CIN(q);
    int siz=sqrt(n);//根号分块
    FOR(i,1,n){cin>>a[i];pos[i]=i/siz;}//读入数据时顺便初始化一下块信息
    
    FOR(i,1,q){//强制离线
        cin>>ask[i].l>>ask[i].r;
        ask[i].i=i;
    }
    sort(ask+1,ask+1+q,[&](Mo a,Mo b){//按块排序，归属同一块的比较右端点大小，不同块的比较快位置
        return pos[a.l]==pos[b.l]?a.r<b.r:pos[a.l]<pos[b.l];
    });

    int l=1,r=0;//依次处理排序后的询问
    FOR(i,1,q){
        while(ask[i].l<l)ADD(--l);//非常板的部分，理解记忆即可
        while(ask[i].l>l)SUB(l++);
        while(ask[i].r>r)ADD(++r);
        while(ask[i].r<r)SUB(r--);
        ans[ask[i].i]=res;//收集答案
    }

    FOR(i,1,q)cout<<ans[i]<<ET;//输出答案，注意题目格式要求
}

举例： 洛谷P2709 小B的询问

#include<iostream>
#include<vector>
#include<cmath>
#include<set>
#include<array>
#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
#define ET '\n'
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define rFOR(i,a,b) for(ll i=(a);i>=(b);i--)
//趋向for循环，一般情况别用，规定方向时会跳出的循环在这里不会跳出
#define rep(i,a,b) for(ll i=(a);i!=(b)+2*(a<b)-1;i+=2*(a<b)-1)
#define CIN(a) ll a;cin>>a
#define DCIN(a) ld a;cin>>a
#define SCIN(a) string a;cin>>a
#define CA cout<<ans<<ET
#define CY cout<<"YES"<<ET
#define CN cout<<"NO"<<ET
#define max(a,b) ((a>b)?(a):(b))
#define min(a,b) ((a<b)?(a):(b))
std::mt19937 myrand(time(0));
ll rnd(ll l, ll r) {return std::uniform_int_distribution<ll>(l, r)(myrand);}
//没有C++20就不能用ranges了//CF又可以用C++20了，封印解除
#define PP(l,r,CK) *ranges::partition_point(ranges::iota_view((l),(r)+1),(CK))
int M=1e9+7;
inline ll MO(ll x){return (x%M+M)%M;}
string ANS[2]={"No\n","Yes\n"};
const int MAXN=1e5+5;

int cnt[MAXN],a[MAXN];//使用cnt作为一个桶记录元素出现次数

struct Mo{
    int l,r,i;
}ask[MAXN];
int pos[MAXN];
ll ans[MAXN];
ll res;
void ADD(int x){
    res-=cnt[a[x]]*cnt[a[x]];//先从res答案中剔除未修改部分
    cnt[a[x]]++;//再加回来
    res+=cnt[a[x]]*cnt[a[x]];
}
void SUB(int x){
    res-=cnt[a[x]]*cnt[a[x]];
    cnt[a[x]]--;
    res+=cnt[a[x]]*cnt[a[x]];
}

void solve(){
    CIN(n);CIN(q);CIN(k);
    int siz=sqrt(n);
    FOR(i,1,n){cin>>a[i];pos[i]=i/siz;}
    
    FOR(i,1,q){
        cin>>ask[i].l>>ask[i].r;
        ask[i].i=i;
    }
    sort(ask+1,ask+1+q,[&](Mo a,Mo b){
        return pos[a.l]==pos[b.l]?a.r<b.r:pos[a.l]<pos[b.l];
    });

    int l=1,r=0;
    FOR(i,1,q){
        while(ask[i].l<l)ADD(--l);
        while(ask[i].l>l)SUB(l++);
        while(ask[i].r>r)ADD(++r);
        while(ask[i].r<r)SUB(r--);
        ans[ask[i].i]=res;
    }

    FOR(i,1,q)cout<<ans[i]<<ET;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //pre();
    //CIN(t);while(t--)
    solve();
    return 0;
}

洛谷P1494 小Z的袜子

#include<iostream>
#include<vector>
#include<cmath>
#include<set>
#include<array>
#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
#define ET '\n'
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define rFOR(i,a,b) for(ll i=(a);i>=(b);i--)
//趋向for循环，一般情况别用，规定方向时会跳出的循环在这里不会跳出
#define rep(i,a,b) for(ll i=(a);i!=(b)+2*(a<b)-1;i+=2*(a<b)-1)
#define CIN(a) ll a;cin>>a
#define DCIN(a) ld a;cin>>a
#define SCIN(a) string a;cin>>a
#define CA cout<<ans<<ET
#define CY cout<<"YES"<<ET
#define CN cout<<"NO"<<ET
#define max(a,b) ((a>b)?(a):(b))
#define min(a,b) ((a<b)?(a):(b))
std::mt19937 myrand(time(0));
ll rnd(ll l, ll r) {return std::uniform_int_distribution<ll>(l, r)(myrand);}
//没有C++20就不能用ranges了//CF又可以用C++20了，封印解除
#define PP(l,r,CK) *ranges::partition_point(ranges::iota_view((l),(r)+1),(CK))
int M=1e9+7;
inline ll MO(ll x){return (x%M+M)%M;}
string ANS[2]={"No\n","Yes\n"};

const int MAXN=5e4+5;
ll a[MAXN];
int pos[MAXN];
int cnt[MAXN];
pair<int,int> ans[MAXN];int res;
struct Mo{
    int l,r,i;
}ask[MAXN];

void ADD(int x){
    res-=(cnt[a[x]])*(cnt[a[x]]-1)/2;
    cnt[a[x]]++;
    res+=(cnt[a[x]])*(cnt[a[x]]-1)/2;
}
void SUB(int x){
    res-=(cnt[a[x]])*(cnt[a[x]]-1)/2;
    cnt[a[x]]--;
    res+=(cnt[a[x]])*(cnt[a[x]]-1)/2;
}

void print(ll a,ll b){
    b=b*(b-1)/2;
    if(a==0)cout<<"0/1\n";
    else {
        ll d=__gcd(a,b);
        cout<<a/d<<"/"<<b/d<<ET;
    }
}

void solve(){
    CIN(n);CIN(m);
    int siz=sqrt(n);
    FOR(i,1,n){cin>>a[i];pos[i]=i/siz;}

    FOR(i,1,m){
        cin>>ask[i].l>>ask[i].r;ask[i].i=i;
    }

    sort(ask+1,ask+1+m,[&](Mo a,Mo b){
        return pos[a.l]==pos[b.l]?a.r<b.r:pos[a.l]<pos[b.l];
    });

    int l=1,r=0;
    FOR(i,1,m){
        while(ask[i].l<l)ADD(--l);
        while(ask[i].r>r)ADD(++r);
        while(ask[i].l>l)SUB(l++);
        while(ask[i].r<r)SUB(r--);
        ans[ask[i].i]={res,ask[i].r-ask[i].l+1};
    }
    FOR(i,1,m)print(ans[i].first,ans[i].second);
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //pre();
    //CIN(t);while(t--)
    solve();
    return 0;
}

待填坑：带修莫队，回滚莫队，树上莫队，二次离线莫队

参考博客：

关于莫队

超全的莫队算法一遍过