发布于 由itewqq

[算法学习] 可持久化线段树基础题 SPOJ D-query

题意问给出一个序列然后q个询问问[l,r]之间有多少种不同的数。这里最简单的思想就是用可持久化线段树，每加入一个点作为一个版本，然后如果某一个点之前出现过那么就在新版本里把那个位置点的计数-1，再把现在这个位置+1，这样的话要求[l,r]中的数字有多少种那就只需要对第r个版本的线段树求[l,r]之间的和就行了，思路并不复杂（毕竟入门题

实现的话，一是用map[num]来保存上一次num出现的位置，然后还有很重要的一点是新版本的树不能影响到前面版本的，但是传统的从前一个版本建立新版本的方法就会影响到（因为有公共节点）还没有看别人的题解，我自己使用的方法是用一个“中间树”来隔离前后两个紧挨的版本，-1和+1都创建新节点，（虽然似乎非常慢）实现也很简单就是用一个临时的树根中转就可以啦

代码 （这个题目时限227ms结果我210ms险过emm回去学习下前排dalao的80ms

#include 
#include 
#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn=300000+5;
const int maxq=2e5+5;
const int maxb=20*maxq;
const int MOD=1e9+7;

int lc[maxb],rc[maxb],rt[maxn],sum[maxb],idx;
int ar[maxn],ars[maxn];
unordered_mapmp;

void build(int &k,int l,int r)
{
    k=++idx;
    if(l==r)
    {
        sum[k]=0;
        return ;
    }
    else
    {
        int mid=(l+r)>>1;
        build(lc[k],l,mid);
        build(rc[k],mid+1,r);
        sum[k]=0;
        return ;
    }
}


void update(int o,int &v,int l,int r,int p,int x)//pay attention to the &
{
    v=++idx;
    lc[v]=lc[o],rc[v]=rc[o],sum[v]=sum[o]+x;
    if(l==r)
    {
        return ;
    }
    else
    {
        int mid=(l+r)>>1;
        if(p<=mid)update(lc[o],lc[v],l,mid,p,x);
        else update(rc[o],rc[v],mid+1,r,p,x);
        return ;
    }
}

int ql,qr;
int query(int o,int l,int r)
{
    if(ql<=l&&r<=qr)
    {
        return sum[o];
    }
    else
    {
        int mid=(l+r)>>1;
        if(ql<=mid)
            return query(lc[o],l,mid)+sum[rc[o]];
        else return query(rc[o],mid+1,r);
    }
}


int main()
{
    int n,q;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&ar[i]);
    }

    build(rt[0],1,n);
    for (int i=1;i<=n;i++)
    {
        if(mp[ar[i]])
        {
            int teprt;
            update(rt[i-1],teprt,1,n,mp[ar[i]],-1);
            update(teprt,rt[i],1,n,i,1);
            mp[ar[i]]=i;
        }
        else
        {
            mp[ar[i]]=i;
            update(rt[i-1],rt[i],1,n,i,1);
        }
    }
    scanf("%d",&q);
    for (int i=1;i<=q;i++)
    {
        scanf("%d%d",&ql,&qr);
        printf("%d\n",query(rt[qr],1,n));
    }
    return 0;
}

 

 

发表回复

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。