Nowcoder9983E.买礼物（链表+线段树）

链接：https://ac.nowcoder.com/acm/contest/9983/E
来源：牛客网

在卖礼物的超市中有 $ii个柜子里的礼物编号为aia_{i}ai。茶山牛想给牛牛和牛妹买相同编号的礼物，但礼物有可能在某个时刻被其他人买走，而且柜子数量太多，因此茶山牛在某个时刻只想知道某一个柜子区间是否能买到两件相同编号的礼物。具体来说，有qmathit qq次操作，格式如下： 1 ext 11 xmathit xx，第xmathit xx个柜子里的礼物被买走，保证此时这个柜子里的礼物还在。 2 ext 22 lmathit ll rmathit rr，茶山牛询问第lmathit ll到第rmathit rr个柜子未被买走的礼物中是否有两个礼物编号相同。$

$第一眼以为是树套树，但是这个数据范围加上2秒，树套树是肯定t的，树套树的常数是相当爆炸的。$

注意到题目里有一个性质是只需要判断两个礼物编号相同即可，从这个性质入手，单个线段树就可以完成任务了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+100;
const int M=1e6+100;
//区间是否存在1个数出现两次
//对每个礼物维护一个位置序列
//对每个礼物的位置确定下一个礼物在哪，并确定这个位置 
//然后在线段树上存储这个位置
//维护一个区间最小值
//每次区间询问，就查询这个区间内的最小位置是否小于r
int nxt[maxn];//维护每个位置
int pre[maxn];//维护每个位置的上一个位置
int Pre[M]; 
int a[maxn],w[maxn];
struct node {
    int l,r,sum;
}segTree[maxn<<3];
int n,q;
void build (int i,int l,int r) {
    segTree[i].l=l;
    segTree[i].r=r;
    if (l==r) {
        segTree[i].sum=w[l];
        return;
    }
    int mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    segTree[i].sum=min(segTree[i<<1].sum,segTree[i<<1|1].sum);
}
void up (int i,int p,int v) {
    if (segTree[i].l==p&&segTree[i].r==p) {
        segTree[i].sum=v;
        return;
    }
    int mid=(segTree[i].l+segTree[i].r)>>1;
    if (p<=mid) up(i<<1,p,v);
    if (p>mid) up(i<<1|1,p,v);
    segTree[i].sum=min(segTree[i<<1].sum,segTree[i<<1|1].sum);
}
int query (int i,int l,int r) {
    if (segTree[i].l>=l&&segTree[i].r<=r) {
        return segTree[i].sum;
    }
    int mid=(segTree[i].l+segTree[i].r)>>1;
    int ans=1e9;
    if (l<=mid) ans=min(ans,query(i<<1,l,r));
    if (r>mid) ans=min(ans,query(i<<1|1,l,r));
    return ans;
}
void del (int x) {
    //删除x位置的元素 
    if (pre[x]) {
        nxt[pre[x]]=nxt[x];
        if (nxt[x])
            up(1,pre[x],nxt[x]);
        else
            up(1,pre[x],1e9);
    }
    if (nxt[x]) {
        pre[nxt[x]]=pre[x];
    }
    nxt[x]=1e9;
    up(1,x,nxt[x]);
} 
int main () {
    scanf("%d%d",&n,&q);
    for (int i=1;i<=n;i++) scanf("%d",a+i);
    for (int i=1;i<=n;i++) {
        pre[i]=Pre[a[i]];
        if (Pre[a[i]]) nxt[Pre[a[i]]]=i;
        Pre[a[i]]=i;
    }
    for (int i=1;i<=n;i++) {
        if (nxt[i]) {
            w[i]=nxt[i];
        }
        else {
            w[i]=1e9;
        }
    }
    build(1,1,n);
    while (q--) {
        int op;
        scanf("%d",&op);
        if (op==1) {
            int x;
            scanf("%d",&x);
            del(x);
        }
        else {
            int l,r;
            scanf("%d%d",&l,&r);
            //for (int i=1;i<=n;i++) printf("%d ",nxt[i]);
            //printf("
%d
",query(1,l,r));
            if (query(1,l,r)<=r) {
                printf("1
");
            }
            else {
                printf("0
");
            }
        }
    }
}