M_sea

洛谷1903 [国家集训队]数颜色 / 维护队列
LuoguBZOJ算法带修改莫队的板子(调了半年qwq)但是我写的常数巨大,吸口氧才能过qwq然而BZOJ都A了在...
扫描右侧二维码阅读全文
03
2018/10

洛谷1903 [国家集训队]数颜色 / 维护队列

Luogu

BZOJ

算法

带修改莫队的板子(调了半年qwq)

但是我写的常数巨大,吸口氧才能过qwq

然而BZOJ都A了

在标准莫队的操作上加上一个延时间轴的移动就行了。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int block,cnt[1000010];
int a[50010];
int ans=0,Ans[50010];
int n,m;

struct query { int l,r,pre,id; } q[50010];
struct change { int pos,col; } c[50010];
int qcnt,ccnt;

inline bool cmp(query a,query b) {
    return (a.l/block)^(b.l/block)?a.l<b.l:(((a.l/block)&1)?a.r<b.r:a.r>b.r);
}

inline void add(int x) {
    if (!cnt[x]) ++ans;
    ++cnt[x];
}

inline void del(int x) {
    --cnt[x];
    if (!cnt[x]) --ans;
}
inline void modify(int cid,int qid) {
    int ql=q[qid].l,qr=q[qid].r;
    int p=c[cid].pos,col=c[cid].col;
    if (ql<=p&&p<=qr) {
        del(a[p]); add(col);
    }
    re int t=a[p]; a[p]=c[cid].col; c[cid].col=t;
}

int main() {
    n=read(),m=read(); block=sqrt(n);
    for (re int i=1;i<=n;i++) a[i]=read();
    for (re int i=1;i<=m;i++) {
        char opt=getchar();
        while (opt!='Q'&&opt!='R') opt=getchar();
        if (opt=='Q') {
            q[++qcnt].l=read(),q[qcnt].r=read();
            q[qcnt].pre=ccnt,q[qcnt].id=qcnt;
        }
        else if (opt=='R') {
            c[++ccnt].pos=read();
            c[ccnt].col=read();
        }
    }
    sort(q+1,q+qcnt+1,cmp);
    int l=1,r=0,t=0;
    for (re int i=1;i<=qcnt;i++) {
        int ql=q[i].l,qr=q[i].r,qt=q[i].pre;
        while (l<ql) del(a[l++]);
        while (l>ql) add(a[--l]);
        while (r<qr) add(a[++r]);
        while (r>qr) del(a[r--]);
        while (t<qt) modify(++t,i);
        while (t>qt) modify(t--,i);
        Ans[q[i].id]=ans;
    }
    for (re int i=1;i<=qcnt;i++) printf("%d\n",Ans[i]);
    return 0;
}
最后修改:2019 年 05 月 26 日 03 : 02 PM

发表评论