[HEOI2012]采花

题意:

给出n个数字,和m组询问,每次询问区间有多少种数字个数大于1….
n,m\leq 1000000

分析:

刚刚看到题目,直接想到分块,然后看数据范围GG….然后我们考虑树状数组的写法,我们先给询问按照左端点排一个序.然后我们右移左端点,然后维护树状数字…我们找到一个位置i,那么我们将其next[i]-1,next[next[i]]+1,然后区间询问就好了….
为什么是这样子呢,我们发现现在枚举了左端点,表示我们要询问的是到有段点之间的值,那么我们发现当你枚举一种颜色的位置时,没有产生贡献的区间就是这个位置和下一个位置之间的点……然后BIT维护前缀和就好了….

代码:

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define LL long long
const LL N=1e6+10;
const LL inf=0x3f3f3f3f;
const LL mod=1e9+7;
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,c,l=1;
int x[N],p[N],nxt[N],ans[N];
namespace BIT
{
    int tree[N];
    int lowbit(int now){return now&-now;}
    void change(int now,int v){for(;now<=n;now+=lowbit(now)) tree[now]+=v;}
    int sum(int now,int ret=0){for(;now;now-=lowbit(now)) ret+=tree[now];return ret;}
}
using namespace BIT;
struct Ask{int l,r,id;}ask[N];
bool cmp(Ask a,Ask b){return a.l<b.l;}
int main()
{
    read(n),read(c),read(m);
    for(int i=1;i<=n;i++) read(x[i]);
    for(int i=n;i>=1;i--) nxt[i]=p[x[i]],p[x[i]]=i;
    for(int i=1;i<=c;i++) if(nxt[p[i]]) change(nxt[p[i]],1);
    for(int i=1;i<=m;i++) read(ask[i].l),read(ask[i].r),ask[i].id=i;
    sort(ask+1,ask+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        while(l<ask[i].l)
        {
            if(nxt[l]) change(nxt[l],-1);
            if(nxt[nxt[l]]) change(nxt[nxt[l]],1);
            l++;
        }
        ans[ask[i].id]=sum(ask[i].r)-sum(ask[i].l-1);
    }
    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    return 0;
}

发表评论

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