小美的彩带是由一条长度为
的彩带一直无限循环得到的,彩带的每一个位置都有一个颜色,用
表示。因此当
时,
。
小美每次会从左往右或从右往左剪一段长度为
的彩带,她想知道她每次剪下来的彩带有多少种颜色。
第一行输入两个整数
代表彩带长度、剪彩带次数。
第二行输入
个整数
代表彩带每一个位置的颜色。
此后
行,每行输入一个字符
和一个整数
代表裁剪方向和裁剪长度,其中 '
' 说明从左往右剪, '
' 说明从右往左剪 。
对于每一次裁剪彩带,在一行上输出一个整数代表颜色数量。
6 4 1 1 4 5 1 4 L 2 L 3 R 12 R 1
1 3 3 1
第一次剪彩带,剪下来的是
,有
这
种颜色;
第二次剪彩带,剪下来的是
,有
这
种颜色;
第三次剪彩带,剪下来的是
,有
这
种颜色。
第四次剪彩带,剪下来的是
,有
这一种颜色。
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(); } }
#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; }
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(); } }
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)