记录编号	159196	评测结果	AAAAAAAAAA
题目名称	牛	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	0.041 s
提交时间	2015-04-20 12:05:31	内存使用	2.22 MiB

#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;
}