Link

ICPC2022Hangzhou F Da Mi Lao Shi Ai Kan De

Question

给出 \(Q\) 个 \(a-z\) 的排序表示比较规则，求 \(n\) 个串在每个比较规则下的逆序对个数

Solution

我们发现，对于两个串的比较来说，决定大小的只是两个字母的比较，比如说

aac
aab

判断这是否是逆序对，起决定性作用的就是比较规则中 \(c\) 在 \(b\) 前面还是 \(b\) 在 \(c\) 前面。然而，前面的 aa 其实对任意的一组比较规则都可以忽略不看，就取决于 \(c\)，\(b\) 的顺序

如果我们可以先不看比较规则，提前构造出起决定性作用的那些字符二元组，定义 \(f(x,y)\) 表示 \(n\) 个串中，起决定性作用的两个字母是 \(x\) 和 \(y\)，\(x\) 的串在 \(y\)的串前面，出现的数量。例如前面的数据中 \(x\) 就是 \(c\)，\(y\) 就是 \(b\)

如果构造出了 \(f(x,y)\) ，如果一组排列中，\(y\) 在 \(x\) 前面，那么 \(f(x,y)\) 就构成了逆序，要加上 \(f(x,y)\)

关键在于如何构造 \(f(x,y)\)

\(x,y\) 只与不同的那个字符有关，所以考虑字典树，刚开始是一颗空的字典树，往字典树里面加字符串，当遍历到的字典树的节点为 \(pos\) 时，需要加入的下一个字符是 \(s_j\) ，那么对于 \(pos\) 的每一个儿子所对应的序列都在 \(s\) 前面，所以 \(f(son_k,s_j)+=num[sum_k]\) ，\(num[x]\) 表示字典树上 \(x\) 点所包含的串数

如图，蓝色部分就是在当前串之前已经处理好的串，我需要加入 \(c\) ，那么就要增加 \(f(a,c)\) 和 \(f(b,c)\) 的值

有一个小细节，就是在处理一个串是另外一个串的前缀的时候，是无法处理的，比如 aaab 和 aa 也是逆序对，这就需要在处理 aa 的最后一个字符的时候，加上这个字符的所有字数的 \(num\)

Code

#include<bits/stdc++.h>
using namespace std;
int N,Q;
typedef long long LL;
const int maxn=5e5+5,maxL=1e6+5;
inline int read(){
	int ret=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}

int t[maxL][26],Len=0;
LL num[maxL],now_ans=0,ans2;
string s[maxn];
LL ans[26][26];


void in(string s){
    int siz=s.length(),pos=0;

    for(int i=0;i<siz;i++){
        int now_x=s[i]-'a';
        for(int j=0;j<26;j++){
            if(now_x==j) continue;
            ans[j][now_x]+=num[t[pos][j]];
        }

        if(t[pos][now_x]==0) {
            ++Len;
            t[pos][now_x]=Len;
            pos=Len;
        }

        else {
            pos=t[pos][now_x];
            if(i==siz-1){
                for(int j=0;j<26;j++)
                    ans2+=num[t[pos][j]];
            }
        }
        num[pos]++;
    }
}

int main(){
    N=read(),Q=read();
    for(int i=1;i<=N;i++){
        cin>>s[i];
        in(s[i]);
    }
    for(int i=1;i<=Q;i++){
        now_ans=0;
        string q;cin>>q;
        int siz=q.length();
        vector<int> id(26);
        for(int j=0;j<siz;j++){
            id[q[j]-'a']=j;
        }
        for(int j1=0;j1<26;j1++)
        for(int j2=0;j2<26;j2++){
            if(id[j1]>id[j2]){
                now_ans+=ans[j1][j2];
            }
        }
        printf("%lld\n",now_ans+ans2);
    }
    return 0;
}

JZTXT

ICPC2022Hangzhou F Da Mi Lao Shi Ai Kan De 题解

Link

Question

Solution

Code