全部RE求调
查看原帖
全部RE求调
632830
Mark_666楼主2024/7/12 18:14
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int c[N],n,a[N];
int trie[N*5][60], cnt[N*5], id;
int pd(char s)
{
	if('a'<=s&&'z'>=s) return s-'a';
	if('A'<=s&&'Z'>=s) return s-'A'+26;
}
void insert(string s,int t){
	int p = 0;
	for(int i = 0; i < s.size(); i++){
		int x = pd(s[i]);
		if(trie[p][x] == 0) trie[p][x] = ++id;
		p = trie[p][x];
	}
	cnt[p]=t;
}
int find(string s){
	int p = 0;
	for(int i = 0; i < s.size(); i++){
		int x = pd(s[i]);
		if(trie[p][x] == 0) return 0;
		p = trie[p][x];
	}
	return cnt[p];
}
int lowbit(int x){return x&-x;}
int update(int x,int v)
{
	for(;x<=n;x+=lowbit(x)) a[x]+=v;
}
int query(int x)
{
	int sum=0;
	for(;x;x-=lowbit(x)) sum+=a[x];
	return sum;
}
int main()
{
	//ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	string str;
	for(int i=1;i<=n;i++)
	{
		cin>>str;
		insert(str,i);
	}	
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		cin>>str;
		int x=find(str);
		update(x,1);
		ans+=i-query(x);
	}
	cout<<ans<<' ';
	return 0;
}
2024/7/12 18:14
加载中...