跟随zzd的blog,我去写了这道题目,然后用了BIT和莫队,两种写法….

题意:

给你一个序列,询问区间数字种类……..

分析:

莫队就是裸的莫队,直接排序完,暴力就好了….
树状数组的写法就是我们把所有询问按R排序,然后把一个数值的贡献加到最右边的点上面,枚举询问,右移右端点…..然后左边直接写BIT就好了…..

代码:

BIT:

#pragma GCC optimise(2)
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=5e4+10;
const LL mod=998244353;
const double eps=1e-12;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,m,nowr,col[N],ans[N*4];
struct ASK{int l,r,name;}ask[N*4];
bool cmp(ASK a,ASK b){return a.r<b.r;}
int last[N*20];
namespace BIT
{
    int xx[N];
    int lowbit(int now){return now&-now;}
    void change(int now,int v){for(;now<=n;now+=lowbit(now)) xx[now]+=v;}
    int query(int now,int ret=0){for(;now;now-=lowbit(now)) ret+=xx[now];return ret;}
}
using namespace BIT;
signed main() 
{
    read(n);
    for(int i=1;i<=n;i++) read(col[i]);
    read(m);
    for(int i=1;i<=m;i++) read(ask[i].l),read(ask[i].r),ask[i].name=i;
    sort(ask+1,ask+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        while(nowr<ask[i].r)
        {
            nowr++;
            if(last[col[nowr]])
                change(last[col[nowr]],-1);
            last[col[nowr]]=nowr;
            change(last[col[nowr]],+1);
        }
        ans[ask[i].name]=query(ask[i].r)-query(ask[i].l-1);
    }
    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    return 0;
}

莫队:



\#pragma GCC optimise(2) #include<bits/stdc++.h> #define LL long long #define P pair<int,int> const LL N=5e4+10; const LL mod=998244353; const double eps=1e-12; using namespace std; template<typename tp> inline void read(tp &x) { x=0; char c=getchar(); bool f=0; for(;c<'0'||c>'9';f|=(c=='-'),c = getchar()); for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar()); if(f) x=-x; } int n,m,k; int ans[N*4],block[N],col[N],tot; struct ASK{int l,r,name;}ask[N*4]; bool cmp(ASK a,ASK b) { if(block[a.l]==block[b.l]) return a.r<b.r; return block[a.l]<block[b.l]; } int flag[N*20],nowl=1,nowr,anss; signed main() { read(n);k=sqrt(n); for(int i=1;i<=n;i++) read(col[i]); for(int i=1;i<=n;i++){block[i]=tot;if(i%k==0&&i!=n) tot++;} read(m); for(int i=1;i<=m;i++) read(ask[i].l),read(ask[i].r),ask[i].name=i; sort(ask+1,ask+m+1,cmp); for(int i=1;i<=m;i++) { while(nowr<ask[i].r) anss+=(flag[col[++nowr]]++==0); while(nowl>ask[i].l) anss+=(flag[col[--nowl]]++==0); while(nowr>ask[i].r) anss-=(--flag[col[nowr--]]==0); while(nowl<ask[i].l) anss-=(--flag[col[nowl++]]==0); ans[ask[i].name]=anss; } for(int i=1;i<=m;i++) printf("%d\n",ans[i]); return 0; }

Leave A Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注