P1972 [SDOI2009]HH的项链 莫队or树状数组

时间：2023-03-09 05:52:26
P1972 [SDOI2009]HH的项链 莫队or树状数组

用什么树状数组莫队多帅

思路：树状数组\(or\)莫队（其实还是推荐树状数组\(QwQ\)）

提交：我告诉你我卡了一会儿常

卡不满原因：没有用奇偶性排序

题解：

莫队：

就是裸的莫队，把询问排序\(etc.\)

// luogu-judger-enable-o2

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cmath>

#define R register int

using namespace std;

namespace Fread {

    static char B[1<<15],*S=B,*D=B;

    #define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)

    inline int g() {

        R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;

        do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;

    }

}using Fread::g;

int T;

struct seg{

    int l,r,rk;

    bool operator <(const seg& a)const{return (l/T)==(a.l/T)?r>a.r:l<a.l;}

}s[1000010];

int n,m,l=0,r=0,ans;

int a[500010],cnt[1000010],anss[500010],pos[500010];

bool cmp(const seg& a,const seg& b){

    return pos[a.l]^pos[b.l]?pos[a.l]<pos[b.l]:pos[a.l]&1?a.r<b.r:a.r>b.r;

}

inline void change(int pos,int inc) {(inc>0)?ans+=(++cnt[a[pos]]==1):ans-=(--cnt[a[pos]]==0);}

signed main() {

    n=g(); T=sqrt(n);

    for(R i=1;i<=n;++i) a[i]=g();

    m=g(); for(R i=1;i<=m;++i) s[i].l=g(),s[i].r=g(),s[i].rk=i;

    for(R i=1;i<=n;++i) pos[i]=(i-1)/T+1;

    sort(s+1,s+m+1,cmp);

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

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

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

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

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

        anss[s[i].rk]=ans;

    } for(R i=1;i<=m;++i) printf("%d\n",anss[i]);

}

树状数组：（推荐）

不用卡常先把询问按右端点排序，然后按照排好序的询问向树状数组里添加颜色，把每一种颜色最后出现的位置标记成\(1\)。因为排完序后右端点是递增的，所以我们可以只维护每一种颜色最后出现的位置，询问时查一下区间有多少个\(1\)。

我们维护一个数组叫\(pos[color]\)，记录\(color\)上一次出现的位置。当我们向右扫时，设遇到的颜色\(a[now]=color\)，当\(pos[color]!=0\)时，我们把\(pos[color]\)改成\(0\)，并把\(now\)修改成\(1\)，并令\(pos[color]=now\)，即可维护信息。

#include<cstdio>

#include<iostream>

#include<algorithm>

#define R register int

using namespace std;

inline int g() {

    R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;

    do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;

}

struct seg{

    int l,r,rk;

    #define l(i) s[i].l

    #define r(i) s[i].r

    #define rk(i) s[i].rk

    bool operator <(const seg& a)const{return r==a.r?l<a.l:r<a.r;}

}s[500010];

int n,m,lst=1;

int a[500010],ans[500010],c[1000010],pos[1000010];

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

inline void add(int pos,int inc) {for(;pos<=n;pos+=lbt(pos)) c[pos]+=inc;}

inline int query(int pos) { R ret=0;

    for(;pos;pos-=lbt(pos)) ret+=c[pos];

    return ret;

}

signed main() {

    n=g(); for(R i=1;i<=n;++i) a[i]=g();

    m=g(); for(R i=1;i<=m;++i) l(i)=g(),r(i)=g(),rk(i)=i;

    sort(s+1,s+m+1);

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

        for(R j=lst;j<=r(i);++j) {

            if(pos[a[j]]) add(pos[a[j]],-1);

            add(j,1); pos[a[j]]=j;

        } lst=r(i)+1;

        ans[rk(i)]=query(r(i))-query(l(i)-1);

    }

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

}

2019.07.22

相关文章