小美的彩带

[题目链接](https://www.nowcoder.com/practice/5cf15987d8654d69b67e46fb25fe051b)

思路

彩带由长度为 $n$ 的颜色序列无限循环构成，即 $c[i] = a[i \bmod n]$ （对所有整数 $i$ ）。有两个独立的指针：左指针初始在位置 $0$ ，右指针初始在位置 $-1$ 。每次操作：

L x：从左指针处向右裁剪 $x$ 个位置，即取 $[\text{leftPtr}, \text{leftPtr}+x-1]$ 这一段，然后 $\text{leftPtr} \mathrel{+}= x$ 。
R x：从右指针处向左裁剪 $x$ 个位置，即取 $[\text{rightPtr}-x+1, \text{rightPtr}]$ 这一段，然后 $\text{rightPtr} \mathrel{-}= x$ 。

每次输出裁剪段中不同颜色的数量。

关键观察

由于颜色序列以 $n$ 为周期循环，任意连续段的颜色只取决于起始位置对 $n$ 取模后的值以及段的长度：

若 $x \geq n$ ：段中必然包含完整的一个周期，答案就是数组中不同颜色的总数。
若 $x < n$ ：需要查询环形数组上从某个起点开始、长度为 $x$ 的子段中有多少种不同的颜色。

莫队算法

将环形数组 复制一份 得到长度为 $2n$ 的数组 $\text{arr}[0..2n-1]$ ，其中 $\text{arr}[i] = a[i \bmod n]$ 。对于起点 $s = ((\text{start} \bmod n) + n) \bmod n$ 、长度为 $x$ 的查询，对应的区间就是 $[s, s+x-1]$ ，其中 $s+x-1 < 2n$ （因为 $x < n$ ）。

这样问题就转化为：在长度为 $2n$ 的数组上回答若干 区间颜色数 查询——经典的莫队算法场景。

莫队算法步骤：

将所有查询按左端点所在块编号排序，同一块内按右端点排序（奇偶优化）。
维护当前窗口 $[cl, cr]$ 和一个颜色计数数组 $\text{cnt}[]$ ，以及当前不同颜色数 $\text{curDistinct}$ 。
通过逐步扩展/收缩窗口边界来回答每个查询。

复杂度分析

时间复杂度： $O((n+q)\sqrt{n})$ 。莫队算法在长度为 $2n$ 的数组上处理 $q$ 个查询，总移动次数为 $O((n+q)\sqrt{n})$ 。
空间复杂度： $O(n+q)$ 。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    // 离散化颜色
    vector<int> sorted_a = a;
    sort(sorted_a.begin(), sorted_a.end());
    sorted_a.erase(unique(sorted_a.begin(), sorted_a.end()), sorted_a.end());
    int total_distinct = sorted_a.size();

    for(int i = 0; i < n; i++){
        a[i] = lower_bound(sorted_a.begin(), sorted_a.end(), a[i]) - sorted_a.begin();
    }

    // 复制数组处理环形查询
    int N = 2 * n;
    vector<int> arr(N);
    for(int i = 0; i < N; i++) arr[i] = a[i % n];

    // 两个独立指针
    long long left_ptr = 0;
    long long right_ptr = -1;

    struct Query {
        int l, r, idx;
    };

    vector<int> ans(q);
    vector<Query> queries;

    for(int i = 0; i < q; i++){
        char c;
        long long x;
        cin >> c >> x;

        if(x >= n){
            ans[i] = total_distinct;
            if(c == 'L') left_ptr += x;
            else right_ptr -= x;
            continue;
        }

        long long start;
        if(c == 'L'){
            start = left_ptr;
            left_ptr += x;
        } else {
            start = right_ptr - x + 1;
            right_ptr -= x;
        }

        int s = ((start % n) + n) % n;
        queries.push_back({s, s + (int)x - 1, i});
    }

    if(!queries.empty()){
        // 莫队排序
        int block = max(1, (int)sqrt(N));
        sort(queries.begin(), queries.end(), [&](const Query& a, const Query& b){
            int ba = a.l / block, bb = b.l / block;
            if(ba != bb) return ba < bb;
            return (ba & 1) ? (a.r > b.r) : (a.r < b.r);
        });

        vector<int> cnt(total_distinct, 0);
        int cur_distinct = 0;
        int cl = 0, cr = -1;

        auto add = [&](int pos){
            if(cnt[arr[pos]]++ == 0) cur_distinct++;
        };
        auto rem = [&](int pos){
            if(--cnt[arr[pos]] == 0) cur_distinct--;
        };

        for(auto& qr : queries){
            while(cr < qr.r) add(++cr);
            while(cl > qr.l) add(--cl);
            while(cr > qr.r) rem(cr--);
            while(cl < qr.l) rem(cl++);
            ans[qr.idx] = cur_distinct;
        }
    }

    for(int i = 0; i < q; i++) cout << ans[i] << '\n';
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        DataInputStream din = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
        int n = nextInt(din);
        int q = nextInt(din);

        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = nextInt(din);

        // 离散化
        int[] sorted = a.clone();
        Arrays.sort(sorted);
        int totalDistinct = 1;
        for (int i = 1; i < n; i++) {
            if (sorted[i] != sorted[i - 1]) totalDistinct++;
        }
        int[] uniq = new int[totalDistinct];
        uniq[0] = sorted[0];
        int uid = 1;
        for (int i = 1; i < n; i++) {
            if (sorted[i] != sorted[i - 1]) uniq[uid++] = sorted[i];
        }
        for (int i = 0; i < n; i++) {
            a[i] = Arrays.binarySearch(uniq, a[i]);
        }

        int N = 2 * n;
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) arr[i] = a[i % n];

        long leftPtr = 0;
        long rightPtr = -1;

        int[] ans = new int[q];
        int[] qlArr = new int[q], qrArr = new int[q], qiArr = new int[q];
        int qCount = 0;

        for (int i = 0; i < q; i++) {
            int c = nextChar(din);
            long x = nextLong(din);

            if (x >= n) {
                ans[i] = totalDistinct;
                if (c == 'L') leftPtr += x;
                else rightPtr -= x;
                continue;
            }

            long start;
            if (c == 'L') {
                start = leftPtr;
                leftPtr += x;
            } else {
                start = rightPtr - x + 1;
                rightPtr -= x;
            }

            int s = (int) ((start % n + n) % n);
            qlArr[qCount] = s;
            qrArr[qCount] = s + (int) x - 1;
            qiArr[qCount] = i;
            qCount++;
        }

        if (qCount > 0) {
            int block = Math.max(1, (int) Math.sqrt(N));
            int[] order = new int[qCount];
            for (int i = 0; i < qCount; i++) order[i] = i;
            mergeSort(order, 0, qCount, qlArr, qrArr, block);

            int[] cnt = new int[totalDistinct];
            int curDistinct = 0;
            int cl = 0, cr = -1;

            for (int i = 0; i < qCount; i++) {
                int idx = order[i];
                int tl = qlArr[idx], tr = qrArr[idx];
                while (cr < tr) { if (cnt[arr[++cr]]++ == 0) curDistinct++; }
                while (cl > tl) { if (cnt[arr[--cl]]++ == 0) curDistinct++; }
                while (cr > tr) { if (--cnt[arr[cr--]] == 0) curDistinct--; }
                while (cl < tl) { if (--cnt[arr[cl++]] == 0) curDistinct--; }
                ans[qiArr[idx]] = curDistinct;
            }
        }

        StringBuilder sb = new StringBuilder(q * 4);
        for (int i = 0; i < q; i++) sb.append(ans[i]).append('\n');
        System.out.print(sb);
    }

    static void mergeSort(int[] arr, int lo, int hi, int[] ql, int[] qr, int block) {
        if (hi - lo <= 1) return;
        int mid = (lo + hi) / 2;
        mergeSort(arr, lo, mid, ql, qr, block);
        mergeSort(arr, mid, hi, ql, qr, block);
        int[] tmp = new int[hi - lo];
        int i = lo, j = mid, k = 0;
        while (i < mid && j < hi) {
            int ba = ql[arr[i]] / block, bb = ql[arr[j]] / block;
            boolean takeI;
            if (ba != bb) takeI = ba < bb;
            else takeI = (ba & 1) != 0 ? qr[arr[i]] > qr[arr[j]] : qr[arr[i]] < qr[arr[j]];
            if (takeI) tmp[k++] = arr[i++];
            else tmp[k++] = arr[j++];
        }
        while (i < mid) tmp[k++] = arr[i++];
        while (j < hi) tmp[k++] = arr[j++];
        System.arraycopy(tmp, 0, arr, lo, hi - lo);
    }

    private static int nextInt(DataInputStream din) throws IOException {
        int ret = 0;
        int b = din.read();
        while (b < '0' || b > '9') b = din.read();
        while (b >= '0' && b <= '9') {
            ret = ret * 10 + (b - '0');
            b = din.read();
        }
        return ret;
    }

    private static long nextLong(DataInputStream din) throws IOException {
        long ret = 0;
        int b = din.read();
        while (b < '0' || b > '9') b = din.read();
        while (b >= '0' && b <= '9') {
            ret = ret * 10 + (b - '0');
            b = din.read();
        }
        return ret;
    }

    private static int nextChar(DataInputStream din) throws IOException {
        int b = din.read();
        while (b == ' ' || b == '\n' || b == '\r') b = din.read();
        return b;
    }
}