题解：P7707 「Wdsr-2.7」百花齐放的太阳花田

题意

给定长为的序列，每个元素有两种指标：数值和颜色。其初始状态为。有次操作：

1 l r x 将区间中所有指标的元素按原下标提取出，求其颜色段个数，即极长的颜色相同的连续段数量。
2 a c 在序列末尾插入元素。

有强制在线。

思路

这题放模拟赛 T4 真是太好了。没人切出来。

数据结构。

颜色段数量问题，可以想到线段树区间合并维护。具体地，对于每一个区间，维护，分别表示区间左右端点颜色，以及当前区间颜色段个数。合并时，只需判断左区间的右端点颜色是否和右区间的左端点颜色相等，如相等答案需减一。

问题就在于这个条件。考虑到长为的区间其取值最多仅有种可能，所以我们可以对线段树上每一个节点都维护一个长度最多为的 vector，其中每个元素就对应着上面所说的节点维护的信息，但是多出一个，表示当前这个四元组只考虑指标的情况。

如何合并区间？我们可以采用类似归并排序的思想，以双指针的形式，将两个有序的 vector 融合成为一个。下面我们将左区间 vector 称为左序列，右同理。具体地，若左序列中当前遍历到的四元组和右区间的满足，且左序列中不存在其他，右序列中不存在其他，使得，那么这两个四元组可以合并为一个：。这里将左右区间交换也是可以的（即将改为）。

另外，在实现时，有一个小 trick：如果重载了结构体的 < 符号，就可以直接使用 upper_bound()，不需要手写二分。

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int MAXN = 6e5 + 10;

int n, m, k;
pii a[MAXN];

struct Node {
  int x, lc, rc, cnt;
  bool operator<(const Node &oth) const {
    return x < oth.x;
  }
  Node operator+(const Node &oth) {
    if (!x) return oth;
    if (!oth.x) return *this;
    return {max(x, oth.x), lc, oth.rc, cnt + oth.cnt - (rc == oth.lc)};
  }
};

struct SegTree {
  vector<Node> dat[MAXN << 2];
  Node E;
  #define mid (l + r >> 1)
  #define LC root << 1, l, mid
  #define RC root << 1 | 1, mid + 1, r
  #define lc(x) x << 1
  #define rc(x) x << 1 | 1
  void pushup(int root) {
    vector<Node> now;
    Node ls = E, rs = E;
    for (int i = 0, j = 0; i < dat[lc(root)].size() || j < dat[rc(root)].size(); ) {
      int val;
      if (j == dat[rc(root)].size() || (i < dat[lc(root)].size() && dat[lc(root)][i] < dat[rc(root)][j])) val = dat[lc(root)][i].x;
      else val = dat[rc(root)][j].x;
      if (i < dat[lc(root)].size() && dat[lc(root)][i].x == val) ls = dat[lc(root)][i++];
      if (j < dat[rc(root)].size() && dat[rc(root)][j].x == val) rs = dat[rc(root)][j++];
      now.push_back(ls + rs); 
    }
    dat[root].swap(now);
  }
  void update(int root, int l, int r, int pos, pii val) {
    if (l == r) {
      dat[root] = {{val.first, val.second, val.second, 1}};
      return;
    }
    if (pos <= mid) update(LC, pos, val);
    else update(RC, pos, val);
    if (r == pos) pushup(root);
  }
  Node query(int root, int l, int r, int L, int R, int val) {
    if (L <= l && R >= r) {
      auto it = upper_bound(dat[root].begin(), dat[root].end(), (Node){val, 0, 0, 0});
      return it == dat[root].begin() ? E : *prev(it);
    }
    if (L > r || R < l) return E;
    return query(LC, L, R, val) + query(RC, L, R, val);
  }
} T;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].first;
  }
  int w = n + m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].second;
    T.update(1, 1, w, i, a[i]);
  }
  for (int i = 1, op, ans = 0; i <= m; i++) {
    cin >> op;
    if (op == 1) {
      int l, r, x;
      cin >> l >> r >> x;
      l ^= ans * k, r ^= ans * k, x ^= ans * k;
      cout << (ans = T.query(1, 1, w, l, r, x).cnt) << '\n';
    } else {
      int x, y;
      cin >> x >> y;
      x ^= ans * k, y ^= ans * k;
      T.update(1, 1, w, ++n, {x, y});
    }
  }
  return 0;
}