首页 > 试题广场 >

小美的彩带

[编程题]小美的彩带
  • 热度指数：2044 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小美的彩带是由一条长度为 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,\dots,a_n\left(1 \leq a_i \leq 10^9\right) 代表彩带每一个位置的颜色。
\,\,\,\,\,\,\,\,\,\,此后 q 行，每行输入一个字符 c 和一个整数 x\left(1 \leq x \leq 10^9;\ c\in {\tt 'L'} , {\tt 'R'}\right) 代表裁剪方向和裁剪长度，其中 '\tt L' 说明从左往右剪， '\tt R' 说明从右往左剪 。


输出描述:
\,\,\,\,\,\,\,\,\,\,对于每一次裁剪彩带，在一行上输出一个整数代表颜色数量。
示例1

输入

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

输出

1
3
3
1

说明

\,\,\,\,\,\,\,\,\,\,第一次剪彩带，剪下来的是 [1,1] ，有 \{1\} 这 1 种颜色；
\,\,\,\,\,\,\,\,\,\,第二次剪彩带，剪下来的是 [4,5,1] ，有 \{1,4,5\} 这 3 种颜色；
\,\,\,\,\,\,\,\,\,\,第三次剪彩带，剪下来的是 [4,1,5,4,1,1,4,1,5,4,1,1] ，有 \{1,4,5\} 这 3 种颜色。
\,\,\,\,\,\,\,\,\,\,第四次剪彩带，剪下来的是 [4] ，有 \{4\} 这一种颜色。
算法知识视频讲解
添加回答
重生之不如不重生头像 重生之不如不重生
本题的两种思路：1.求区间不同数个数，自然想到莫队算法，C++可以过，但pypy超时；2.由于涉及环形循环，先将数组拼接复制一次，再将所有查询按右端点排序，离线处理查询。考虑到当前出现某个颜色时，之间所有该颜色都不会对查询有贡献，因此维护每种颜色的上一个出现位置即可，当又出现该颜色时清除之前出现的位置，这样查询不同颜色数量就转为一个区间求和。而以上清除和求和操作都可由树状数组高效完成，pypy可通过。
发表于 2024-09-18 16:15:30 回复(0)
C/C++
xx001a不了c头像 xx001a不了c
//变种的处理区间不同数的数量的题目
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
const int mo=1e9+7;
int n,m,x,y,z,a[N],k,p[N],b[N];
void add(int x,int y)
{
    for(int i=x;i<=2*n;i+=(i&(-i)))
    {
        b[i]+=y;
    }
}
int get(int x)
{
    int sum=0;
    for(int i=x;i;i-=(i&(-i)))
    {
        sum+=b[i];
    }
    return sum;
}
int fid(int x,int y)
{
    return get(y)-get(x-1);
}
void slove()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i+n]=a[i];
    }
    int l=1,r=2*n;
    vector<pair<pair<int,int>,int> > v;
    for(int i=1;i<=m;i++)
    {
        char o;
        cin>>o>>x;
        if(o=='L')
        {
            if(x>=n)
            {
                v.push_back({{n,1},i});
            }
            else
            {
                v.push_back({{l+x-1,l},i});
            }
            l=(l+x)%n;
            if(l==0)
            {
                l=n;
            }
        }
        else
        {
            if(x>=n)
            {
                v.push_back({{n,1},i});
            }
            else
            {
                v.push_back({{r,r-x+1},i});
            }
            r=((r-x)%n+n)%n+n;
            if(r==n)
            {
                r=2*n;
            }
        }
    }
    map<int,int> mp;
    sort(v.begin(),v.end());
    r=1;
    for(auto[xl,g]:v)
    {
        auto[x,y]=xl;
        while(r<=x)
        {
            if(mp[a[r]])
            {
                add(mp[a[r]],-1);
            }
            add(r,1);
            mp[a[r]]=r;
            r++;
        }
        p[g]=fid(y,x);
    }
    for(int i=1;i<=m;i++)
    {
        cout<<p[i]<<endl;
    }
}
signed main()
{
    int t=1;
//    cin>>t;
    while(t--)
    {
        slove();
    }
}
发表于 2024-09-07 17:08:36 回复(0)
天文地理头像 天文地理 
import java.io.*;
import java.util.*;

public class Main {
    //树状数组
    private static int lowBit(int x) {
        return x & -x;
    }

    private static void addOfTreeArray(int[] tree, int index, int val) {
        while (index <= tree.length) {
            tree[index] += val;
            index += lowBit(index);
        }
    }

    private static int queryOfTreeArray(int[] tree, int index) {
        int res = 0;
        while (index > 0) {
            res += tree[index];
            index -= lowBit(index);
        }
        return res;
    }

    private static int queryOfTreeArray(int[] tree, int sIndexInclusive, int eIndexInclusive) {
        return queryOfTreeArray(tree, eIndexInclusive) - queryOfTreeArray(tree, sIndexInclusive - 1);
    }


    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[] split = br.readLine().split(" ");
        int amtOfColorColumns = Integer.parseInt(split[0]);
        int amtOfCuts = Integer.parseInt(split[1]);

        //读取彩带颜色列表
        int[] colorArray = new int[amtOfColorColumns * 2];
        String[] colorNumStrArray = br.readLine().split(" ");
        Set<Integer> colorSet = new HashSet<>();//用于颜色离散化
        for (int i = 0; i < amtOfColorColumns; i++) {
            colorArray[i + amtOfColorColumns] = colorArray[i] = Integer.parseInt(colorNumStrArray[i]);
            colorSet.add(colorArray[i]);
        }

        //确定每次裁剪对应的区间,二维数组，第一维表示裁剪的次序，第二个维度表示左侧开始位置、右侧结束位置、裁剪的次序(因为后续会针对intervalLocOfCuts进行排序，需要记录本次裁剪对应的次序)
        int[][] intervalLocOfCuts = new int[amtOfCuts][3];
        int L = 1, R = 2 * amtOfColorColumns;
        for (int i = 0; i < amtOfCuts; i++) {
            String[] cutOps = br.readLine().split(" ");
            int lenOfCut = Integer.parseInt(cutOps[1]);
            String dirOfCut = cutOps[0];

            if (lenOfCut >= amtOfColorColumns) {
                intervalLocOfCuts[i][0] = 1;
                intervalLocOfCuts[i][1] = amtOfColorColumns;

                if ("L".equals(dirOfCut)) {
                    L = (L + lenOfCut) % amtOfColorColumns;
                } else {
                    R = (R - lenOfCut%amtOfColorColumns) % amtOfColorColumns + amtOfColorColumns;//num%n的目的避免R-num出现负数的情况
                }
            } else {
                if ("L".equals(dirOfCut)) {
                    intervalLocOfCuts[i][0] = L;
                    intervalLocOfCuts[i][1] = L + lenOfCut - 1;
                    L = (L + lenOfCut) % amtOfColorColumns;
                } else {
                    intervalLocOfCuts[i][0] = R - lenOfCut + 1;
                    intervalLocOfCuts[i][1] = R;
                    R = (R - lenOfCut) % amtOfColorColumns + amtOfColorColumns;
                }
            }
            if(L == 0){
                L = amtOfColorColumns;
            }
            if(R == amtOfColorColumns){
                R = 2*amtOfColorColumns;
            }
            intervalLocOfCuts[i][2] = i;
        }

        Arrays.sort(intervalLocOfCuts, (a, b) -> a[1] - b[1]);


        //离散化，降低颜色数值的范围，避免内存超过限制
        Map<Integer, Integer> mapOfColor = new HashMap<>();
        ArrayList<Integer> list = new ArrayList<>(colorSet);
        int sizeOfDiscrete = colorSet.size();
        for (int i = 0; i < sizeOfDiscrete; i++) {
            mapOfColor.put(list.get(i), i);
        }

        //遍历颜色列表，边遍历边计算所包含的裁剪区间的颜色的数量
        int indexOfCut = 0;
        int[] lastIndexOfColor = new int[sizeOfDiscrete];
        int[] disColorAmtOfCut = new int[amtOfCuts];
        int[] treeArray = new int[amtOfColorColumns * 2 + 1];//需要使用1--2n的范围，非纯粹的前序和树状数组，为遍历位置处的处理过（每次遍历仅保留同一颜色最后的位置）的彩带颜色列表前序和

        for (int i = 0; i < 2 * amtOfColorColumns; i++) {
            int indexOfColor = mapOfColor.get(colorArray[i]);
            if (lastIndexOfColor[indexOfColor] != 0) {
                addOfTreeArray(treeArray, lastIndexOfColor[indexOfColor], -1);
            }
            lastIndexOfColor[indexOfColor] = i + 1;
            addOfTreeArray(treeArray, i + 1, 1);

            //计算所包含的裁剪区间的颜色数量
            while (indexOfCut < amtOfCuts && intervalLocOfCuts[indexOfCut][1] <= i+1) {
                disColorAmtOfCut[intervalLocOfCuts[indexOfCut][2]] = queryOfTreeArray(treeArray, intervalLocOfCuts[indexOfCut][0], intervalLocOfCuts[indexOfCut][1]);
                indexOfCut++;
            }
        }


        for (int i = 0; i < amtOfCuts; i++) {
            bw.write(disColorAmtOfCut[i] + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

}

编辑于 2025-05-11 17:30:40 回复(0)
C/C++
lr580头像 lr580
解法一：离线+莫队。注意离散化不然 cnt 用 unordered_map 很容易 TLE。还不过的话加一下 inline 和关同步流。290ms 过题 C++ 代码： 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+3;
int a[maxn*2], sq, ans[maxn];
map<int, int> b; // 离散化
struct query { // 莫队
    int l, r, i;
    bool operator<(const query &x) const
    {
        if (l / sq != x.l / sq)
            return l < x.l;
        if (l / sq & 1)
            return r < x.r;
        return r > x.r;
    }
} c***xn];
int cnt[maxn];
int sum;
inline void add(int i) {
    sum += cnt[a[i]]++ == 0;
}
inline void del(int i) {
    sum -= --cnt[a[i]] == 0;
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, q;
    cin >> n >> q;
    for(int i=0;i<n; ++i) cin >> a[i];
    for(int i=0;i<n; ++i) {
        if(b.find(a[i])==b.end()) {
            b[a[i]] = b.size();
        }
        a[i] = b[a[i]];
    }
    for(int i=0;i<n; ++i) a[i+n]=a[i];
    int li = 0, ri = n - 1;
    for(int qi=0;qi<q;++qi) {
        char cm;
        int len,l,r;
        cin >> cm >> len;
        if(cm=='L') {
            l=li, r=li+len-1;
            li=(li+len)%n;
        }else{
            r=ri, l=ri-len+1;
            ri=(ri-len%n+n)%n;
        }
        int lb=l/n-(l<0), rb=r/n-(r<0);
        // cout << l << " " << r << " " << lb << " " << rb << " : ";
        l=(l%n+n)%n, r=(r%n+n)%n;
        if(abs(lb-rb)>=2) {
            cmd[qi] = {0, n-1, qi};
        } else if(lb==rb) {
            cmd[qi] = {l, r, qi};
        } else {
            cmd[qi] = {l, n+r, qi};
        }
    }
    sq=sqrt(n*2);
    sort(cmd, cmd+q);
    for(int i=0,l=0,r=-1; i<q; ++i) {
        while(l>cmd[i].l) add(--l);
        while(r<cmd[i].r) add(++r);
        while(l<cmd[i].l) del(l++);
        while(r>cmd[i].r) del(r--);
        ans[cmd[i].i] = sum;
    }
    for(int i=0;i<q;++i) {
        cout<<ans[i]<<'\n';
    }
    return 0;
}
解法二：思路来自于高赞“重生之不如不重生”的回答。根据他的思路，补充解释：按右端点排序询问，用 last[i] 数组记录在固定右端点下，每个位置 i 是否有颜色。叠树状数组维护 last 的前缀和，然后对每个询问求区间和即可。 

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+3;
int a[maxn*2], ans[maxn], n;
struct query {
    int l, r, i;
    bool operator<(const query &x) const {
        return r<x.r;
    }
} c***xn];
map<int, int> b; // 离散化
int t[maxn*2];
map<int, int> last; // 记录每个颜色最后出现的位置

void add(int i, int delta) {
    while (i < maxn*2) {
        t[i] += delta;
        i += i & -i;
    }
}

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

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int q;
    cin >> n >> q;
    for(int i=0; i<n; ++i) cin >> a[i];
    // 离散化颜色
    for(int i=0; i<n; ++i) {
        if(b.find(a[i]) == b.end()) {
            b[a[i]] = 1 + b.size();
        }
        a[i] = b[a[i]];
    }
    for(int i=0; i<n; ++i) a[i+n] = a[i];
    int li = 0, ri = n - 1;
    // 处理每个查询，确定对应的区间
    for(int qi=0; qi<q; ++qi) {
        char cm;
        int len, l, r;
        cin >> cm >> len;
        if(cm == 'L') {
            l = li;
            r = li + len - 1;
            li = (li + len) % n;
        } else {
            r = ri;
            l = ri - len + 1;
            ri = (ri - len % n + n) % n;
        }
        int lb = l / n - (l < 0 ? 1 : 0);
        int rb = r / n - (r < 0 ? 1 : 0);
        l = (l % n + n) % n;
        r = (r % n + n) % n;
        if(abs(lb - rb) >= 2) {
            cmd[qi] = {0, n-1, qi};
        } else if(lb == rb) {
            cmd[qi] = {l, r, qi};
        } else {
            cmd[qi] = {l, n + r, qi};
        }
    }
    sort(cmd, cmd + q);
    n *= 2; // 扩展后的数组长度为原长度的两倍
    // 处理每个位置，维护树状数组和最后出现的位置
    for(int i=0, qi=0; i < n; ++i) {
        int color = a[i];
        if(last.count(color)) {
            add(last[color] + 1, -1);
        }
        add(i + 1, 1);
        last[color] = i;
        // 处理所有右端点等于当前i的查询
        while (qi < q && cmd[qi].r == i) {
            int current_l = cmd[qi].l;
            ans[cmd[qi].i] = query(i + 1) - query(current_l);
            qi++;
        }
    }
    // 输出所有查询结果
    for(int i=0; i<q; ++i) {
        cout << ans[i] << '\n';
    }
    return 0;
}



编辑于 2025-02-19 00:18:11 回复(0)
牛客990676133号头像 牛客990676133号
这题太臭了，114514
发表于 2025-01-18 22:37:13 回复(0)
倾海_头像 倾海_
离线加莫队，把剪下来的值离线再用莫队来暴力算，复杂度应该是O(q√n)
发表于 2025-01-17 00:21:02 回复(0)
写烂代码的烂程序员头像 写烂代码的烂程序员
一眼 HH的项链
发表于 2024-10-30 22:19:03 回复(2)
Java
丗湜头像 丗湜 
package com.e;  import java.util.*;  /**  * 10 10  * 4 5 3 10 4 7 10 5 4 8  * L 8  * R 4  * L 3  * L 4  * L 1  * L 3  * R 4  * R 3  * L 10  * L 10  * 这个案例没通过  *  *  * 1   5  1  5  * 2   4  2  4  * 3   3  3  2  * 4   4  4  4  * 5   1  5  1  * 6   3  6  3  * 7   3  7  4  * 8   3  8  3  * 9   6  9  6  * 10  6  10 6  */ public class 减彩带 { public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);  int n = scanner.nextInt();  int q = scanner.nextInt();  int[] colors = new int[n];  Set<Integer> set=new HashSet<>();  for (int i = 0; i < n; i++) {
            colors[i] = scanner.nextInt();  set.add( colors[i]);  } // 初始化裁剪区间  int start = 0;  int end = -1;   int leftIndex=0;  int beforLeftIndex=0;   int rightIndex=0;  int beforeRightIndex=0;  int ColorCount[]=new int[q-1];  for(int j=0;j<q;j++){
            String derect=scanner.next();  int cutCount=scanner.nextInt();  if(derect.equals("L")){ if(cutCount>=colors.length){
                    ColorCount[j]= set.size();  beforLeftIndex=leftIndex;  leftIndex=(beforLeftIndex+cutCount)%colors.length;  } if(cutCount<colors.length){
                    beforLeftIndex=leftIndex;  leftIndex=(beforLeftIndex+cutCount)%colors.length;  ColorCount[j]=getColorSizeLeft(beforLeftIndex,leftIndex,colors);  }
            } //从右到左的下标取值时，要从颜色数组的反向取  if(derect.equals("R")){ if(cutCount>=colors.length){
                    ColorCount[j]= set.size();  beforeRightIndex=beforeRightIndex;  rightIndex=(rightIndex+cutCount)%colors.length;  } if(cutCount<colors.length){
                    beforLeftIndex=leftIndex;  leftIndex=(leftIndex+cutCount)%colors.length;  ColorCount[j]=getColorSizeRight(beforLeftIndex,leftIndex,colors);  }
            }
        } for (int i = 0; i < ColorCount.length; i++) {
            System.out.print(ColorCount[i]+" ");  }

    } public static int getColorSizeLeft(int startIndex,int endIndex,int[] colors){
        Set<Integer> set=new HashSet<>();  if(endIndex>startIndex){ for(int i=startIndex;i<endIndex;i++){
              set.add(colors[i]);  }
      }else{ for(int i=startIndex;i<colors.length;i++){
              set.add(colors[i]);  } for(int i=0;i<endIndex;i++){
              set.add(colors[i]);  }
      } return set.size();  } public static int getColorSizeRight(int startIndex,int endIndex,int[] colors){
        Set<Integer> set=new HashSet<>();  if(endIndex>startIndex){ for(int i=startIndex;i<endIndex;i++){
                set.add(colors[(colors.length-1)-i]);  }
        }else{ for(int i=startIndex;i<colors.length;i++){
                set.add(colors[colors.length-1-i]);  } for(int i=0;i<endIndex;i++){
                set.add(colors.length-1-i);  }
        } return set.size();  }
}
发表于 2025-02-23 11:13:36 回复(1)
风度翩翩的小哥哥很主动头像 风度翩翩的小哥哥很主动
虽然有5个例子过不去但是思路应该没错的这题我真的服了
import java.util.*;
import java.io.*;
public class Main {
    public static final int MAXN=200001;
    //因为是循环的纸条所以开两倍空间
    public static int[] tree=new int[MAXN<<1];
    public static int[] array=new int[MAXN<<1];
    public static int[] first_comming=new int[MAXN];
    public static HashMap<Integer,Integer> map=new HashMap<>();
    public static HashSet<Integer> set=new HashSet<>();
    public static int[][] question=new int[MAXN][3];
    public static int[] ans=new int[MAXN];
    public static int n;
    public static int q;
    //树状数组
    public static int lowbit(int a){
        return a&-a;
    }
    public static int query(int p){
        int ans=0;
        while(p>0){
            ans+=tree[p];
            p-=lowbit(p);
        }
        return ans;
    }
    public static int query(int l,int r){
        return query(r)-query(l-1);
    }
    public static void add(int p,int v){
        while(p<MAXN*2){
            tree[p]+=v;
            p+=lowbit(p);
        }
    }
    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[] str=br.readLine().split(" ");
        n=Integer.parseInt(str[0]);
        q=Integer.parseInt(str[1]);
        str=br.readLine().split(" ");
        for(int i=0;i<n;i++){
            set.add(Integer.parseInt(str[i]));
            array[i]=Integer.parseInt(str[i]);
            array[n+i]=Integer.parseInt(str[i]);
        }
        //离散化
        ArrayList<Integer> list=new ArrayList<>(set);
        Collections.sort(list);
        for(int i=0;i<list.size();i++){
            map.put(list.get(i),i+1);
        }
        int L=1,R=2*n;
        for(int i=0;i<q;i++){
            str=br.readLine().split(" ");
            int number=Integer.parseInt(str[1]);
            if(number>=n){
                question[i][0]=1;
                question[i][1]=n;
                if(str[0].charAt(0)=='L'){
                   L=(L+number)%(2*n); 
                }else{
                   R=(R-number+2*n)%(2*n); 
                }
            }else{
                if(str[0].charAt(0)=='L'){
                    //如果L为0其代表的是2*n
                    if(L==0) L=2*n;
                    int l=L,r=L+number-1;
                    /*
                        将l和r做映射操作
                        例如现在数组为1，2，3
                        开两倍后变为1，2，3，1，2，3（下标从1开始）
                        但现在l为5，r为7
                        则将了l,r映射为2，4
                    */
                    if(r>2*n|l>n){
                        l-=n;
                        r-=n;
                    }
                    question[i][0]=l;
                    question[i][1]=r;
                    L=(L+number)%(2*n);
                }else{
                    //与L操作类似
                    if(R==0) R=2*n;
                    int r=R,l=R-number+1;
                    if(l<=0){
                        r+=n;
                        l+=n;
                    }
                    if(l>n){
                        r-=n;
                        l-=n;
                    }
                    question[i][0]=l;
                    question[i][1]=r;
                    R=(R-number+2*n)%(2*n);
                }
            }
            question[i][2]=i;
        }
        //树状数组维护种类数不会的可以去看看左程云109第4题洛谷P1972
        Arrays.sort(question,0,q,(a,b)->a[1]-b[1]);
        int right=1,cnt=0;
        while(right<=2*n&&cnt<q){
            //获取离散化后的编号
            int index=map.get(array[right-1]);
            if(first_comming[index]!=0){
                add(first_comming[index],-1);
            }
            first_comming[index]=right;
            add(first_comming[index],1);
            while(cnt<q&&question[cnt][1]<=right){
                ans[question[cnt][2]]=query(question[cnt][0],question[cnt++][1]);
            }
            right++;
        }
        for(int i=0;i<q;i++){        
            bw.write(ans[i]+"\n");
        }
        bw.close();
        br.close();
    }
}
发表于 2025-02-19 00:15:28 回复(0)
Java
云深尽处头像 云深尽处
Java貌似做不了？？？运行超时，C++可以
发表于 2024-12-16 13:50:54 回复(0)
Python
牛客657744323号头像 牛客657744323号
第二组用例超时
每次裁剪都根据颜色循环拼接一个新的color_left或color_right，颜色输出set的长度 
def solve(color_left, color_right, c, x):
    color_set = set(color_left)
    full_color_count = 0
 
    if x >= len(color_left):
        x = x % len(color_left)
        full_color_count = len(color_set)
 
    if c == "L":
        cut_arr = color_left[:x]
        cut_set = set(cut_arr)
        color_count = len(cut_set)
 
        new_left = color_left[x:]
        new_left.extend(cut_arr)
 
        if full_color_count:
            return new_left, color_right, full_color_count
        else:
            return new_left, color_right, color_count
 
    elif c == "R":
        cut_arr = color_right[:x]
        cut_set = set(cut_arr)
        color_count = len(cut_set)
 
        new_right = color_right[x:]
        new_right.extend(cut_arr)
         
        if full_color_count:
            return color_left, new_right, full_color_count
        else:
            return color_left, new_right, color_count
 
if __name__ == "__main__":
    n, q = list(map(int, input().split()))
    color_left = list(map(int, input().split()))
    color_right = color_left.copy()
    color_right.reverse()
     
    for _ in range(q):
        c, x = list(input().split())
        x = int(x)
        color_left, color_right, ans = solve(color_left, color_right, c, x)
        print(ans)


发表于 2024-10-28 00:37:50 回复(0)
Java
法学小鑫头像 法学小鑫
首先，我没有做出来这道题目，但是想要谈一下自己的理解。
1.第一种思路，暴力直接遍历整个数组，那么时间复杂度和空间复杂度 大致是O（n）O（n）。
于是乎给定k组查询，那么时间复杂度应该是O（nk），下意识感觉不太行。
2.假定第一种思路是失败的，那么有没有第二种思路可以优化呢？如果单次查询指定区间的颜色数量如果是O（1） 或者O（log n） 那么k次查询复杂度是O（k） 或者O（k*logn）。似乎这样的答案才是符合要求的。
思路就戛然而止了...
发表于 2024-09-08 15:00:50 回复(0)
提交观点

问题信息

难度：
12条回答 2936浏览

热门推荐

相关试题

小美的彩带

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号