求助哪错了

P8306 【模板】字典树

__hqt__ @ 2024-05-11 17:09:17

思路:放在字典树里的同时放入一个编号,查询个数时用尾编号首编号再加,但不知道哪错了

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>//tree
#include<ext/pb_ds/hash_policy.hpp>//hash
#include<ext/pb_ds/trie_policy.hpp>//trie
#include<ext/pb_ds/priority_queue.hpp>//priority_queue
using namespace std;
using namespace __gnu_pbds;
#define endl '\n'
typedef long long ll;
typedef pair<string,int> psi;
trie<string,int,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update> a;
int k=0;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T,n,q;
    string s;
    cin>>T;
    while(T--)
    {
        a.clear();
        k=0;
        cin>>n>>q;
        for(int i=1;i<=n;i++)
        {
            cin>>s;
            k++;
            psi t=make_pair(s,k);
            a.insert(t);
        }
        for(int i=1;i<=q;i++)
        {
            cin>>s;
            auto t=a.prefix_range(s);
            cout<<((*(t.second)).second-(*(t.first)).second+1)<<endl;
        }
    }
}

by CaoSheng_zzz @ 2024-05-11 17:35:39

数据错了


by _ayaka_ @ 2024-05-11 17:44:04

@CaoSheng 神金


by elpsconr @ 2024-05-14 22:16:28

之前知乎上说pb_ds的字典树好像复杂度是是 O(n)(θ(ans)) 的,所以不能通过本题。


|