蓝桥杯每日一题：第一周周四哞叫时间
蓝桥杯每日一题：第一周周四哞叫时间
疑惑：如何把复杂度控制在Q（n），怎么枚举a和b，longlong的形式又该怎么输入（考虑用string）
思路：枚举倒数第二个b前面有多少个a
这是一种经典的实现方法，需要掌握,用数的值做数的下标，其实就和用字母序号做下标一样，left[x]表示当前数左边值等于x的数的个数，right[x]则相反
注意特别的含义，left[x]=0,当前就是从右往左遍历到的最后一个x了，
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e6 + 5;
typedef long long int LL;
LL res;//因为res最大为N的平方，超int了
int l[N],r[N],w[N],cnt;//cnt表示一共有多少个不同的数
int main(){
int n;
cin>>n;
for(int i=1;i<=n;++i){
cin>>w[i];
if(++l[w[i]]==1) cnt++;
}
for(int i=n;i>=1;--i){
int x=w[i];
r[x]++;l[x]--;
if(l[x]==0) cnt--;//即不一样的数就减少了一个
if(r[x]==2) {
res+=cnt;
if(l[x]>0) res-=1;}//剪掉的1就是左边剩下的一个b，因为只有不一样的数字才会被记到cnt里，左边无论有几个b，在cnt里左边不同的数都只有1
}
cout<<res<<endl;
}