【洛谷2709】小B的詢問（莫隊模闆題）

點此看題面

大緻題意： 有一個長度為 N N N的序列，每個數字在 1 ∼ K 1\sim K 1∼K之間，有 M M M個詢問，每個詢問給你一個區間，讓你求出 ∑ i = 1 K c ( i ) 2 \sum_{i=1}^K c(i)^2 ∑i=1K​c(i)2，其中 c ( i ) c(i) c(i)表示數字 i i i在該區間内的出現次數。

莫隊算法

顯然，這題可以用莫隊算法來做，而這題本身就是莫隊算法的一道模闆題。

L i n k Link Link

莫隊算法詳見部落格莫隊算法學習筆記（一）——普通莫隊

代碼

#include<bits/stdc++.h>
#define N 50000
#define M 50000
using namespace std;
int n,Q,k,a[N+5],pos[N+5],cnt[N+5],ans[M+5];
struct Query
{
    int l,r,pos;
}q[M+5];
inline char tc()
{
    static char ff[100000],*A=ff,*B=ff;
    return A==B&&(B=(A=ff)+fread(ff,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
    x=0;char ch;
    while(!isdigit(ch=tc()));
    while(x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc()));
}
inline void write(int x)
{
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
bool cmp(Query x,Query y)
{
    return pos[x.l]<pos[y.l]||(pos[x.l]==pos[y.l]&&(pos[x.l]&1?x.r<y.r:x.r>y.r));
}
int main()
{
    register int i;
    read(n),read(Q),read(k);
    for(i=1;i<=n;++i) read(a[i]),pos[i]=(i-1)/sqrt(n)+1;//邊讀入，邊将序列分塊
    for(i=1;i<=Q;++i) read(q[i].l),read(q[i].r),q[i].pos=i;//存儲下來每一個詢問
    sort(q+1,q+Q+1,cmp);//将詢問以l所在的塊為第一關鍵字，r的值為第二關鍵字sort一遍
    int L=q[1].l,R=q[1].r;//将L指針和R指針預處理為指向第一個詢問的l和r
    for(i=q[1].l;i<=q[1].r;++i)//暴力求解第一個詢問
    	ans[q[1].pos]-=cnt[a[i]]*cnt[a[i]],++cnt[a[i]],ans[q[1].pos]+=cnt[a[i]]*cnt[a[i]];
    for(i=2;i<=Q;++i)//對每一個詢問依次求解
    {
    	ans[q[i].pos]=ans[q[i-1].pos];
        while(L<q[i].l) ans[q[i].pos]-=cnt[a[L]]*cnt[a[L]],--cnt[a[L]],ans[q[i].pos]+=cnt[a[L]]*cnt[a[L]],++L;//若L小于目前詢問的l，則更新ans，并将L加1
        while(L>q[i].l) --L,ans[q[i].pos]-=cnt[a[L]]*cnt[a[L]],++cnt[a[L]],ans[q[i].pos]+=cnt[a[L]]*cnt[a[L]];//若L大于目前詢問的l，則将L減1，并更新ans（注意，這裡改變L值和更新ans的順序與上一個操作不同）
        while(R>q[i].r) ans[q[i].pos]-=cnt[a[R]]*cnt[a[R]],--cnt[a[R]],ans[q[i].pos]+=cnt[a[R]]*cnt[a[R]],--R;//類似于上面的操作
        while(R<q[i].r) ++R,ans[q[i].pos]-=cnt[a[R]]*cnt[a[R]],++cnt[a[R]],ans[q[i].pos]+=cnt[a[R]]*cnt[a[R]];//類似于上面的操作
    }
    for(i=1;i<=Q;++i) write(ans[i]),putchar('\n');//對每一個答案按照讀入順序輸出
    return 0;
}