C++11(clang++ 3.9) 解法, 执行用时: 206ms, 内存消耗: 86624K, 提交时间: 2018-02-23 21:26:14

#include <bits/stdc++.h>
using namespace std;

typedef long long  LL;
const int N=1000010;
int n,tot,prt,srt,pre[N],suf[N],ch[N][26],L[N],R[N],t1[N],t2[N];
LL ans;
char s[N];
vector <int> tag[N];

void modify(int *t,int x,int k){for (; x<N; t[x]+=k,x+=x&-x);}
int ask(int *t,int x){int s=0;  for (; x; s+=t[x],x-=x&-x);  return s;}

int insert(int x)
{
	for (int i=1; s[i]!='#'; i++)
		{
			if (!ch[x][s[i]-'a'])  ch[x][s[i]-'a']=++tot;
			x=ch[x][s[i]-'a'];
		}
	return x;
}

void dfs1(int x)
{
	L[x]=++tot;
	for (int i=0; i<26; i++)
		if (ch[x][i])  dfs1(ch[x][i]);
	R[x]=tot;
}

void ask(int i)
{
	i=pre[i];
	ans+=ask(t1,L[i])+ask(t2,R[i])-ask(t2,L[i]);
}

void mark(int i,int k)
{
	i=pre[i];
	modify(t1,L[i],k),modify(t1,R[i]+1,-k),modify(t2,L[i],k);
}

void dfs2(int x)
{
	for (int i=0; i<tag[x].size(); i++)  ask(tag[x][i]),mark(tag[x][i],1);
	for (int i=0; i<26; i++)
		if (ch[x][i])  dfs2(ch[x][i]);
	for (int i=0; i<tag[x].size(); i++)  mark(tag[x][i],-1);
}

void work()
{
	scanf("%d",&n),prt=1,srt=2,tot=2;
	for (int i=1; i<=n; i++)
		{
			scanf("%s",s+1),pre[i]=insert(prt);
			reverse(s+1,s+strlen(s+1)+1),suf[i]=insert(srt);
			tag[pre[i]].push_back(i),tag[suf[i]].push_back(i);
		}
	tot=0;
	dfs1(prt);
	dfs2(srt);
	printf("%lld\n",ans);	
}

int main()
{
	work();
	return 0;
}