莫隊算法+帶修改莫隊算法

莫隊算法：解決一切區間問題。o(n sqrt(n)).離線一般處理1e4

普通莫隊算法解決無修改區間查詢問題。

//A[i]為輸入數組
//B[i]為每個詢問區間
//MonAns:區間l,r中不同數的個數，不同的題目求的不同，具體該它
//cnt[i]表示區間中數i的個數

#include <cstdio>
#include <algorithm>
using namespace std;

int const SIZE = 30100;
int const BLOCK_SIZE = 200;//分塊大小為接近根号n的整數，這樣容易調試

struct _t{
    int s,e;
    int idx;
};

bool operator  < (_t const&lhs,_t const&rhs){
    int ln = lhs.s / BLOCK_SIZE;
    int rn = rhs.s / BLOCK_SIZE;
    return ln < rn || ( ln == rn && lhs.e < rhs.e );
}

int N,Q;
int A[SIZE];
_t B[SIZE ];
int Ans[SIZE ];
int Cnt[SIZE ] = {0};

void read(){
    scanf("%d",&N);
    for(int i=1;i<=N;++i)scanf("%d",A+i);
    scanf("%d",&Q);
    for(int i=0;i<Q;++i){
        scanf("%d%d",&B[i].s,&B[i].e);
        B[i].idx = i;
    }
}

int MoAns;
inline void insert(int n){
    ++Cnt[n];
    if ( 1 == Cnt[n] ) ++MoAns;
}

inline void remove(int n){
    --Cnt[n];
    if ( 0 == Cnt[n] ) --MoAns;
}

void Mo(){
    sort(B,B+Q);

    int curLeft = 1;
    int curRight = 0;
    MoAns = 0;

    for(int i=0;i<Q;++i){
        while( curRight < B[i].e  ) insert(A[++curRight]);
        while( curLeft > B[i].s ) insert(A[--curLeft]);
        while( curRight > B[i].e ) remove(A[curRight--]);
        while( curLeft < B[i].s ) remove(A[curLeft++]);
        Ans[B[i].idx] = MoAns;
    }
}
int main(){
    //freopen("1.txt","r",stdin);
    read();
    Mo();
    for(int i=0;i<Q;++i)printf("%d\n",Ans[i]);
    return 0;
}
           

G、區間求和

//A[i]為輸入數組
//B[i]為每個詢問區間
//MonAns:區間l,r中不同數的個數，不同的題目求的不同，具體該它
//cnt[i]表示區間中數i的個數

#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;

int const SIZE = 100010;
int const BLOCK_SIZE = 350;//分塊大小為接近根号n的整數，這樣容易調試

struct _t{
    int s,e;
    int idx;
};

bool operator  < (_t const&lhs,_t const&rhs){
    int ln = lhs.s / BLOCK_SIZE;
    int rn = rhs.s / BLOCK_SIZE;
    return ln < rn || ( ln == rn && lhs.e < rhs.e );
}

int N,Q;
int A[SIZE];
_t B[100010];
ll Ans[100010];
int Cnt[100010] = {0};

void read(){
    scanf("%d%d",&N,&Q);
    for(int i=1;i<=N;++i)scanf("%d",A+i);
    for(int i=0;i<Q;++i){
        scanf("%d%d",&B[i].s,&B[i].e);
        B[i].idx = i;
    }
}

ll MoAns;
inline void insert(int n){
    ++Cnt[n];
    //if ( 1 == Cnt[n] ) ++MoAns;
    MoAns+=2LL*Cnt[n]*n-n;
}

inline void remove(int n){
    --Cnt[n];
    //if ( 0 == Cnt[n] ) --MoAns;
    MoAns-=2LL*Cnt[n]*n+n;
}

void Mo(){
    sort(B,B+Q);

    int curLeft = 1;
    int curRight = 0;
    MoAns = 0;

    for(int i=0;i<Q;++i){
        while( curRight < B[i].e  ) insert(A[++curRight]);
        while( curLeft > B[i].s ) insert(A[--curLeft]);
        while( curRight > B[i].e ) remove(A[curRight--]);
        while( curLeft < B[i].s ) remove(A[curLeft++]);
        Ans[B[i].idx] = 1LL*MoAns;
    }
}
int main(){
    read();
    Mo();
    for(int i=0;i<Q;++i)printf("%lld\n",Ans[i]);
    return 0;
}
           

帶單點修改莫隊算法

theme：n個元素，q次詢問：

，num(ai​)代表aia_iai​在這個區間中出現的次數。

//theme：n個元素，q次詢問：l,r區間中a[i]*num[i]之和。num(ai​)代表aia_iai​在這個區間中出現的次數。

#include <cstdio>
#include <list>
#include <algorithm>
using namespace std;
typedef long long ll;

int const SIZE = 10010;
int const BLOCK_SIZE = 300;//分塊大小為接近根号n的整數，這樣容易調試

struct _t{
    int s,e;
    int idx;
    int changedCnt;
}Query[SIZE];

bool operator  < (_t const&lhs,_t const&rhs){
    int la = lhs.s / BLOCK_SIZE;
    int ra = rhs.s / BLOCK_SIZE;
    int lb = lhs.e / BLOCK_SIZE;
    int rb = rhs.e / BLOCK_SIZE;
    return la < ra || ( la == ra && lb < rb )||(la==ra&&lb==rb&&lhs.changedCnt<rhs.changedCnt);
}

struct change_t{
    int pos; //改變的位置
    int newColor;//改變前的值
    int preColor;//改變後的值
}Change[SIZE];

int N,M;//N為元素個數，M為總操作數
int A[SIZE];
int PreColor[SIZE];
int MoAns;
int Cnt[1000100];
int QCnt,CCnt;//查詢、修改的個數(查詢修改從0開始編号)
int Ans[SIZE];
int curLeft,curRight,curChangedCnt;

void read(){
    scanf("%d",&N);
    scanf("%d",&M);
    for(int i=1;i<=N;++i)scanf("%d",A+i),PreColor[i]=A[i];

    QCnt=CCnt=0;

    char cmd;
    int l,r;
    for(int i=0;i<M;++i){
        getchar();
        cmd=getchar();
        scanf("%d%d",&l,&r);
        if(cmd=='Q')
        {
            Query[QCnt].s=l;
            Query[QCnt].e=r;
            Query[QCnt].idx=QCnt;
            Query[QCnt++].changedCnt=CCnt;
        }
        else
        {
            Change[CCnt].preColor=PreColor[l];
            Change[CCnt].pos=l;
            Change[CCnt++].newColor=PreColor[l]=r;
        }
    }
}

inline void insert(int n){
    ++Cnt[n];
    if(1==Cnt[n])
        ++MoAns;
}

inline void remove(int n){
    --Cnt[n];
    if(0==Cnt[n])
        --MoAns;
}

inline void change(int pos,int color)
{
    if(curLeft<=pos&&pos<=curRight)
    {
        remove(A[pos]);
        insert(color);
    }
    A[pos]=color;
}

void Mo(){
    sort(Query,Query+QCnt);

    curLeft = 1;
    curRight = 0;//下标
    curChangedCnt=0;
    MoAns = 0;

    for(int i=0;i<QCnt;++i){

        while(curChangedCnt<Query[i].changedCnt)
            change(Change[curChangedCnt].pos,Change[curChangedCnt].newColor),++curChangedCnt;
        while(curChangedCnt>Query[i].changedCnt)
            --curChangedCnt,change(Change[curChangedCnt].pos,Change[curChangedCnt].preColor);

        while( curRight < Query[i].e  ) insert(A[++curRight]);
        while( curLeft > Query[i].s ) insert(A[--curLeft]);
        while( curRight > Query[i].e ) remove(A[curRight--]);
        while( curLeft < Query[i].s ) remove(A[curLeft++]);
        Ans[Query[i].idx]=MoAns;
    }
}
int main(){
    //freopen("1.txt","r",stdin);
    read();
    Mo();
    for(int i=0;i<QCnt;++i)printf("%d\n",Ans[i]);
    return 0;
}