CodeChef Match the Streams

题目链接：​​传送门​​ 题目中的pdf翻译：

题目描述：

给定两个序列和。定义序列和的相似度为满足的下标的数量。
你需要回答个询问。每个询问给定参数，你需要将更改为，然后计算序列和的相似度。
询问强制在线，具体见输入格式。

输入格式：

输入的第一行包含一个整数，代表测试数据的组数。接下来是组数据。
每组数据的第一行包含两个整数和。第二行包含个整数。第三行包含个整数。
接下来行，每行包含三个整数，代表一个询问，你需要按照如下方式解码：

• 记上一询问的答案为。在第一个询问前，为两序列初始时的相似度。
• 这一询问的，，。

输出格式：

对于每个询问，输出一行，包含一个整数，代表操作后两序列的相似度。

样例输入：

1
4 3
1 2 3 4
1 1 3 5
0 1 0
0 5 3
1 4 1

样例输出：

1
0
2

这题的官方英文题解在​​这里​​​ 给的做法是
就是用维护每个值相同的连续的区间
里二分来统计答案
个人感觉比较难写，因为迭代器的细节太多
下面给出了我自己的翻译和代码

讨论区还给出了两种正常的做法
一种是分块，复杂度要高一些，带一个根号
还有一个就是线段树，只带一个
按理说是比官方题解要跑得快的

用一颗线段树维护的序列。
每次区间修改只会影响内的的位置。
数组是不变的，直接用动态开点的线段树维护出每个值的区间。
即多颗线段树，每颗线段树内的点，权值相同，位置不变。
例如这个序列会产生四棵线段树：




由于值域太大所以这里要用来存每个点开线段树的根节点
区间修改为为，则新的贡献就是点开线段树的区间的大小
也就是有几个叶节点
具体的，并不是每次要在动态开点上面查询
而是随的线段树的查询函数一同递归
时间复杂度
空间复杂度

#include <bits/stdc++.h>
#define

using namespace std;
typedef long long ll;
const int treesize = 1 << 18;
const int maxsize = A * 30;
struct node {int l, r, w, f;}tree[treesize];
int n, q, a[A], b[A], lc[maxsize], rc[maxsize], d[maxsize];
int T, cnt, l, r, c;
template<typename B>
void build(B k, B l, B r) {
  tree[k].l = l; tree[k].r = r; tree[k].f = -1;
  if (l == r) {tree[k].w = a[l] == b[l]; return;}
  int m = (l + r) >> 1;
  build(k << 1, l, m); build(k << 1 | 1, m + 1, r);
  tree[k].w = tree[k << 1].w + tree[k << 1 | 1].w;
}
template<typename V>
void update_val(V &k, V l, V r, V pos) {
  if (!k) k = ++cnt, lc[k] = rc[k] = d[k] = 0;
  d[k]++;
  if (l == r) return;
  int m = (l + r) >> 1;
  if (pos <= m) update_val(lc[k], l, m, pos);
  else update_val(rc[k], m + 1, r, pos);
}
template<typename L>
void update_lazy(L k, L l, L r, L val) {
  if (tree[k].l >= l and tree[k].r <= r) {
    tree[k].f = val;
    tree[k].w = d[val];
    return;
  }
  int m = (tree[k].l + tree[k].r) >> 1;
  if (~tree[k].f) {
    tree[k << 1].f = lc[tree[k].f]; tree[k << 1 | 1].f = rc[tree[k].f];
    tree[k << 1].w = d[lc[tree[k].f]]; tree[k << 1 | 1].w = d[rc[tree[k].f]];
    tree[k].f = -1;
  }
  if (l <= m) update_lazy(k << 1, l, r, lc[val]);
  if (r > m) update_lazy(k << 1 | 1, l, r, rc[val]);
  tree[k].w = tree[k << 1].w + tree[k << 1 | 1].w;
}
inline char Getchar() {
  static char buf[10000], *p1 = buf, *p2 = buf;
  return p1 == p2 and (p2 = (p1 = buf) + fread(buf, 1, 10000, stdin), p1 == p2) ? EOF : *p1++;
}
template<class T>
void read(T &x) {
  x = 0; char ch = Getchar();
  while (!isdigit(ch)) ch = Getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = Getchar();
}
inline void write(int x) {
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}

int main(int argc, char const *argv[]) {
  read(T);
  while (T--) {
    read(n); read(q); cnt = 0; map<int, int> mm;
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int i = 1; i <= n; i++) read(b[i]), update_val(mm[b[i]], 1, n, i);
    build(1, 1, n);
    while (q--) {
      read(l); read(r); read(c);
      l = l ^ tree[1].w; r = r ^ tree[1].w; c = c ^ tree[1].w;
      if (l > r) swap(l, r);
      update_lazy(1, l, r, mm[c]);
      write(tree[1].w); puts("");
    }
  }
  return 0;
}

下面是我自己翻译的官方题解，有些地方进行了删减（有语义错误还请指出）

Super Quick Explanation：

将连续的且拥有相同值的位置存贮到平衡树中。初始时计算相似值，更新序列的值同时更新相似值。
利用序列不变，预处理出内值为的位置个数。
最后在时间复杂度分析部分证明了该方法的有效性。

Explanation：

注意一个事实，假设我们在对的修改之前求出了目前这个序列的相似度，我们可以知道，两个序列相同的位置只会在更新的范围之内的时候才改变，其他的位置都会保持不变。这样，我们就能计算出在更新范围内的更新导致的两个序列相似性的变化，也就是维护答案。
我们用另一种方式来代表序列，定义一个三元组表示序列的元素在区间内为这个值，并且把它们存储在一个集合中，按左端点排序。
首先来讨论更新，假设更新的范围是，想想序列在更新之后会是什么样子。在更新范围内的集合将会被修改，完全位于更新范围内的集合将被删除并插入一个新的集合。
假设在更新前，我们的序列的更新范围内有个位置和序列相同，那么答案会在更新后减少，因为这些位置被修改了。假设更新后在更新范围内序列有个数和序列相同，那么答案就会增加。所以，在每次更新之后，答案会变成。
我们首先计算，我们知道，在更新后，所有在更新范围内的数会变成，所以与序列更新范围内的且值为的位置的数量相同。
这里对边界的处理要十分小心。
假设我们的数组为，那么我们维护的集合就是（编号从开始）。把更新为，那么集合会变成。
我们仍然需要解决那个子问题，给一个序列，求出内值为的位置个数。
我们把值压缩到数组中，用一个有序的对应于数组中存储在序列中的每一个值，如果询问的时候没有对应值的，那么序列就没有这个值。否则我们可以用前缀和解决中的值个数。综上问题可用二分解决，也就是的lower_bound，复杂度（或者更快，准确的来说是）。

Time Complexity Analysis:

首先，在最开始，无论如何不会超过个，成立的时候当且仅当每两个连续的数都不相同。
然后，我们找到可能的最大插入次数。我们知道，一次修改最多改变三个范围，和两个左右边界。这样我们在每次询问可以插入最多个集合，也就是最多有次插入，可以近似看成。
最后，删除的集合的总数不会超过初始集合数加上后来插入的集合个数，所以删除也是的。
每次插入和删除的时间复杂度是的（在中二分），所以这个解法的最坏时间复杂度是。对序列的预处理只会是的，因此复杂度主要由询问决定。

一番魔改的官方正解代码

#include <bits/stdc++.h>

using namespace std;
#define

int T, n, q, ans, a[100010], b[100010], l, r, c;
vector<int> v[100010];
map<int, int> m;
void add(int l, int r, int x) {
    if (m.find(x) == m.end()) return;
    x = m[x];
    ans += upper_bound(v[x].begin(), v[x].end(), r) - lower_bound(v[x].begin(), v[x].end(), l);
}
void remove(int l, int r, int x) {
    if (m.find(x) == m.end()) return;
    x = m[x];
    ans -= upper_bound(v[x].begin(), v[x].end(), r) - lower_bound(v[x].begin(), v[x].end(), l);
}
template<class T> void read(T &x) {
    x = 0; char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
}
inline void write(int x) {
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

int main(int argc, char const *argv[]) {
    read(T);
    while (T--) {
        /*---------------------input and init------------------------*/
        read(n); read(q); set<pair<int, int> > s;
        for (int i = 1; i <= n; i++) read(a[i]), s.insert(mp(i, a[i]));
        m.clear(); int cnt = 0; ans = 0;
        for (int i = 1; i <= n; i++) {
            read(b[i]);
            if (a[i] == b[i]) ans++;
            if (m.find(b[i]) == m.end()) m[b[i]] = cnt++;
            v[m[b[i]]].push_back(i);
        }
        /*------------------------------------------------------------*/
        set<pair<int, int> >::iterator it, it1;
        while (q--) {
            read(l); read(r); read(c);
            l ^= ans; r ^= ans; c ^= ans;
            if (l > r) swap(l, r);
            it = s.lower_bound(mp(l, 0));
            if (it == s.end() or it->first != l) s.insert(mp(l, (*--it).second));
            it = s.lower_bound(mp(r + 1, 0));
            if (it == s.end() or it->first != r + 1) s.insert(mp(r + 1, (*--it).second));
            while (1) {
                it = s.lower_bound(mp(l, 0));
                if (it->first == r + 1) break;
                it1 = it; it1++;
                remove(it->first, it1->first - 1, it->second);
                s.erase(it);
            }
            add(l, r, c); s.insert(mp(l, c));
            write(ans); puts("");
        }
        for (int i = 0; i < cnt; i++) v[i].clear();
    }
    return 0;
}