P1366 双指针

Usada_Pekora · 2022-12-18 18:29:02 · 题解

题意很清晰，在此不再分析，解法要求时间空间都是线性的。

注意到题目给出了一个特殊性质：a,b 都是升序的。

也就是说与 a_i 相等的那些 b_{l_1\sim r_1} 和与 a_{i+1} 相等的那些 b_{l_2\sim r_2} 是彼此不相交的一些数，即若他们都存在，则一定有 l_2\gt r_1。

于是从左到右扫一下就好了，对于每个 a_i 我们需要统计值域在 (a_{i-1},a_i] 的 b_j，维护一个 j 即可。具体地，我们每次从第一个大于 a_{i-1} 的 b_j 开始往右找到第一个大于 a_i 的 b_{j^{'}}，容易发现若我们每次从前一个数继承 j，则 i 的移动次数是 O(n) 的，j 的移动次数是 O(m) 的。

复杂度 O(\sum(n+m))。

#include <bits/stdc++.h>
using namespace std;
inline uint64_t read() {
    uint64_t x = 0;
    char ch = getchar();
    while (!isdigit(ch))
        ch = getchar();
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x;
}
uint64_t a[10000001], b[10000001];
signed main() {
    for (int T = read(), n, m; (T--) && (n = read(), m = read()); ) {
        for (int i = 1; i <= n; i++)
            a[i] = read();
        for (int i = 1; i <= m; i++)
            b[i] = read();
        int j = 1, cnt = 0, ans = 0;
        for (int i = 1; i <= n; i++) {
            cnt = 0;
            while (j <= m && a[i] >= b[j]) {
                cnt += (a[i] == b[j]);
                j++;
            }
            ans ^= cnt;
        }
        printf("%d\n", ans);
    }
    return 0;
}