BZOJ2120&2453 数颜色带修改莫队

[toggle hide="yes" title="题目" color=""]

Description
墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令： 1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求，你知道你需要干什么了吗？

Input
第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。

Output
对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。

Sample Input
6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

Sample Output
4
4
3
4

HINT
对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。

[/toggle]

带修改的莫队，在普通莫队的基础上增加了在时间轴上的滚动，将询问和修改分别记录，保存每个询问的左右端点，以及在当前询问之前进行了多少次修改，将块长设置为n^(2/3)，保证理论时间复杂度是O(n^(5/3))，再将询问按照(左端点所在块，右端点所在块，时间)，进行三元组排序，可以感性理解一下查询区间移动的趋势，就能知道这样做的优势了，比较严谨的推导在这里：https://blog.sengxian.com/algorithms/mo-s-algorithm

对于这道题，我的做法是先将莫队的初始区间拉到(1,n)，也就是序列的初始状态，预处理每个修改操作修改前的值，方便以后撤销修改，之后再进行莫队的操作，比较水（个人不是非常喜欢把修改操作全写成函数，感觉边界处理不如分别搞直观易调试）。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <math.h>
using namespace std;
#define mxn 10005
inline int read(){
    int s=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
    return s*f;
}
struct query{int p,v,o;}c[mxn];
struct query2{int l,r,t,id;}q[mxn];
int n,m,sc,sq,len,id[mxn],s[mxn],ans[mxn],tmp[mxn],cnt[mxn*100],cur;
inline int gchar(){
    char op=' ';
    while(op!='Q'&&op!='R') op=getchar();
    if(op=='Q') return 0;
    return 1;
}
inline bool cmp(query2 a,query2 b){
    if(id[a.l]==id[b.l]){
        if(id[a.r]==id[b.r]) return a.t<b.t;
        else return id[a.r]<id[b.r];
    }
    return id[a.l]<id[b.l];
}
int main(){
    // freopen("bzoj2120.in","r",stdin);
    // freopen("my.out","w",stdout);
    n=read(),m=read(),len=ceil(pow(n,0.67));
    for(int i=1;i<=n;++i) {
        tmp[i]=s[i]=read(),id[i]=(i-1)/len+1;
        if(!cnt[s[i]]) cur++;
        cnt[s[i]]++;
    }
    for(int i=1;i<=m;++i){
        int op=gchar();
        if(!op) q[++sq].l=read(),q[sq].r=read(),q[sq].t=sc,q[sq].id=sq;
        else c[++sc].p=read(),c[sc].v=read();
    }
    for(int i=1;i<=sc;++i) c[i].o=tmp[c[i].p],tmp[c[i].p]=c[i].v;
    sort(q+1,q+1+sq,cmp);
    for(int i=1,l=1,r=n,t=0;i<=sq;++i) {
        while(t<q[i].t) {
            t++;
            if(c[t].p>=l&&c[t].p<=r){
                if(!cnt[c[t].v]) cur++;
                cnt[c[t].o]--,cnt[c[t].v]++;
                if(!cnt[c[t].o]) cur--;
            }
            s[c[t].p]=c[t].v;
        }
        while(t>q[i].t) {
            if(c[t].p>=l&&c[t].p<=r){
                if(!cnt[c[t].o]) cur++;
                cnt[c[t].v]--,cnt[c[t].o]++;
                if(!cnt[c[t].v]) cur--;
            }
            s[c[t].p]=c[t].o;
            t--;
        }
        while(l<q[i].l) {
            cnt[s[l]]--;
            if(!cnt[s[l]]) cur--;
            l++;
        }
        while(l>q[i].l) {
            l--;
            if(!cnt[s[l]]) cur++;
            cnt[s[l]]++;
        }
        while(r<q[i].r) {
            r++;
            if(!cnt[s[r]]) cur++;
            cnt[s[r]]++;
        }
        while(r>q[i].r) {
            cnt[s[r]]--;
            if(!cnt[s[r]]) cur--;
            r--;
        }
        ans[q[i].id]=cur;
    }
    for(int i=1;i<=sq;++i) printf("%d\n",ans[i]);
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <math.h>

using namespace std;

#define mxn 10005

inline int read(){

int s=0,f=1; char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}

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

return s*f;

}

struct query{int p,v,o;}c[mxn];

struct query2{int l,r,t,id;}q[mxn];

int n,m,sc,sq,len,id[mxn],s[mxn],ans[mxn],tmp[mxn],cnt[mxn*100],cur;

inline int gchar(){

char op=' ';

while(op!='Q'&&op!='R') op=getchar();

if(op=='Q') return 0;

return 1;

}

inline bool cmp(query2 a,query2 b){

if(id[a.l]==id[b.l]){

if(id[a.r]==id[b.r]) return a.t<b.t;

else return id[a.r]<id[b.r];

}

return id[a.l]<id[b.l];

}

int main(){

// freopen("bzoj2120.in","r",stdin);

// freopen("my.out","w",stdout);

n=read(),m=read(),len=ceil(pow(n,0.67));

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

tmp[i]=s[i]=read(),id[i]=(i-1)/len+1;

if(!cnt[s[i]]) cur++;

cnt[s[i]]++;

}

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

int op=gchar();

if(!op) q[++sq].l=read(),q[sq].r=read(),q[sq].t=sc,q[sq].id=sq;

else c[++sc].p=read(),c[sc].v=read();

}

for(int i=1;i<=sc;++i) c[i].o=tmp[c[i].p],tmp[c[i].p]=c[i].v;

sort(q+1,q+1+sq,cmp);

for(int i=1,l=1,r=n,t=0;i<=sq;++i) {

while(t<q[i].t) {

t++;

if(c[t].p>=l&&c[t].p<=r){

if(!cnt[c[t].v]) cur++;

cnt[c[t].o]--,cnt[c[t].v]++;

if(!cnt[c[t].o]) cur--;

}

s[c[t].p]=c[t].v;

}

while(t>q[i].t) {

if(c[t].p>=l&&c[t].p<=r){

if(!cnt[c[t].o]) cur++;

cnt[c[t].v]--,cnt[c[t].o]++;

if(!cnt[c[t].v]) cur--;

}

s[c[t].p]=c[t].o;

t--;

}

while(l<q[i].l) {

cnt[s[l]]--;

if(!cnt[s[l]]) cur--;

l++;

}

while(l>q[i].l) {

l--;

if(!cnt[s[l]]) cur++;

cnt[s[l]]++;

}

while(r<q[i].r) {

r++;

if(!cnt[s[r]]) cur++;

cnt[s[r]]++;

}

while(r>q[i].r) {

cnt[s[r]]--;

if(!cnt[s[r]]) cur--;

r--;

}

ans[q[i].id]=cur;

}

for(int i=1;i<=sq;++i) printf("%d\n",ans[i]);

}

Narcissus' Blog

BZOJ2120&2453 数颜色带修改莫队

BZOJ3289 Mato的文件管理莫队+树状数组

BZOJ1014 [JSOI2008]火星人prefix 无旋Treap+Hash

Scott

叨叨几句... NOTHING

取消回复

Narcissus' Blog

BZOJ3289 Mato的文件管理 莫队+树状数组

BZOJ1014 [JSOI2008]火星人prefix 无旋Treap+Hash

Scott

叨叨几句... NOTHING

取消回复

Narcissus' Blog

BZOJ3289 Mato的文件管理莫队+树状数组