bzoj2120: 数颜色（BIT套主席树+set/分块）

时间：2021-12-24 22:00:07

　　带修改的 HH的项链。

　　带修改考虑用BIT套主席树，查区间里有几个不同的数用a[i]上次出现的位置pre[i]<l的数有几个来算就好了。

　　考虑怎么修改。修改i的时候，我们需要改变i同颜色的后继的pre，加入新的颜色，并且找到i在新颜色中的前驱后继，更改自己的pre和在新颜色中后继的pre，于是用一个set来维护每种颜色的前驱后继就好了。

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<set>

using namespace std;

const int maxn=,inf=1e9;

struct poi{int sum,lt,rt;}tree[maxn<<];

int n,m,sz,N,x,delta;

int a[maxn],b[maxn],q1[maxn],q2[maxn],root[maxn],pos[maxn];

char ch[maxn][];

set<int>s[maxn];

set<int>::iterator pre,it,last;

inline void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

inline int lowbit(int x){return x&-x;}

void update(int &x,int l,int r,int cx,int delta)

{

    tree[++sz]=tree[x];tree[sz].sum+=delta;x=sz;

    if(l==r)return;

    int mid=(l+r)>>;

    if(cx<=mid)update(tree[x].lt,l,mid,cx,delta);

    else update(tree[x].rt,mid+,r,cx,delta);

}

int query(int x,int l,int r,int cl,int cr)

{

    if(cl<=l&&r<=cr)return tree[x].sum;

    int mid=(l+r)>>,ret=;

    if(cl<=mid)ret+=query(tree[x].lt,l,mid,cl,cr);

    if(cr>mid)ret+=query(tree[x].rt,mid+,r,cl,cr);

    return ret;

}

int main()

{

    read(n);read(m);

    for(int i=;i<=n;i++)read(a[i]),b[++N]=a[i];

    for(int i=;i<=m;i++)

    {

        scanf("%s",ch[i]);read(q1[i]);read(q2[i]);

        if(ch[i][]=='R')b[++N]=q2[i];

    }

    sort(b+,b++N);N=unique(b+,b++N)-b-;

    for(int i=;i<=n;i++)a[i]=lower_bound(b+,b++N,a[i])-b;

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

    {

        for(int j=i;j<=n;j+=lowbit(j))

        update(root[j],,N,pos[a[i]],);

        s[a[i]].insert(i);pos[a[i]]=i;

    }

    for(int i=;i<=N;i++)s[i].insert();

    for(int i=;i<=m;i++)

    {

        if(ch[i][]=='Q')

        {

            int ans=;

            for(int j=q1[i]-;j;j-=lowbit(j))ans-=query(root[j],,N,,q1[i]-);

            for(int j=q2[i];j;j-=lowbit(j))ans+=query(root[j],,N,,q1[i]-);

            printf("%d\n",ans);

        }

        else

        {

            pre=it=last=s[a[q1[i]]].find(q1[i]);pre--;last++;

            if(last!=s[a[q1[i]]].end())

            {

                for(int j=*last;j<=n;j+=lowbit(j))update(root[j],,N,q1[i],-);

                for(int j=*last;j<=n;j+=lowbit(j))update(root[j],,N,*pre,);

            }

            q2[i]=lower_bound(b+,b++N,q2[i])-b;

            for(int j=q1[i];j<=n;j+=lowbit(j))update(root[j],,N,*pre,-);

            s[a[q1[i]]].erase(it);a[q1[i]]=q2[i];s[a[q1[i]]].insert(q1[i]);

            pre=last=s[a[q1[i]]].find(q1[i]);pre--;last++;

            for(int j=q1[i];j<=n;j+=lowbit(j))update(root[j],,N,*pre,);

            if(last!=s[a[q1[i]]].end())

            {

                for(int j=*last;j<=n;j+=lowbit(j))update(root[j],,N,*pre,-);

                for(int j=*last;j<=n;j+=lowbit(j))update(root[j],,N,q1[i],);

            }

        }

    }

}

　　分块的做法等会补...

相关文章