Acwing哞叫时间II

6134. 哞叫时间II - AcWing题库

题目大意：统计数组中子序列abb的数量：

做法：从右往左枚举倒数第二个b，查前面出现过多少次a，查的方法(开一个数组left[x]来统计当前及前面出现过多少次x，cnt记录不同x的数量)

const int N = 1e6 + 10,T = 20; int n; LL a[N],L[N],R[N],cnt; //L[i]:下标i及i左（右）边x的数量, void solve() { cin >> n; for (int i = 1;i <= n;i ++) { cin >> a[i]; L[a[i]] ++; if (L[a[i]] == 1) cnt ++;//x第一次出现，cnt++ } LL res = 0; for (int i = n;i >= 1;i --) { LL x = a[i]; R[x] ++,L[x] --;//线往左移动 if (L[x] == 0) cnt --;//线左边没有x了 if (R[x] == 2) //有两个bb { res += cnt;//cnt就是左边不同的数的数量 if (L[x] > 0) res --;//线左边还有x,即bbb,这种不符合要求的减去 } } cout << res << endl; }