莫隊總結&bzoj 2038 小Z的襪子

算法簡介

莫隊算法，是一種用于解決序列上的問題的離線算法，可以回答對于區間的詢問，非常bug。

算法流程

先讀入所有的詢問，對詢問的左端點分塊。

在對詢問排序，以左端點的塊編号為第一關鍵字，以右端點為第二關鍵字。

然後周遊詢問，同時維護L，R以及答案：對于目前區間，[l,r]，不斷移動左端點與右端點，直至l==L&&r==R。

算法複雜度

算法複雜度為 O(nn−√) ，可以用意識流跑一遍：

對于同一個塊，R最多移動n次，然而，一共隻有 n−√ 個塊，是以複雜度就是 O(nn−√) 。

對于左端點，先讨論同一個塊中的情況，每次移動至多為 n−√ ，于是總複雜度為 O(nn−√) ，對于不同塊中的情況，隻有 n−√ 個，即使每次 O(n) 也沒關系。

綜上，莫隊算法的複雜度就是 O(nn−√) 。

入門題——小Z的襪子

題目連結

令 Ti 表示數i在 [L,R] 中出現的次數。

P=∑C2iC2R−L+1=∑Ti∗(Ti−1)/2(R−L+1)∗(R−L)/2=∑T2i−∑Ti(R−L+1)∗(R−L)

顯然 ∑Ti =R-L+1，是以隻要求 ∑T2i 就可以了。

這時我們驚奇的發現，似乎把剛學的莫隊算法套上去就可以了！

用 cnti 表示元素i在目前區間中出現的次數。

每次添加一個元素，就往答案中加 (cnti+1)2−cnt2i ，再 cnti++ 這就是剛加入到元素的貢獻。

每次删除一個元素，就減掉 cnt2i−(cnti−1)2 ，再 cnti−− 。

每次操作都是 O(1) 的，是以總複雜度是 O(nn−√) 。

/**************************************************************
    Problem: 
    User: unicornt
    Language: C++
    Result: Accepted
    Time: ms
    Memory: kb
****************************************************************/

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int M=;
typedef long long ll;
struct Query{
    int L,R,id;
}q[M];
int s,col[M];
ll ans[M][],cnt[M];
bool cmp(Query a,Query b){
    if(a.L/s==b.L/s) return a.R<b.R;
    return a.L/s<b.L/s;
}
int gcd(ll a,ll b){
    return a?gcd(b%a,a):b;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    s=(int)sqrt(n);
    for(int i=;i<=n;i++)
        scanf("%d",&col[i]);
    for(int i=;i<m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        q[i]=(Query){a,b,i};
    }
    sort(q,q+m,cmp);
    int L=,R=;
    ll res=;
    for(int i=;i<m;i++){
        while(R<q[i].R){
            R++;
            res+=(cnt[col[R]]+)*(cnt[col[R]]+)-cnt[col[R]]*cnt[col[R]];
            cnt[col[R]]++;
        }
        while(L<q[i].L){
            res-=cnt[col[L]]*cnt[col[L]]-(cnt[col[L]]-)*(cnt[col[L]]-);
            cnt[col[L]]--;
            L++;
        }
        while(R>q[i].R){
            res-=cnt[col[R]]*cnt[col[R]]-(cnt[col[R]]-)*(cnt[col[R]]-);
            cnt[col[R]]--;
            R--;
        }
        while(L>q[i].L){
            L--;
            res+=(cnt[col[L]]+)*(cnt[col[L]]+)-cnt[col[L]]*cnt[col[L]];
            cnt[col[L]]++;
        }
        ans[q[i].id][]=res-R+L-;
        ans[q[i].id][]=LL*(R-L+)*(R-L);
    }
    for(int i=;i<m;i++){
        int G=gcd(ans[i][],ans[i][]);
        ans[i][]/=G;
        ans[i][]/=G;
        if(!ans[i][]) ans[i][]=;
    }
    for(int i=;i<m;i++)
        printf("%lld/%lld\n",ans[i][],ans[i][]);
    return ;
}
           

一些題

codeforces 375D Tree and Queries 題解

codeforces 86D power array題解

hdu 4638 Group 題解