bzoj 2120: 數顔色 帶修改莫隊算法

題意：有n個位置(n<=10000),初始每個位置有一種顔色，要求資磁兩個操作：

R x y 把位置x的顔色變為y

Q x y 求x到y這個區間内出現了多少種不同的顔色

分析：讓我們來介紹一下帶修改莫隊，其實就是三維莫隊。

每個詢問本來隻有二進制組(l,r)表示，現在我用一個三元組(l,r,x)表示，意思是對[l,r]進行詢問，x表示在此次詢問操作之前經過了x次修改操作。

然後和普通莫隊一樣，第三維也是暴力移動的。即知道(l,r,x)的答案可以知道(l-1,r,x)(l+1,r,x)(l,r-1,x)(l,r+1,x)(l,r,x-1)(l,r,x+1)的答案。

按l所在的塊為第一關鍵字，r所在的塊為第二關鍵字，x為第三關鍵字排序處理。

塊大小需要設為n^2/3，總複雜度是n^5/3，這裡就略去複雜度的證明。

代碼：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define B 250
#define N 10005
using namespace std;

int n,m,q,scha,color[N],t[N*],tot;
struct data{int l,r,id,ans,x;}w[N];
struct chan{int x,y;}cha[N];

bool cmp(data a,data b)
{
    return (a.l/B<b.l/B||a.l/B==b.l/B&&a.r/B<b.r/B||a.l/B==b.l/B&&a.r/B<b.r/B&&a.x<b.x);
}

void updata(int x,int y)
{
    if (y==)
    {
        if (!t[color[x]]) tot++;
        t[color[x]]++;
    }else
    {
        t[color[x]]--;
        if (!t[color[x]]) tot--;
    }
}

void change(int x,int y,int l,int r)
{
    if (cha[x].x>=l&&cha[x].x<=r) updata(cha[x].x,-);
    swap(color[cha[x].x],cha[x].y);
    if (cha[x].x>=l&&cha[x].x<=r) updata(cha[x].x,);
}

void solve()
{
    updata(,);
    for (int i=,l=,r=,x=;i<=q;i++)
    {
        for (;r<w[i].r;r++)
            updata(r+,);
        for (;r>w[i].r;r--)
            updata(r,-);
        for (;l<w[i].l;l++)
            updata(l,-);
        for (;l>w[i].l;l--)
            updata(l-,);
        for (;x<w[i].x;x++)
            change(x+,,l,r);
        for (;x>w[i].x;x--)
            change(x,-,l,r);
        w[i].ans=tot;
    }
}

bool cmp1(data a,data b)
{
    return a.id<b.id;
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=;i<=n;i++)
        scanf("%d",&color[i]);
    for (int i=;i<=m;i++)
    {
        char ch[];
        int x,y;
        scanf("%s%d%d",ch,&x,&y);
        if (ch[]=='R')
        {
            cha[++scha].x=x;
            cha[scha].y=y;
        }else
        {
            w[++q].l=x;
            w[q].r=y;
            w[q].x=scha;
            w[q].id=q;
        }
    }
    sort(w+,w+q+,cmp);
    solve();
    sort(w+,w+q+,cmp1);
    for (int i=;i<=q;i++)
        printf("%d\n",w[i].ans);
    return ;
}