数据结构专题之杂题

查找 Search

传送门：查找 Search

题意：给了一个序列，有两个操作，分别为修改序列中的某个值，以及查询区间内是否存在两个值和为$w$，每次查询的$w$都相同，并且强制在线。

思路：首先考虑没有修改操作，我们对于所有$a[i]$，保存一个离它最近的前一个$w - a[i]$的位置记作$pre[i]$，查询时就判断区间内最大的一个$pre[i]$是否在区间内。如果有修改操作，我们还用刚刚这种方法，修改掉一个值可能要修改后面所有的$pre$，这样可能会超时。我们考虑下面这种情况，

当我们有一个为蓝色的查询区间的时候，我们会发现后面的$x$其实是没有用的，因为包含着一个更小的区间(红色)有$x$，也就是说我们对于一个$a[i]$来说，最多会有一个来自后面的$w - a[i]$。那么我们可以利用$set$对每一个值存它的下标进行处理，再利用线段树维护$pre$的最大值。本题的细节比较多。

代码：

#include <bits/stdc++.h>
#define ls k << 1
#define rs k << 1 | 1
#define lson k << 1, l, mid
#define rson k << 1 | 1, mid + 1, r
using namespace std;

const int MAX = 5e5 + 5;
struct Node {
  int l, r, pre;
} tree[MAX << 2];
int a[MAX], pre[MAX], n, m, w;
set<int> pos[MAX];

void pushup(int k) {
  tree[k].pre = max(tree[ls].pre, tree[rs].pre);
}

void build(int k, int l, int r) {
  tree[k].l = l; tree[k].r = r;
  if (l == r) {
    tree[k].pre = pre[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(lson);
  build(rson);
  pushup(k);
}

void modify(int k, int x, int y) {
  if (tree[k].l == tree[k].r) {
    tree[k].pre = y;
    return;
  }
  int mid = (tree[k].l + tree[k].r) >> 1;
  if (x <= mid) modify(ls, x, y);
  else modify(rs, x, y);
  pushup(k);
}

int query(int k, int l, int r) {
  if (tree[k].l == l && tree[k].r == r) {
    return tree[k].pre;
  }
  int mid = (tree[k].l + tree[k].r) >> 1;
  if (r <= mid) return query(ls, l, r);
  else if (l > mid) return query(rs, l, r);
  else return max(query(lson), query(rson));
}

bool isBetween(int x, int l = 1, int r = n) {
  return l <= x && x <= r;
}

void modifyPre(int p, int x) {
  if (!isBetween(p)) {
    return;
  }
  int ptr1 = *prev(pos[x].lower_bound(p));
  int ptr2 = *prev(pos[w - x].lower_bound(p));
  if (ptr1 < ptr2) {
    pre[p] = ptr2;
  } else {
    pre[p] = 0;
  }
  modify(1, p, pre[p]);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m >> w;
  for (int i = 0; i <= 500001; i++) {
    pos[i].insert(0);
    pos[i].insert(n + 1);
    pre[i] = 0;
  }
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    pos[a[i]].insert(i);
  }
  for (int i = 1; i <= n; i++) {
    int p = *pos[w - a[i]].upper_bound(i);
    if (isBetween(p) && i > pre[p]) {
      pre[p] = i;
    }
  }
  build(1, 1, n);
  int cnt = 0;
  while (m--) {
    int op;
    cin >> op;
    if (op == 1) {
      int x, y;
      cin >> x >> y;
      if (a[x] == y) {
        continue;
      }
      pos[a[x]].erase(x);
      pos[y].insert(x);
      modifyPre(x, y);
      modifyPre(*pos[a[x]].upper_bound(x), a[x]);
      modifyPre(*pos[w - a[x]].upper_bound(x), w - a[x]);
      modifyPre(*pos[y].upper_bound(x), y);
      modifyPre(*pos[w - y].upper_bound(x), w - y);
      a[x] = y;
    } else {
      int l, r;
      cin >> l >> r;
      l ^= cnt;
      r ^= cnt;
      if (l > r) {
        swap(l, r);
      }
      int maxv = query(1, max(1, l), min(n, r));
      if (isBetween(maxv, l, r)) {
        cnt++;
        cout << "Yes\n";
      } else {
        cout << "No\n";
      }
    }
  }
  return 0;
}

Little Pony and Lord Tirek

传送门：Little Pony and Lord Tirek

题意：有$n$只小马，每只马有三种属性，分别为初始法力值，可拥有的最大法力值和单位时间内恢复的法力值。接着有$m$条指令，每条指令要求计算在时间$t$时，$[l, r]$内的所有小马法力值总和并将区间内每只小马法力值清零。

思路：每次查询后会将区间清零，也就是说我们可以将之前不同时间查询的区间合并起来，具体可以看图。

这利用了颜色段均摊的方法，时间复杂度是均摊的，我们可以用$set$存每个段上一次的时间。对于当前的查询，我只需要遍历红色区间内所有段进行计算，计算完后将零散的段删除，合并成一个大的段。如果边界处不是完全包含，则需要将原来边界的段分成两块，一块保持不变，一块并进来。

现在的问题是如何计算每段的贡献。我们如果将下标看作横坐标，将时间看作纵坐标，该问题就转化成了二维数点。首先将每只小马从$0$开始恢复满法力值的时间计算出来记作$p$，假如我当前的的查询时间和上一次的查询时间相隔了$x$，进行分类讨论，对于所有$p \le x$的小马，它们的贡献是$\sum_{i=l}^{r}m[i]$；对于所有$p \gt x$的小马，它们的贡献是$x * \sum_{i=l}^{r}r[i]$。我们可以用主席树维护$m$和$r$的和。由于初始时法力值不全是$0$，所以需要特判一下最开始的时间。在写这题的时候发现$set$存结构体有很多坑一定要注意。

代码：

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e5 + 5;
struct Node {
  int l, r, t, ok;
  bool operator < (const Node& rhs) const {
    if (l != rhs.l) return l < rhs.l;
    if (r != rhs.r) return r < rhs.r;
    if (t != rhs.t) return t < rhs.t;
    return ok < rhs.ok;
  }
};
struct TreeNode {
  int l, r;
  long long sum;
} tree[MAX * 70];
int rootM[MAX], rootR[MAX], idx;
int si[MAX], mi[MAX], ri[MAX], n, q;
set<Node> st;

void modify(int l, int r, int pre, int& now, int x, int y) {
  now = ++idx;
  tree[now] = tree[pre];
  tree[now].sum += y;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (x <= mid) modify(l, mid, tree[pre].l, tree[now].l, x, y);
  else modify(mid + 1, r, tree[pre].r, tree[now].r, x, y);
}

long long query(int l, int r, int L, int R, int ql, int qr) {
  if (l > qr || r < ql) return 0;
  if (ql <= l && r <= qr) {
    return tree[R].sum - tree[L].sum;
  }
  int mid = (l + r) >> 1;
  return query(l, mid, tree[L].l, tree[R].l, ql, qr)
          + query(mid + 1, r, tree[L].r, tree[R].r, ql, qr);
}

long long query(Node node, int now) {
  int l = node.l, r = node.r, last = node.t, ok = node.ok;
  int x = now - last;
  long long ans = 0;
  if (ok) {
    ans = query(0, 100000, rootM[l - 1], rootM[r], 1, x)
            + query(0, 100000, rootR[l - 1], rootR[r], x + 1, 100000) * x;
  } else {
    for (int i = l; i <= r; i++) {
      ans += min((long long) mi[i], (long long) si[i] + (long long) ri[i] * x);
    }
  }
  return ans;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> si[i] >> mi[i] >> ri[i];
    modify(0, 100000, rootM[i - 1], rootM[i], ri[i] ? ((mi[i] + ri[i] - 1) / ri[i]) : 0, ri[i] ? mi[i] : 0);
    modify(0, 100000, rootR[i - 1], rootR[i], ri[i] ? ((mi[i] + ri[i] - 1) / ri[i]) : 0, ri[i]);
  }
  st.insert({1, n, 0, 0});
  cin >> q;
  while (q--) {
    int t, l, r;
    cin >> t >> l >> r;
    auto lptr = --st.upper_bound({l, INT_MAX, 0, 0});
    auto rptr = --st.upper_bound({r, INT_MAX, 0, 0});
    long long ans = 0;
    if (lptr == rptr) {
      int L = lptr->l, R = lptr->r, T = lptr->t, ok = lptr->ok;
      st.erase(lptr);
      ans += query({max(l, L), min(r, R), T, ok}, t);
      if (l > L) {
        st.insert({L, l - 1, T, ok});
      }
      if (r < R) {
        st.insert({r + 1, R, T, ok});
      }
      st.insert({l, r, t, 1});
    } else {
      set<Node>::iterator it = st.end(), temp = lptr;
      for (auto ptr = ++temp; ptr != rptr; ptr++) {
        if (it != st.end()) {
          st.erase(it);
          it = st.end();
        }
        ans += query({ptr->l, ptr->r, ptr->t, ptr->ok}, t);
        it = ptr;
      }
      if (it != st.end()) {
        st.erase(it);
        it = st.end();
      }
      ans += query({l, lptr->r, lptr->t, lptr->ok}, t);
      ans += query({rptr->l, r, rptr->t, rptr->ok}, t);
      if (l > lptr->l) {
        st.insert({lptr->l, l - 1, lptr->t, lptr->ok});
      }
      if (r < rptr->r) {
        st.insert({r + 1, rptr->r, rptr->t, rptr->ok});
      }
      st.erase(lptr);
      st.erase(rptr);
      st.insert({l, r, t, 1});
    }
    cout << ans << "\n";
  }
  return 0;
}

Frequency Problem

传送门：Frequency Problem (Easy Version) 、Frequency Problem (Hard Version)

题意：给了一个序列，求最长的满足区间众数有至少两种的区间长度。Easy和Hard版的区别在于Easy的值域为$[1,100]$，而Hard版为$[1,200000]$。

思路：这题有一个结论，对于答案所在的区间，其中的一个众数一定是全局的众数。我们令全局众数为$x$。

对于Easy版，我们可以枚举每一个数$y$，将所有为$x$的位置设为$1$，所有$y$的位置设为$-1$，其余设为$0$，然后做前缀和并记录下位置，找到一个最大的区间使得该区间和为$0$即为答案。

而对于Hard版，我们首先设置一个$lim=sqrt(n)$，可以发现，出现次数大于等于$lim$的数的个数不会超过$\frac{n}{lim}$个，我们同样让这些数像Easy版那样去遍历，此时复杂度为$O(n \sqrt{n})$。而出现次数少于$lim$的数，我们可以枚举出现次数，然后利用双指针，维护一个区间，使得该区间内至少出现两个数的出现次数为我们枚举的次数，复杂度同样是$O(n \sqrt{n})$。

代码：

#include <bits/stdc++.h>
using namespace std;

const int MAX = 2e5 + 5;
int a[MAX], b[MAX], c[MAX], n;
int pos[MAX << 1];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  int lim = int(sqrt(n)), cnt = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    b[a[i]]++;  // 统计每个数字的出现次数
    cnt += (b[a[i]] == 1);  // 统计有多少不同的数
  }
  if (cnt == 1) {  // 特判
    cout << "0\n";
    return 0;
  }
  int num = max_element(b + 1, b + n + 1) - b;  // 全局众数
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    if (b[i] >= lim) {  // 出现lim次以上的数的个数不会超过n/lim=sqrt(n)个,复杂度n*sqrt(n)
      int sum = 0;
      for (int i = 0; i <= n * 2; i++) pos[i] = n + 1;
      pos[n] = 0;
      for (int j = 1; j <= n; j++) {
        if (a[j] == num) {
          sum++;
        } else if (a[j] == i) {
          sum--;
        }
        if (pos[sum + n] == n + 1) {  // 记录前缀和第一次出现的位置
          pos[sum + n] = j;
        } else {
          ans = max(ans, j - pos[sum + n]);
        }
      }
    }
  }
  // 出现次数少于lim的数,枚举这些数的个数,然后再原序列上进行双指针扫描,确保每个数最多不超过k次
  for (int i = 1; i < lim; i++) {
    int l = 1, r = 0, cntx = 0;
    while (l <= n) {
      while (r < n && c[a[r + 1]] + 1 <= i) {
        r++;
        c[a[r]]++;
        cntx += (c[a[r]] == i);
      }
      if (cntx >= 2) {
        ans = max(ans, r - l + 1);
      }
      cntx -= (c[a[l]] == i);
      c[a[l]]--;
      l++;
    }
  }
  cout << ans << "\n";
  return 0;
}