买礼物 题解(线段树+思维)

题目链接

题目思路

本质上还是一个线段树裸题

就是要思考这个线段树记录的是什么

线段树记录区间中每个元素的下一个元素的最小值

这样只要查询的时候小于右边界即可

而如果把某个值变为空，即模拟一下链表操作即可

所以要记录这个元素上一个元素，也要记录这个元素下一个元素

那么就变成了单点修改，区间查询

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
const int eps=1e-6;
int n,q;
int a[maxn],nxt[maxn],bef[maxn],last[maxn];
int tree[maxn<<2];
void build(int node,int l,int r){
    if(l==r){
        tree[node]=nxt[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    tree[node]=min(tree[node<<1],tree[node<<1|1]);
}
void update(int node,int l,int r,int pos,int zhi){
    if(l==r){
        tree[node]=zhi;
        return ;
    }
    int mid=(l+r)>>1;
    if(mid>=pos) update(node<<1,l,mid,pos,zhi);
    else update(node<<1|1,mid+1,r,pos,zhi);
    tree[node]=min(tree[node<<1],tree[node<<1|1]);
}
int query(int node,int l,int r,int L,int R){
    if(L<=l&&r<=R){
        return tree[node];
    }
    int mid=(l+r)>>1,mi=inf;
    if(mid>=L) mi=min(mi,query(node<<1,l,mid,L,R));
    if(mid<R) mi=min(mi,query(node<<1|1,mid+1,r,L,R));
    return mi;
}
signed main(){
    memset(nxt,0x3f,sizeof(nxt));
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        nxt[last[a[i]]]=i;//
        bef[i]=last[a[i]];
        last[a[i]]=i;
    }
    build(1,1,n);
    for(int i=1,opt,x,l,r;i<=q;i++){
        scanf("%d",&opt);
        if(opt==1){
            scanf("%d",&x);
            if(nxt[x]!=inf){
                bef[nxt[x]]=bef[x];
            }
            if(bef[x]!=0){
                nxt[bef[x]]=nxt[x];
                update(1,1,n,bef[x],nxt[x]);
            }
            update(1,1,n,x,inf);
        }else{
            scanf("%d%d",&l,&r);
            if(query(1,1,n,l,r)<=r){
                printf("1\n");
            }else{
                printf("0\n");
            }
        }
    }
    return 0;
}