买礼物

比赛的时候知道这题是线段树，但不知道应该维护什么就没有写

表示第个礼物的上一个相同礼物的位置

表示第个礼物的下一个相同礼物的位置

我们要维护的就是区间 ~间的最小值或者的最大值

我这里维护的是的最小值，当删除位置的物品时，把置成n+1，查询时看区间最小值小于等于就好

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
#define lson st<<1,l,mid
#define INF 1e9
#define rson st<<1|1,mid+1,r
const int maxn = 5e5+5;
int a[maxn];
int sum[maxn << 2];
int pre[maxn],nex[maxn];
int n,Q;

void push_up(int st){
    sum[st] = min(sum[st << 1] , sum[st << 1 | 1]);
}
void build(int st, int l, int r) {
    if (l == r) {
        sum[st] = nex[l];
        return;
    }
    int mid = l + r >> 1;
    build(lson);
    build(rson);
    push_up(st);
}
int query(int st,int l,int r,int L,int R){//查询[L,R]的最小值
    if(l > R || r < L) return n + 1;
    if(l >= L && r <= R) return sum[st];
    int mid = l + r >> 1;
    return min(query(lson,L,R),query(rson,L,R));
}
void updata(int st,int l,int r,int x,int val){//把位置为X的值改成val
    if(l > x || r < x) return ;
    if(l == r){
        sum[st] = val;
        return ;
    }
    int mid = l + r >> 1;
    updata(lson,x,val);
    updata(rson,x,val);
    push_up(st);
}
unordered_map<int,int>mp;
int main(){
    n = read(),Q = read();
    for(int i = 1 ; i <= n ; ++i){
        a[i] = read();
    }
    for(int i = 1 ; i <= n ; ++i){
        pre[i] = mp[a[i]];//前一个a[i]的位置，没有为0
        mp[a[i]] = i;
    }
    mp.clear();
    for(int i = n ; i ; --i){
        nex[i] = (mp[a[i]] == 0 ? n + 1 : mp[a[i]]);//后一个a[i]的位置，没有为n+1
        mp[a[i]] = i;
    }
    build(1,1,n);
    while(Q--){
        int op = read();
        if(op == 1){
            int x = read();
            updata(1,1,n,x,n+1);//第i个位置没东西了，他的下一个相同的礼物位置变成大于n的值不影响查询
            updata(1,1,n,pre[x],nex[x]);//第i个礼物的上一个礼物的下一个礼物的位置变成第i个礼物的下一个礼物的位置（好绕）
            nex[pre[x]] = nex[x];//把位置i上一个的nex的值变成i下一个的位置
            pre[nex[x]] = pre[x];//把位置i下一个的pre值变成i上一个的位置
        }
        else{
            int l = read(),r = read();
            if(query(1,1,n,l,r) <= r){
                puts("1");
            }
            else puts("0");
        }
    }
}