__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)) 的,所以不能通过本题。