HDU 4747 mex "recommended collection"

Hello everyone , I meet you again , I'm the king of the whole stack .

The question ：

Give a number a Definition mex(l,r) Express a[l]…a[r] The smallest discontinuous number in Find all mex(l,r) And

Ideas ：

First of all, I can think of l Start to n Of all numbers mex The value must be increasing Then we can find out with 1 Start to n Of all numbers mex Sweep it from front to back At this time, we can find [1,r] All interval mex and Using the segment tree

Then consider how to find [2,r]、[3,r]…. from [1,r] To [2,r] The change of is nothing more than removing the first number So what is the effect of removing a number ？

For example, remove one 2 Then he can affect the next one at most 2 Where it appears also He just put mex>2 The place was changed to 2 From 2 There's a cut And because of the increasing relationship mentioned before So the range of influence must also be continuous ！

Then we can delete one number at a time Use the line segment tree to find out the interval of his influence And cover this interval with the deleted number

Finally, every summation is the answer

Code ：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
typedef __int64 ll;
#define N 201000
#define L(x) (x<<1)
#define R(x) ((x<<1)|1)

struct node
{
    int l,r,val,lazy;
    ll sum;
}tree[N*4];
int a[N],mex[N],next[N];
int n,l,r;
map<int,int> mp;
ll ans;

void up(int i)
{
    tree[i].val=max(tree[L(i)].val,tree[R(i)].val);
    tree[i].sum=tree[L(i)].sum+tree[R(i)].sum;
}

void down(int i)
{
    if(tree[i].lazy!=-1)
    {
        tree[L(i)].lazy=tree[i].lazy;
        tree[L(i)].val=tree[i].lazy;
        tree[L(i)].sum=(tree[L(i)].r-tree[L(i)].l+1)*tree[i].lazy;
        tree[R(i)].lazy=tree[i].lazy;
        tree[R(i)].val=tree[i].lazy;
        tree[R(i)].sum=(tree[R(i)].r-tree[R(i)].l+1)*tree[i].lazy;
        tree[i].lazy=-1;
    }
}

void init(int l,int r,int i)
{
    tree[i].l=l; tree[i].r=r; tree[i].lazy=-1;
    if(l==r)
    {
        tree[i].val=mex[l];
        tree[i].sum=mex[l];
        return ;
    }
    int mid=(l+r)>>1;
    init(l,mid,L(i));
    init(mid+1,r,R(i));
    up(i);
}

void update(int l,int r,int i,int k)
{
    if(l==tree[i].l&&r==tree[i].r)
    {
        tree[i].sum=(tree[i].r-tree[i].l+1)*k;
        tree[i].val=k;
        tree[i].lazy=k;
        return ;
    }
    down(i);
    int mid=(tree[i].l+tree[i].r)>>1;
    if(r<=mid) update(l,r,L(i),k);
    else if(l>mid) update(l,r,R(i),k);
    else
    {
        update(l,mid,L(i),k);
        update(mid+1,r,R(i),k);
    }
    up(i);
}

void query(int i,int k)
{
    if(tree[i].l==tree[i].r)
    {
        if(tree[i].val>k) l=tree[i].l;
        else l=n+1;
        return ;
    }
    down(i);
    if(tree[L(i)].val>k) query(L(i),k);
    else query(R(i),k);
    up(i);
}

int main()
{
    int i,j;
    while(~scanf("%d",&n))
    {
        if(!n) break;
        mp.clear(); // get mex
        j=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            mp[a[i]]=1;
            while(mp[j]) j++;
            mex[i]=j;
        }
        mp.clear(); // get next
        for(i=1;i<=n;i++) mp[a[i]]=n+1;
        for(i=n;i>=1;i--)
        {
            next[i]=mp[a[i]];
            mp[a[i]]=i;
        }
        //for(i=1;i<=n;i++) printf("%d %d\n",mex[i],next[i]);
        init(1,n,1);
        for(i=1,ans=0;i<=n;i++)
        {
            ans+=tree[1].sum;
            query(1,a[i]);
            r=next[i];
            //printf("%d %d\n",l,r);
            if(l<r)
            {
                update(l,r-1,1,a[i]);
            }
            update(i,i,1,0);
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

Copy

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/116215.html Link to the original text ：https://javaforall.cn