2019-09-21 16:51 中国矿业大学 C++

关注

CodeChef Match the Streams

题目链接：传送门

题目描述：

给定两个序列 $A_{1},...,A_{N}$ 和 $B_{1},...,B_{N}$ 。定义序列 $A$ 和 $B$ 的相似度为满足 $A_{i}=B_{i}$ 的下标 $i$ 的数量。
你需要回答 $Q$ 个询问。每个询问给定参数 $l,r,c$ ，你需要将 $A_{l},A_{l+1},...,A_{r}$ 更改为 $c$ ，然后计算序列 $A$ 和 $B$ 的相似度。
询问强制在线，具体见输入格式。

输入格式：

输入的第一行包含一个整数 $T$ ，代表测试数据的组数。接下来是 $T$ 组数据。
每组数据的第一行包含两个整数 $N$ 和 $Q$ 。第二行包含 $N$ 个整数 $A_{1},...,A_{N}$ 。第三行包含 $N$ 个整数 $B_{1},...,B_{N}$ 。
接下来 $Q$ 行，每行包含三个整数 $x,y,z$ ，代表一个询问，你需要按照如下方式解码：

记上一询问的答案为 $P_r$ 。 $\star\star$ 在第一个询问前， $P_r$ 为两序列初始时的相似度 $\star\star$ 。
这一询问的 $l=x\oplus P_r$ ， $r=y\oplus P_r$ ， $c=z\oplus P_r$ 。

输出格式：

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

样例输入：

样例输出：

1
0
2

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

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

用一颗线段树维护 $A[i]==B[i]$ 的 $bool$ 序列。
每次区间修改只会影响 $[l,r]$ 内的 $B[i]==c$ 的位置。 $B$ 数组是不变的，直接用动态开点的线段树维护出每个值的区间。
即多颗线段树，每颗线段树内的点，权值相同，位置不变。
例如 $1 3 2 1 4 2 4$ 这个序列会产生四棵线段树： $1..1...$
$..2..2.$
$.3.....$
$....4.4$
由于值域太大所以这里要用 $map$ 来存每个<stron>的根节点
区间修改为 $[l,r]$ 为 $c$ ，则新的贡献就是<stron> $[c]$ 的区间 $[l,r]$ 的大小
也就是有几个叶节点
具体的，并不是每次要在动态开点上面查询
而是随 $A$ 的线段树的查询函数一同递归
时间复杂度 $\Theta(nlogn)$
空间复杂度 $\Theta(nlog(inf))$ </stron></stron>

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

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：

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

Explanation：

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

Time Complexity Analysis:

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

一番魔改的官方正解 $stl$ 代码

#include <bits/stdc++.h>

using namespace std;
#define mp make_pair

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;
}