蓝桥杯每日一题：第一周周四哞叫时间

蓝桥杯每日一题：第一周周四哞叫时间

疑惑：如何把复杂度控制在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;
}