K. Master of Both

我们通过一些性质可以知道排序
可以只比较每个串的第一个不同的地方即可
这样我们就能比较轻易的得出n2的做法
我们把它搞到一个trie树上面
要求逆序对数目
就相当于先插入的与后面插入的不同的地方 后面的比前面的字典序更小 这样贡献+1
这样我们就可以直接记一个dp[26][26]为i字母在前j字母在后的贡献
我们在插入的时候边维护这个dp边插入
最后每个q的s 就直接26*26的求出来
最后要注意的是：
比如这两个串
abc
ab
这种肯定会形成一个逆序对 注意写的时候特别加上即可

int son[N][26], idx ,cnt[N][26];
int n,q,dp[27][27],res;
void init(){
    son[0][0] = son[0][1] = 0;
    idx = 1;
}
void add(string s){
    int p = 0;
    for (int i = 0; i < s.size() ; i++){
        int u=s[i]-'a';
        if (!son[p][u])
            son[p][u] = idx++;
        for(int v=0;v<26;v++){
            if(v==u)continue;
            if(son[p][v])dp[u][v]+=cnt[p][v];
        }
        cnt[p][u]++;
        p = son[p][u];
    }
    for(int v=0;v<26;v++)
        if(son[p][v])res+=cnt[p][v];
}
void solve(){
    init();
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        string s;cin>>s;
        add(s);
    }
    while(q--){
        string s;cin>>s;
        int ans=res;
        for(int i=0;i<26;i++)
            for(int j=i+1;j<26;j++)
                ans+=dp[s[i]-'a'][s[j]-'a'];
        cout<<ans<<endl;
    }
}