BZOJ2743 采花

题目大意

有n个数,每个数一种颜色。m次询问,每次询问l,r区间内除去只有一个数的颜色的不同颜色的种数。
n,m<=1000,000

Solution

刚看到题目,就想到了一种非常方便的莫队做法。看了一眼数据范围,发现要$10^9$的复杂度,卡一卡就过去了。

我会函数式线段树,于是有口胡了一个可持久化线段树的做法,就是维护出所有1~r的线段树,且1~i+1的线段树是从1~i的线段树修改几个点后继承过来的。花了10分钟写完,开数组时发现要开三个2e7的数组,空间240MB,而内存限制只有128MB,不得已,砍掉一半,数组大小定了1e7。交上去后,喜闻乐见地RE了o(╥﹏╥)o。

后来又发现,这道题没有强制在线,所以对读入的数据按右端点排序后,可以每次加入一个数i后处理完右端点为i的询问,就不需要记录前面的线段树了。不需要可持久化的线段树,空间复杂度变成了O(n)。

单点修改,区间查询和,其实也能用树状数组,只是懒得改线段树了。

Code
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
    int l,r,id;
}q[1000010];
int cnt=0;
int tree[8000010],pre[1000010],Pre[1000010],root[1000010],a[1000010],ans[1000010];
int read()
{
    int ans=0;
    char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') 
    {
        ans=ans*10+ch-'0';
        ch=getchar();
    }
    return ans;
}
bool cmp(node x,node y)
{
    return x.r<y.r;
}
void insert(int pos,int l,int r,int t,int key)
{
    if (l==r)
    {
        tree[t]+=key;
        return;
    }
    int mid=(l+r)>>1;
    if (pos<=mid) insert(pos,l,mid,t<<1,key);
    else insert(pos,mid+1,r,t<<1|1,key);
    tree[t]=tree[t<<1]+tree[t<<1|1];
}
int query(int t,int l,int r,int x,int y)
{
    if (!tree[t]) return 0;
    if (l==x&&y==r) return tree[t];
    int mid=(l+r)>>1;
    if (y<=mid) return query(t<<1,l,mid,x,y);
    if (x>mid) return query(t<<1|1,mid+1,r,x,y);
    return query(t<<1,l,mid,x,mid)+query(t<<1|1,mid+1,r,mid+1,y);
}
int main()
{
    int n,c,m;
    scanf("%d%d%d",&n,&c,&m);
    for (int i=1;i<=n;i++) a[i]=read();
    for (int i=1;i<=m;i++)
        q[i].l=read(),q[i].r=read(),q[i].id=i; 
    sort(q+1,q+1+m,cmp);
    int head=1;
    for (int i=1;i<=n;i++)
    {
        if (Pre[pre[a[i]]]) insert(Pre[pre[a[i]]],1,n,1,-1);
        if (pre[a[i]]) insert(pre[a[i]],1,n,1,1);
        while (head<=m&&q[head].r==i)
            ans[q[head].id]=query(1,1,n,q[head].l,q[head].r),head++;
        if (head>m) break;
        Pre[i]=pre[a[i]];
        pre[a[i]]=i;
    }
    for (int i=1;i<=m;i++) 
        printf("%d\n",ans[i]);
    return 0;
}

1,595 thoughts on “BZOJ2743 采花”

  1. Pingback: buy online sofa beds nz