C63 可持久化线段树 P3939 数颜色

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
#define mid ((l+r)>>1)
int a[N];
struct treenode{int ls,rs,siz;}tr[N*25];int trlen,rt[N];

void change(int &now, int l, int r, int p, int k)// 点修
{ 
    if(!now)now=++trlen;
    tr[now].siz+= k;
    if(l==r){return;}
    if(p<=mid) change(lc(now), l, mid, p, k);
    else       change(rc(now), mid + 1, r, p, k);
}
int query(int now, int l, int r, int x, int y)// 区查
{ 
    if(x<=l && r<=y)return tr[now].siz;
    int s=0;
    if(x<=mid)s+= query(lc(now), l, mid, x, y);
    if(y>mid) s+= query(rc(now), mid+1, r, x, y);
    return s;
}
int main()
{
    int n,m;scanf("%d%d", &n, &m);
    trlen=0;memset(rt,0,sizeof(rt));
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),change(rt[a[i]],1,n,i,1);

    for(int i=1,op,l,r,x;i<=m;i++)
    {
        scanf("%d",&op);
        if(op==2)
        {
            scanf("%d",&x); 
            change(rt[a[x]],1,n,x,-1);
            change(rt[a[x+1]],1,n,x+1,-1);
            change(rt[a[x]],1,n,x+1,1);
            change(rt[a[x+1]],1,n,x,1);
            swap(a[x],a[x+1]);
        }
        else
        {
            scanf("%d%d%d",&l,&r,&x);
            printf("%d\n", query(rt[x], 1, n, l, r));
        }
    }
    return 0;
}

C63 可持久化线段树 P3939 数颜色

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
#define mid ((l+r)>>1)
int a[N];
struct treenode{int ls,rs,siz;}tr[N*25];int trlen,rt[N];

void change(int &now, int l, int r, int p, int k)// 点修 { if(!now)now=++trlen; tr[now].siz+= k; if(l==r){return;} if(p<=mid) change(lc(now), l, mid, p, k); else change(rc(now), mid + 1, r, p, k); } int query(int now, int l, int r, int x, int y)// 区查 { if(x<=l && r<=y)return tr[now].siz; int s=0; if(x<=mid)s+= query(lc(now), l, mid, x, y); if(y>mid) s+= query(rc(now), mid+1, r, x, y); return s; } int main() { int n,m;scanf("%d%d", &n, &m); trlen=0;memset(rt,0,sizeof(rt)); for(int i=1;i<=n;i++)scanf("%d",&a[i]),change(rt[a[i]],1,n,i,1);

for(int i=1,op,l,r,x;i<=m;i++)
{
    scanf("%d",&op);
    if(op==2)
    {
        scanf("%d",&x); 
        change(rt[a[x]],1,n,x,-1);
        change(rt[a[x+1]],1,n,x+1,-1);
        change(rt[a[x]],1,n,x+1,1);
        change(rt[a[x+1]],1,n,x,1);
        swap(a[x],a[x+1]);
    }
    else
    {
        scanf("%d%d%d",&l,&r,&x);
        printf("%d\n", query(rt[x], 1, n, l, r));
    }
}
return 0;

}</pre>