2021牛客寒假算法基础集训营3 E. 买礼物(线段树、链表思想)

Description

Solution

一开始的思路是用把2的查询 是否有相同转换成查询 里有多少个不同的数字，用带修莫队/树套树等奇奇怪怪的做法。然而， 的数据范围支撑不了上述 和 的做法。
于是考虑能否用 的复杂度完成本题。注意到我们可以用链表记录每一个数字上次出现和下次出现的下标，那么实际上对于每一次查询，我们只需要查找 是否在 的范围里面，如果成立，就输出 ，否则输出 。对于每次修改，可以类似于链表删除的思想，如下图：

简单的说就是令 ,
那么, ，即上图里面的红线。此时，我们把 设置为很大的数字如 保证不会再影响我们查询最小值的过程。
剩下的就是对于 数组建立线段树，使用区间查询最小和单点修改的操作。

Code

#include<bits/stdc++.h>

typedef long long ll;
using namespace std;

const int N = 1e6 + 5;

int n, m, a[N], last[N], nextz[N], pos[N];

struct node {
  int l, r, mx;
}t[N << 1];
void push_up(int rt) {
  t[rt].mx = min(t[rt << 1].mx, t[rt << 1 | 1].mx);
}
void build(int rt, int l, int r) {
  t[rt].l = l, t[rt].r = r;
  if(l == r) {
    t[rt].mx = nextz[l];
    return ;
  }
  int mid = t[rt].l + t[rt].r >> 1;
  build(rt << 1, l, mid);
  build(rt << 1 | 1, mid + 1, r);
  push_up(rt);
}
void update(int rt, int x, int val) {
  if(t[rt].l == t[rt].r) {
    t[rt].mx = val;
    return ;
  }
  int mid = t[rt].l + t[rt].r >> 1;
  if(x <= mid) {
    update(rt << 1, x, val);
  } else {
    update(rt << 1 | 1, x, val);
  }
  push_up(rt);
}
int query(int rt, int ql, int qr) {
  if(ql <= t[rt].l && qr >= t[rt].r) {
    return t[rt].mx;
  }
  int mid = t[rt].l + t[rt].r >> 1;
  if(qr <= mid) {
    return query(rt << 1, ql, qr);
  } else if(ql > mid) {
    return query(rt << 1 | 1, ql, qr);
  } else {
    return min(query(rt << 1, ql, mid), query(rt << 1 | 1, mid + 1, qr));
  }
}
void solve() {
  cin >> n >> m;
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
    nextz[i] = n + 1, last[i] = 0;
  }
  for(int i = 1; i <= n; i++) {
    if(pos[a[i]]) {
      last[i] = pos[a[i]];
      nextz[last[i]] = i;
      pos[a[i]] = i;
    } else {
      pos[a[i]] = i;
    }
  }
  build(1, 1, n);
  while(m--) {
    int op, l, r; cin >> op;
    if(op == 1) {
      cin >> l;
      int L = last[l], R = nextz[l];
      nextz[L] = R, last[R] = L;
      nextz[l] = 1e9;
      update(1, L, R);
      update(1, l, 1e9);
    } else {
      cin >> l >> r;
      int pos = query(1, l, r); // 找到 [l, r] 里面的 nextz 最小的
      if(pos <= r) {
        cout << 1 << '\n';
      } else {
        cout << 0 << '\n';
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int T = 1; //cin >> T;
  while(T--) {
    solve();
  }
  return 0;
}