P3939 数颜色 线段树动态开点

luogu P3939

水。直接对每种颜色开个权值线段树即可，注意动态开点。

#include <cstdio>

#include <algorithm>

#define MAXN 300003

#define MAXM MAXN*30

#define mid ((l+r)>>1)

inline void myswap(int &a, int &b){

    int t=a;a=b;b=t;

}

int tre[MAXM],lson[MAXM],rson[MAXM],tot;

void change(int &cur, int l, int r, int p, int val){

    if(cur==0) cur=++tot;

    tre[cur]+=val;

    if(l==r) return;

    if(p<=mid) change(lson[cur], l, mid, p, val);

    if(mid<p) change(rson[cur], mid+1, r, p, val);

}

int query(int cur, int l, int r, int ql, int qr){

    if(cur==0) return 0;

    if(ql<=l&&r<=qr) return tre[cur];

    int res=0;

    if(ql<=mid) res+=query(lson[cur], l, mid, ql, qr);

    if(mid<qr) res+=query(rson[cur], mid+1, r, ql, qr);

    return res;

}

int n,m;

int rot[MAXN];

int col[MAXN];

inline int read(){

    char ch=getchar();int s=0;

    while(ch<'0'||ch>'9') ch=getchar();

    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();

    return s;

}

int main(){

    n=read(),m=read();

    for(int i=1;i<=n;++i){

        col[i]=read();

        change(rot[col[i]], 1, n, i, 1);

    }

    while(m--){

        int opt;

        opt=read();

        if(opt==1){

            int l=read(),r=read(),c=read();

            printf("%d\n", query(rot[c], 1, n, l, r));

        }else{

            int x=read();

            change(rot[col[x]], 1, n, x, -1);

            change(rot[col[x+1]], 1, n, x+1, -1);

            change(rot[col[x]], 1, n, x+1, 1);

            change(rot[col[x+1]], 1, n, x, 1);

            myswap(col[x], col[x+1]);

        }

    }

    return 0;

}