比赛 20150420 评测结果 AAAAAAAAAA
题目名称 最终得分 100
用户昵称 Satoshi 运行时间 0.044 s
代码语言 C++ 内存使用 2.22 MiB
提交时间 2015-04-20 08:30:03
显示代码纯文本
#include <fstream>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
ifstream in("cowa.in");
ofstream out("cowa.out");
int n;
map<int,int> f;
long long ans=0;
set<int> G;
int c[100001]={0},cnt=1;
int l[100001]={0},r[100001]={0};
int d[100001]={0},a[100001]={0};
int lowbit(int x)
{
	return x&-x;
}
void add(int x)
{
	while(x<=100001)
	{
		d[x]++;
		x+=lowbit(x);
	}
}
int sum(int x)
{
	int cnt=0;
	while(x>0)
	{
		cnt+=d[x];
		x-=lowbit(x);
	}
	return cnt;
}
int main()
{
	int i;char duang;
	in>>n;
	for(i=1;i<=n;i++)
	{
		in>>duang;
		if(duang=='C')a[i]=1;
		if(duang=='O')a[i]=2;
		if(duang=='W')a[i]=3;
	}
	for(i=1;i<=100001;i++)d[i]=0;
	for(i=1;i<=n;i++)
	{
		l[i]=sum(a[i]-1);
		add(a[i]);
	}
	for(i=1;i<=100001;i++)d[i]=0;
	for(i=n;i>=1;i--)
	{
		r[i]=(n-i)-sum(a[i]);
		add(a[i]);
	}
	//for(i=1;i<=n;i++)out<<l[i]<<' '<<r[i]<<endl;
	for(i=1;i<=n;i++)ans+=l[i]*r[i];
	out<<ans<<endl;
	return 0;
}