题目思路

首先需要注意的是题目是持续的裁剪，就是每个操作是在上一个操作的基础上进行的，由于彩带无限长，所以只需要维护左端点和右端点当前裁剪到的位置。

考虑离线，对于裁剪长度大于n的，直接输出总的颜色数量即可，对于长度在n以内的，需要通过维护左端点和右端点先预处理好对应的彩带区间，由于彩带是无限循环的，所以可能出现从右边再到左边，这里可以将原始的彩带扩充为原来的2倍长度，这样从右边到左边也可以看做是其中的连续部分。

将得到的彩带区间进行排序，此时彩带区间之间已经互不干扰了，因为在此前我们已经通过维护左右端点得到了持续裁剪的区间，只需要计算每个区间内不同颜色数量即可。这里可以使用树状数组在nlogn的时间下得到颜色数量，我们考虑维护每个颜色最早出现的位置，由于彩带区间排序了，所以区间的左端点是不断右移的，每次左端点移动的时候，就将其代表的颜色的位置抹去，加入和它相同颜色的下一个位置。此时对于每个区间只需要求出对应区间的位置内包含了最早出现的颜色的位置的数量即可。

最后将离线排序后的区间对应的答案依次输出即可。时间复杂度为O(nlogn)。

代码

C++

#include <bits/stdc++.h>

using namespace std;

struct BIT {
        vector<int> bit;
        int n;
        void init(int _n) {
                n = _n;
                bit.assign(n + 1, 0);
        }
        void add(int x, int v) {
                for (++ x; x <= n; x += x & -x) {
                        bit[x] += v;
                }
        }
        int sum(int x) {
                int res = 0;
                for (++ x; x > 0; x -= x & -x) {
                        res += bit[x];
                }
                return res;
        }
}bit;

int main()
{
  int n, q;
        cin >> n >> q;
        vector<int> a(n), ne(2 * n, -1);
        for (int i = 0;i < n;i++) {
                cin >> a[i];
        }
        map<int, int> mapp;
        for (int i = 0;i < 2 * n;++ i) {
                if (mapp.count(a[i % n])) {
                        ne[mapp[a[i % n]]] = i;
                }
                mapp[a[i % n]] = i;
        }
        vector<array<int, 3>> query;
        vector<int> ans(q);
        int curl = 0, curr = n - 1;
        for (int i = 0;i < q;++ i) {
                string op;
                int x;
                cin >> op >> x;
                if (x > n) {
                        ans[i] = mapp.size();
                        if (op == "L") curl = (curl + x) % n;
                        else curr = ((curr - x) % n + n) % n;
                }
                else if (op == "L") {
                        query.push_back({curl, curl + x - 1, i});
                        curl = (curl + x) % n;
                } else {
                        if (curr < x) curr += n;
                        query.push_back({curr - x + 1, curr, i});
                        curr = ((curr - x) % n + n) % n;
                        
                }
        }
        sort(query.begin(), query.end());
        curl = 0;
        bit.init(2 * n);
        mapp.clear();
        for (int i = 0;i < n;++ i) {
                if (!mapp.count(a[i])) {
                        mapp[a[i]] = i;
                        bit.add(i, 1);
                }
        }
        for (auto&t: query) {
                while (curl < t[0]) {
                        bit.add(curl, -1);
                        if (~ne[curl]) {
                                bit.add(ne[curl], 1);
                        }
                        ++ curl;
                }
                ans[t[2]] = bit.sum(t[1]);
        }
        for (int i = 0;i < q;++ i) {
                cout << ans[i] << '\n';
        }
  return 0;
}

python

class BIT:
    def __init__(self, size):
        self.n = size
        self.bit = [0] * (size + 1)

    def add(self, x, v):
        x += 1
        while x <= self.n:
            self.bit[x] += v
            x += x & -x

    def sum(self, x):
        x += 1
        res = 0
        while x > 0:
            res += self.bit[x]
            x -= x & -x
        return res


def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    
    n = int(data[idx])
    idx += 1
    q = int(data[idx])
    idx += 1

    a = [int(data[i]) for i in range(idx, idx + n)]
    idx += n
    
    ne = [-1] * (2 * n)
    mapp = {}
    for i in range(2 * n):
        if a[i % n] in mapp:
            ne[mapp[a[i % n]]] = i
        mapp[a[i % n]] = i
    
    queries = []
    ans = [0] * q
    curl = 0
    curr = n - 1
    
    for i in range(q):
        op = data[idx]
        x = int(data[idx + 1])
        idx += 2
        
        if x > n:
            ans[i] = len(mapp)
        elif op == "L":
            queries.append((curl, curl + x - 1, i))
            curl = (curl + x) % n
        else:
            if curr < x:
                curr += n
            queries.append((curr - x + 1, curr, i))
            curr = (curr - x + n) % n

    queries.sort()
    
    curl = 0
    bit = BIT(2 * n)
    mapp.clear()
    
    for i in range(n):
        if a[i] not in mapp:
            mapp[a[i]] = i
            bit.add(i, 1)

    for t in queries:
        while curl < t[0]:
            bit.add(curl, -1)
            if ne[curl] != -1:
                bit.add(ne[curl], 1)
            curl += 1
        ans[t[2]] = bit.sum(t[1])
    
    for a in ans:
        print(a)

if __name__ == "__main__":
    main()

会员可通过查看《已通过》的提交记录来查看其他语言哦~

题目描述

小美的彩带是由一条长度为 $n$ 的彩带一直无限循环得到的, 彩带的每一个位置都有一个颜色, 用 $a_{i}$ 表示。因此当 $i>n$ 时, $a_{i}=a_{i-n}$ 。

小美每次会从左往后或从右往左剪一段长度为 $x$ 的彩带, 她想知道她每次剪下来的彩带有多少种颜色。

输入描述

第一行输入两个整数 $n, q\left(1 \leq n, q \leq 2 \times 10^{5}\right)$ 代表彩带长度、剪彩带次数。 第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1 \leq a_u \leq 1e9)$ 代表彩带每一个位置的颜色。

此后 $q$ 行, 每行输入一个字符 $c$ 和一个整数 $x$ 代表裁剪方向和裁剪长度, 其中 'L' 说明从左往右剪, 'R' 说明从右往左剪。

输出描述

对于每一次裁剪彩带, 在一行上输出一个整数代表颜色数量。

样例输入输出

6 3
1 1 4 5 1 4
L 2
L 3
R 12

1
3
3

说明

第一次剪彩带, 剪下来的是 $[1,1]$ , 有 $\{1\}$ 这 $1$ 种颜色；

第二次剪彩带, 剪下来的是 $[4,5,1]$, 有 $\{1,4,5\}$ 这 $3$ 种颜色；

第三次剪彩带, 剪下来的是 $[1,1,4,5,1,4,1,1,4,5,1,4]$, 有 {1,4,5} 这 $3$ 颜色。