方法思路

这道题目要求处理一个环形数组，并回答多个查询，每个查询询问在移动后的区间内不同颜色的数量。关键在于高效处理这些查询，避免每次查询都重新计算不同颜色的数量。

1. 离散化处理：首先对颜色进行离散化处理，便于后续操作。
2. 记录下一个相同颜色的位置：使用一个数组next来记录每个位置的下一个相同颜色的位置，这样在处理区间时可以快速知道是否需要重新计数。
3. 处理查询：将查询按照起始位置排序，使用树状数组（Fenwick Tree）来动态维护当前区间的颜色数量。树状数组可以高效地进行点更新和区间查询。
4. 移动区间：根据查询的类型（左移或右移）调整当前区间，并利用树状数组更新颜色计数。

代码实现

Java

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

public class Main {
    static class TreeArray {
        int n;
        int[] tree;

        TreeArray(int n) {
            this.n = n;
            tree = new int[n + 2];
        }

        void insert(int idx, int val) {
            idx++;
            while (idx <= n) {
                tree[idx] += val;
                idx += idx & -idx;
            }
        }

        int query(int idx) {
            int ret = 0;
            idx++;
            while (idx > 0) {
                ret += tree[idx];
                idx -= idx & -idx;
            }
            return ret;
        }
    }

    static class Query implements Comparable<Query> {
        int s, e, idx;
        Query(int s, int e, int idx) {
            this.s = s;
            this.e = e;
            this.idx = idx;
        }
        public int compareTo(Query other) {
            return Integer.compare(this.s, other.s);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] first = br.readLine().split(" ");
        int n = Integer.parseInt(first[0]);
        int k = Integer.parseInt(first[1]);

        int[] a = new int[n];
        int[] next = new int[2 * n];
        Arrays.fill(next, -1);

        String[] parts = br.readLine().split(" ");
        for (int i = 0; i < n; i++) a[i] = Integer.parseInt(parts[i]);

        // 离散化并记录下一个相同颜色的位置
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < 2 * n; i++) {
            int val = a[i % n];
            if (map.containsKey(val)) {
                next[map.get(val)] = i;
            }
            map.put(val, i);
        }

        int curl = 0, curr = n - 1;
        int[] ans = new int[k];
        List<Query> queries = new ArrayList<>();

        for (int i = 0; i < k; i++) {
            String[] line = br.readLine().split(" ");
            char c = line[0].charAt(0);
            int x = Integer.parseInt(line[1]);

            if (x > n) {
                ans[i] = map.size();
                if (c == 'L') curl = (curl + x) % n;
                else curr = ((curr - x) % n + n) % n;
            } else if (c == 'L') {
                queries.add(new Query(curl, curl + x - 1, i));
                curl = (curl + x) % n;
            } else {
                if (curr < x) curr += n;
                queries.add(new Query(curr - x + 1, curr, i));
                curr = ((curr - x) % n + n) % n;
            }
        }

        Collections.sort(queries);
        TreeArray tree = new TreeArray(n * 2);
        map.clear();
        curl = 0;

        for (int i = 0; i < n; i++) {
            if (!map.containsKey(a[i])) {
                map.put(a[i], i);
                tree.insert(i, 1);
            }
        }

        for (Query q : queries) {
            while (curl < q.s) {
                tree.insert(curl, -1);
                if (next[curl] != -1) {
                    tree.insert(next[curl], 1);
                }
                curl++;
            }
            ans[q.idx] = tree.query(q.e);
        }

        for (int v : ans) {
            bw.write(v + "\n");
        }
        bw.flush();
    }
}

Python

import sys
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    ptr = 0
    n, k = map(int, input[ptr:ptr+2])
    ptr +=2
    a = list(map(int, input[ptr:ptr+n]))
    ptr +=n

    next_pos = [-1] * (2 * n)
    last_pos = {}
    for i in range(2 * n):
        val = a[i % n]
        if val in last_pos:
            next_pos[last_pos[val]] = i
        last_pos[val] = i

    queries = []
    ans = [0] * k
    curl, curr = 0, n - 1

    for idx in range(k):
        c = input[ptr]
        x = int(input[ptr+1])
        ptr +=2
        if x > n:
            ans[idx] = len(last_pos)
            if c == 'L':
                curl = (curl + x) % n
            else:
                curr = (curr - x) % n
        elif c == 'L':
            end = curl + x - 1
            queries.append((curl, end, idx))
            curl = (curl + x) % n
        else:
            start = curr - x + 1
            if start < 0:
                start += n
                end = curr + n
            else:
                end = curr
            queries.append((start, end, idx))
            curr = (curr - x) % n

    queries.sort()
    m = 2 * n
    fenwick = [0] * (m + 2)

    def update(pos, delta):
        pos +=1
        while pos <= m:
            fenwick[pos] += delta
            pos += pos & -pos

    def query(pos):
        res = 0
        pos +=1
        while pos >0:
            res += fenwick[pos]
            pos -= pos & -pos
        return res

    first_occurrence = {}
    for i in range(n):
        if a[i] not in first_occurrence:
            first_occurrence[a[i]] = i
            update(i, 1)

    current_left = 0
    for q in queries:
        l, r, idx = q
        while current_left < l:
            update(current_left, -1)
            if next_pos[current_left] != -1:
                update(next_pos[current_left], 1)
            current_left +=1
        ans[idx] = query(r)

    print('\n'.join(map(str, ans)))

if __name__ == '__main__':
    main()

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

struct FenwickTree {
    int n;
    vector<int> tree;

    FenwickTree(int size) : n(size), tree(size + 2, 0) {}

    void update(int idx, int delta) {
        idx++;
        while (idx <= n) {
            tree[idx] += delta;
            idx += idx & -idx;
        }
    }

    int query(int idx) {
        idx++;
        int res = 0;
        while (idx > 0) {
            res += tree[idx];
            idx -= idx & -idx;
        }
        return res;
    }
};

struct Query {
    int l, r, idx;
    Query(int l, int r, int idx) : l(l), r(r), idx(idx) {}
    bool operator<(const Query& other) const {
        return l < other.l;
    }
};

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

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

    vector<int> next_pos(2 * n, -1);
    unordered_map<int, int> last_pos;
    for (int i = 0; i < 2 * n; ++i) {
        int val = a[i % n];
        if (last_pos.count(val)) {
            next_pos[last_pos[val]] = i;
        }
        last_pos[val] = i;
    }

    vector<Query> queries;
    vector<int> ans(k, 0);
    int curl = 0, curr = n - 1;

    for (int idx = 0; idx < k; ++idx) {
        char c;
        int x;
        cin >> c >> x;
        if (x > n) {
            ans[idx] = last_pos.size();
            if (c == 'L') {
                curl = (curl + x) % n;
            } else {
                curr = (curr - x) % n;
                if (curr < 0) curr += n;
            }
        } else if (c == 'L') {
            int end = curl + x - 1;
            queries.emplace_back(curl, end, idx);
            curl = (curl + x) % n;
        } else {
            int start = curr - x + 1;
            int end = curr;
            if (start < 0) {
                start += n;
                end += n;
            }
            queries.emplace_back(start, end, idx);
            curr = (curr - x) % n;
            if (curr < 0) curr += n;
        }
    }

    sort(queries.begin(), queries.end());
    FenwickTree fenwick(2 * n);
    unordered_map<int, int> first_occurrence;
    for (int i = 0; i < n; ++i) {
        if (!first_occurrence.count(a[i])) {
            first_occurrence[a[i]] = i;
            fenwick.update(i, 1);
        }
    }

    int current_left = 0;
    for (const auto& q : queries) {
        while (current_left < q.l) {
            fenwick.update(current_left, -1);
            if (next_pos[current_left] != -1) {
                fenwick.update(next_pos[current_left], 1);
            }
            current_left++;
        }
        ans[q.idx] = fenwick.query(q.r);
    }

    for (int num : ans) {
        cout << num << '\n';
    }

    return 0;
}