P3901 数列找不同 题解

2023-12-28 21:54:10

给定一个数列 \(\{A_n\}\)，需要回答 \(Q\) 次询问：第 \(i\) 次询问给定一个区间 \([L_i,R_i]\)，问该区间内的数是否各不相同？

\(1\leq n,Q \leq 10^5,1\leq A_i\leq 10^5\)

暴力：\(O(n^2)\)

对于每次询问，我们 \(O(n)\) 的判断一下区间内的数是否各不相同，方法很简单：开一个 \(vis\) 数组表示该区间内每个数出现的次数（如果别的题目的值域没有这题这么友好，那就开一个 \(map\) 吧），随后从前到后遍历每一个数，并随时记录，一旦某个数出现过多次，则输出 \(\text{No}\)。倘若未出现这种情况，则输出 \(\text{Yes}\) 。

const int N = 100010;
int vis[N];
bool check(int l, int r) {
    memset(vis, 0, sizeof(vis));
    for (int i = l; i <= r; ++i) {
        vis[a[i]]++;
        if (vis[a[i]] > 1) return false;
    }
    return true;
}

显然，这个方法的时间复杂度为 \(O(nQ)\) ，对于 \(10^5\) 的数据规模是力不从心的。

双指针+二分：\(O(Q\log n)\)

倘若 \([L_1,R_1]\) 是一个符合要求的区间，且 \(L_1\leq L_2\leq R_2\leq R_1\) ，那么显然区间 \([L_2,R_2]\) 也是一个符合要求的区间。按照这一准则，我们将所有可以去除的多余区间去掉，最后剩下 \(k\) 段区间，不妨记第 \(i\) 个区间为 \([L_i,R_i]\)，那么显然有 \(1\leq L_1<L_2\cdots<L_k\) ，\(R_1<R_2<\cdots<R_k\leq n\)。既然如此，我们不妨采取双指针的方式来求出所有区间。

const int N = 100010;
int n, a[N], vis[N];
//two-pointer
int j = 1, cnt = 0;
for (int i = 1; i <= n; ++i) {
    bool flag = 0;
    while (cnt == 0 && j <= n) {
        j++;
        vis[a[j]]++;
        if (vis[a[j]] > 1) cnt++;
        flag = 1;
    }
    if (flag) vec.push_back((Node){i, j - 1});
    vis[a[i]]--;
    if (vis[a[i]] == 1) cnt--;
}

在知道了所有区间后，我们对于每次询问，都可以通过 \(O(\log n)\) 的方式来判断其是否是某个区间的子区间。方法还算简单：假设询问给出了区间 \([a,b]\)，那我们在 \(vec\) 中进行二分，找出小于等于 \(a\) 的最大值 \(L_i\)，随后判断是否 \(b\leq R_i\) 即可。

while (q--) {
    int L, R;
    scanf("%d%d", &L, &R);
    int l = -1, r = vec.size() - 1;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (vec[mid].l <= L) l = mid;
        else r = mid - 1;
    }
    puts(R <= vec[l].r ? "Yes" : "No");
}

双指针的复杂度是 \(O(n)\)，处理询问的最坏复杂度是 \(O(Q\log n)\)，因此总时间复杂度为 \(O(Q\log n)\)。

双指针+线性优化：从 \(O(n^2)\) 到 \(O(n)\)

同样的，我们需要先双指针求出所有的区间。

如果我们记 \(ans_i\) 为位置 \(i\) 所能到达的最远位置坐标，那么我们显然应该从左到右进行更新，如下面所示：

const int N = 100010;
int q, ans[N];
struct Node {
    int l, r;
};
vector<Node> vec;
//
void updateAns(int l, int r) {
    for (int i = l; i <= r; ++i) ans[i] = r;
}
//主程序
for (int i = 0; i < vec.size(); ++i)
    updateAns(vec[i].l, vec[i].r);
while (q--) {
    int L, R;
    scanf("%d%d", &L, &R);
    puts(R <= ans[L] ? "Yes" : "No");
}

虽然这段代码可以在洛谷上面通过，但是它的最坏复杂度任然是 \(O(n^2)\)，我们必须要想办法把它压下去。

用线段树可以压到 \(O(n\log n)\)，但是有点大材小用了。

实际上，\(ans_n\) 的每一块都只会被一个值覆盖，考虑到 \(1\leq L_1<L_2\cdots<L_k\) ，\(R_1<R_2<\cdots<R_k\leq n\)，我们在每一次覆盖的时候，都给右边界取一次 \(min\)，这样可以避免一段区间被多次覆盖。

for (int k = 0; k < vec.size(); ++k) {
    int l1, l2, r;
    l1 = vec[k].l, r = vec[k].r;
    l2 = (k == vec.size() - 1) ? n + 1 : vec[k + 1].l;
    for (int i = l1; i <= min(r, l2); ++i) ans[i] = r;
}

不过比起事后亡羊补牢，我们有一个更加简便的方法：直接在双指针过程中更新 \(ans_n\)。

//完整代码
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, q, a[N];
int vis[N], ans[N];
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    //two-pointer
    int j = 1, cnt = 0;
    for (int i = 1; i <= n; ++i) {
        //j++
        while (cnt == 0 && j <= n) {
            j++;
            vis[a[j]]++;
            if (vis[a[j]] > 1) cnt++;
        }
        //update
        ans[i] = j - 1;
        //i++
        vis[a[i]]--;
        if (vis[a[i]] == 1) cnt--;
    }
    //query
    while (q--) {
        int L, R;
        scanf("%d%d", &L, &R);
        puts(R <= ans[L] ? "Yes" : "No");
    }
    return 0;
}

分块：\(O(n\sqrt{n})\)

已知状态 \([L,R]\) 的答案，倘若我们可以 \(O(1)\) 的更新到 \([L-1,R],[L+1,R],[L,R-1],[L,R+1]\)，那么我们都可以对所有询问进行离线并排序（进行分块，以左端点所在块的编号为第一关键字，右端点为第二关键字），随后从前到后进行暴力计算。可以证明，这样的最终复杂度为 \(O(n\sqrt{n})\)。

详细的分块教程，大家可以去 OI-WiKi 详细学习，这里只给出代码。

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, q, k, a[N];
int answer, cnt[N], ans[N];
struct Node {
    int L, R, p;
} ask[N];
bool cmp(Node a, Node b) { return a.L / k == b.L / k ? a.R < b.R : a.L < b.L; }
void remove(int p) { if (--cnt[a[p]] == 0) answer--; }
void    add(int p) { if (++cnt[a[p]] == 1) answer++; }
int main()
{
    scanf("%d%d", &n, &q);
    k = sqrt(n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= q; i++)
        scanf("%d%d", &ask[i].L, &ask[i].R), ask[i].p = i;
    sort(ask + 1, ask + 1 + q, cmp);
    int curl = 0, curr = 0;
    for (int i = 1; i <= q; i++) {
        int L = ask[i].L, R = ask[i].R;
        while (curl < L) remove(curl++);
        while (curl > L) add(--curl);
        while (curr < R) add(++curr);
        while (curr > R) remove(curr--);
        ans[ask[i].p] = (answer == R - L + 1);
    }
    for (int i = 1; i <= q; i++)
        puts(ans[i] == 1 ? "Yes" : "No");
    return 0;
}

化位置关系为区间操作：\(O(n)\)

牛客寒假集训营有一个将位置关系转化为序列操作，随后用线段树维护的题目，可以参照这篇解题报告：牛客寒假集训营3。（似乎只要是判断区间内是否有相同的数之类的题目，都可以这么搞）。

我们不妨记 \(Last_i\) 为在位置 \(i\) 前面最靠近 \(i\)，且该位置的值与 \(a_i\) 相等的位置坐标。那么对于一段询问的区间 \([L,R]\)，每个位置的 \(Last\) 值均要小于 \(L\)，即

\[\max\limits_{L\leq i\leq R}Last_i<L \]

区间最大值可以通过线段树来处理，而且这题是静态的，我们可以直接上 ST 表即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, q, k, a[N];
int vis[N], Last[N];
//ST表
int ST[N][25];
void init() {
    for (int i = 1; i <= n; ++i)
        ST[i][0] = Last[i];
    for (int k = 1; k <= 20; ++k)
        for (int i = 1; i + (1 << k) - 1 <= n; ++i)
            ST[i][k] = max(ST[i][k - 1], ST[i + (1 << (k - 1))][k - 1]);
}
inline int query(int l, int r)
{
    int k = log2(r - l + 1);
    return max(ST[l][k], ST[r - (1 << k) + 1][k]);
}
int main()
{
    //read
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    //build
    for (int i = 1; i <= n; ++i) {
        Last[i] = vis[a[i]];
        vis[a[i]] = i;
    }
    init();
    //query
    while (q--) {
        int L, R;
        scanf("%d%d", &L, &R);
        puts(query(L, R) < L ? "Yes" : "No");
    }
    return 0;
}

P3901 数列找不同 题解

上一篇：POJ3046 Ant Counting 题解


下一篇：leetcode - 6.有效的括号