开O2

不开O2

#include<bits/stdc++.h>

using namespace std;

long long n,m,idx,cnt[500005],a,q[100005],len,ans;

int son[500005][55];
void w(int l,int r){//归并求逆序对
     if(l==r)
     return ;
     int mid=(l+r)>>1;
     w(l,mid),w(mid+1,r);
        int k=l,i=l,j=mid+1;
        while(i<=mid&&j<=r){
            if(q[i]<=q[j])                           cnt[k++]=q[i++];
            else 
            {
                cnt[k++] =q[j++];
                ans+=mid-i+1;
            }
           
        } while(i<=mid) cnt[k++]=q[i++];
            while( j<=r) cnt[k++]=q[j++];
            for(int y=l;y<=r;y++){
                q[y]=cnt[y];
            }
}
void insert(char str[]){//Tire插入
    int p=0;
    for(int i=0;i<strlen(str);i++){
        int u=str[i]-'a';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]=++a;
    return ;
}
void query(char str[]){//Tire查找
    int p=0;
    for(int i=0;i<strlen(str);i++){
        int u=str[i]-'a';
        if(!son[p][u]) {return ;
            }
        p=son[p][u];
    }
    q[len++]=cnt[p];
    return ;
}
int main(){
    scanf("%lld",&n);
    char st[100];
    for(int i=0;i<n;i++){
        scanf("%s",st);
        insert(st);
    }
    for(int i=0;i<n;i++){
        scanf("%s",st);
        query(st);
    }
    for(int i=0;i<100005;i++) cnt[i]=0;
    w(0,n-1);
    printf("%lld",ans);
    return 0;
}

感谢帮助！