题解：P11412 [EPXLQ2024 fall round] 风吹起了从前

SunsetVoice · 2024-12-18 18:32:22 · 题解

背景故事

提供一个能将此题降上位橙的解法。

先按 d 从小到大排序对每一个可能的前缀建桶，记录所有能对这个字符串产生贡献的 d,v 数值，最后对 v 做前缀和。

由于我们已经按 d 排好了序，所以 d 在数组中一定是从小到大排序的，查询时二分即可。

复杂度（使用 map 情况下） O(n\log n+nS_i\log nS_i+m\log nS_i)。

考虑在常数上优化，首先尽量少开 long long，后对每个桶记录是否已计算好前缀和以保证计算时只计算一次，再优化输入输出即可。

#include<bits/stdc++.h>
using namespace std;
struct memory{
    bool isvb;
    vector<long long>d,v,vb;
    void cl(){
        long long sum = 0;
        for(long long hjx:v){
            sum+=hjx;
            vb.push_back(sum);
        }
        isvb = 1;
    }
};
map<string,memory>mp;
long long n,m;
struct node{
    int d,v;
    string str;
}a[200001];
bool cmp(node x,node y){
    return x.d<y.d;
}
inline string read()
{
    string str="";
    char ch=getchar();
    while(ch==' ' || ch=='\n' || ch=='\r')
    {
        ch=getchar(); 
    }
    while(ch!=' ' && ch!='\n' && ch!='\r')
    {
        str+=ch;
        ch=getchar();
    } 
    return str;
}
signed main(){
    scanf("%lld %lld",&n,&m);
    for(register int i = 1;i<=n;i++){
        scanf("%d %d",&a[i].d,&a[i].v);
        a[i].str = read();
    }
    sort(a+1,a+1+n,cmp);
    for(register int i = 1;i<=n;i++){
        string nstr = "";
        int gl = a[i].str.length();
        for(register int j = 0;j<gl;j++){
            nstr+=a[i].str[j];
            mp[nstr].d.push_back(a[i].d);
            mp[nstr].v.push_back(a[i].v);
            mp[nstr].isvb = 0;
        }
    }
    for(int i = 1;i<=n;i++){
        string nstr = "";
        int gl = a[i].str.length();
        for(int j = 0;j<gl;j++){
            nstr+=a[i].str[j];
            if(mp[nstr].isvb==0){
                mp[nstr].cl();
            }
        }
    }
    while(m--){
        int fd;
        string fq;
        scanf("%d",&fd);
        cin>>fq;
        if(!mp.count(fq)){
            printf("0\n");
            continue;
        }
        int pos = upper_bound(mp[fq].d.begin(),mp[fq].d.end(),fd)-mp[fq].d.begin()-1;
        if(pos<0){
            printf("0\n");
            continue;
        }
        printf("%lld\n",mp[fq].vb[pos]);
    }
    return 0;
}