记录编号	487105	评测结果	AAAAAAAAAA
题目名称	叉叉	最终得分	100
用户昵称	HtBest	是否通过	通过
代码语言	C++	运行时间	0.031 s
提交时间	2018-02-09 09:54:42	内存使用	0.47 MiB

#define _CRT_SECURE_NO_DEPRECATE
#define lowbit(_NUM_) _NUM_&(-_NUM_)
/************************
*创建时间：2018 02 09
*文件类型：源代码文件
*题目来源：2018寒假・NOI导刊
*采用算法：树状数组
*作者：HtBest
 ************************/
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int a[100001],counts,n,book[200]={0};
char s[100001];
/* Variable explain:
a:树状数组 
counts:统计答案 
n:字串长度 
book:保存首次出现位置 
s:保存字符串 
*/
void read()
{
	freopen("xxxx.in","r",stdin);
	freopen("xxxx.out","w",stdout);
	scanf("%s",s+1);
	n=strlen(s+1);
	memset(book,-1,sizeof(book));
}
void add(int x,int N)
{
	for(int i=x;i<=n;i+=lowbit(i))
		a[i]+=N;
	return;
}
int sum(int x)
{
	int w=0;
	for(int i=x;i>0;i-=lowbit(i))
		w+=a[i];
	return w;
}
void bit()
{
	for(int i=1;i<=n;++i)
	{
		if(book[s[i]]==-1)
		{
			add(i,1);
			book[s[i]]=i;
		}
		else
		{
			add(book[s[i]],-1);
			counts=counts+sum(i)-sum(book[s[i]]);
			book[s[i]]=-1;
		}
	}
}
int main()
{
	read();
	bit();
	printf("%d",counts);
	return 0;
}