长度为L的字符串最多有L个前缀。删除操作不占用时间复杂度。每次插入的复杂度是log 所以总共是LlogL
把活着的所有前缀插入到Y 集合中
学习 set中用lower_bound 查找pair
set.erase()
预估时间复杂度

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 2e5+5;
const ull Base =51971;
set<ull> X;
set<pair<ull,int>> Y;
string v[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q,ans=0;
    int n;
    cin>>n;

    for(int i=0;i<n;i++){
        cin>>q>>v[i];

       if(q==2){ // cout<<v[i]<<endl;
     //      X.insert(v[i]);
    //       ans++;
    //   }else{
           ull h=0;
           bool fl = true;
           for(int j=0;j<v[i].size();j++){
               h = h*Base +(v[i][j]-'a'+1);//当前的哈希值
               if(X.count(h)){
                   fl = false;
                   break;
               }
           }
           if(fl){
               //插入所有前缀
               ans++;
               h=0;//记得重置h
                for(int j=0;j<v[i].size();j++){
               h = h*Base +(v[i][j]-'a'+1);//当前的哈希值
               Y.insert({h,i});
                }
             }

           }else{
               ull H = 0;
               //删除所有id 的前缀??
               for(int j=0;j<v[i].size();j++){
                   H = H*Base +(v[i][j]-'a'+1);

               }
               X.insert(H);//??
               //为啥找最小的 二分
               while(true){
                   //在Y当中二分查找最小的》= （H，0）; 第一个一定是H 第二个一定是真实下标
                   auto it = Y.lower_bound({H,0});
                   if(it!= Y.end() && it->first ==H){
                       int id = it->second;
                    //   cout<<id<<"  ? "<<endl;
                       ans--; //找到一个杀一个？？
                       ull h =0;
                       for(int j=0;j< v[id].size(); j++){
                           h= h *Base + (v[id][j] -'a'+1);
                           Y.erase({h,id});
                       }
                   }else break; //找不到就是杀干净了

               }
           }

           cout<<ans<<endl;
       }


}