维护队列 bzoj-2453

题目大意：给定一个n个数序列，支持查询区间数的种类数，单点修改。不强制在线。

注释：$1\le n,m\le 10^5$。

想法：

带修改莫队裸题。

如果没有修改操作的话，我们就正常按照莫队一样左右移动区间即可。

有了修改操作的话，我们把块变成$n^{\frac{2}{3}}$，关键字变成：左端点所在块、右端点所在块和时间戳。

然后暴力就行了。

Code：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int N=10003;

struct Query{int l,r,Tim,ID;}q[N];

struct Change{int pos,New,Old;}c[N];

int n,m,s[N],color[N*100],t,Time,now[N],unit,Be[N],ans[N],Ans,l=1,r,T;

inline bool cmp(const Query &a,const Query &b)

{

    return Be[a.l]==Be[b.l]?(Be[a.r]==Be[b.r]?a.Tim<b.Tim:a.r<b.r):a.l<b.l;

}

inline void revise(int x,int d) {color[x]+=d; if(d>0) Ans+=color[x]==1; if(d<0) Ans-=color[x]==0;}

inline void going(int x,int d) {if(l<=x&&x<=r) revise(d,1),revise(s[x],-1); s[x]=d;}

int main()

{

    scanf("%d%d",&n,&m); unit=pow(n,0.666666);

    for(int i=1;i<=n;i++) scanf("%d",&s[i]),now[i]=s[i],Be[i]=i/unit+1;

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

    {

        char s[10]; int x,y;

        scanf("%s%d%d",s+1,&x,&y);

        if(s[1]=='Q') q[++t]=(Query){x,y,Time,t};

        if(s[1]=='R') {c[++Time]=(Change){x,y,now[x]},now[x]=y;}

    }

    // printf("Fuck %d\n",t);

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

    for(int i=1;i<=t;i++)

    {

        while(T<q[i].Tim) going(c[T+1].pos,c[T+1].New),T++;

        while(T>q[i].Tim) going(c[T].pos,c[T].Old),T--;

        while(l<q[i].l) revise(s[l],-1),l++;

        while(l>q[i].l) revise(s[l-1],1),l--;

        while(r<q[i].r) revise(s[r+1],1),r++;

        while(r>q[i].r) revise(s[r],-1),r--;

        ans[q[i].ID]=Ans;

    }

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

    return 0;

}

小结：莫队其实就是暴力啊。

巴特西

[bzoj2453]维护队列_带修改莫队

维护队列 bzoj-2453

最新文章

热门文章