fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define CLR(x,y) memset(x,y,sizeof(x))
  6. #define SQ(x) ((x)*(x))
  7. #define ALL(x) (x).begin(),(x).end()
  8. #define LL long long
  9.  
  10. const int Size = 205055;
  11.  
  12. /// typ = 1 = insert
  13. /// typ = 2 = query
  14. /// typ = 3 = delete
  15.  
  16. struct PRR{
  17.     int strIdx;
  18.     int typ;
  19.     int U;
  20.     int V;
  21.     int Tm;
  22.     int idx;
  23.     PRR(){
  24.     }
  25.     PRR(int _strIdx,int _typ,int _U,int _V,int _Tm){
  26.         strIdx = _strIdx;
  27.         typ = _typ;
  28.         U = _U;
  29.         V = _V;
  30.         Tm = _Tm;
  31.     }
  32. };
  33.  
  34. bool cmp(PRR a,PRR b){
  35.     if(a.Tm == b.Tm){
  36.         return (a.typ < b.typ);
  37.     }
  38.     return (a.Tm<b.Tm);
  39. }
  40.  
  41. int N,Q;
  42. vector<PRR> List;
  43. int typ,U,V,Tm;
  44.  
  45. LL DP[55][55];
  46. LL RES[Size];
  47. char SS[100005][55];
  48.  
  49. struct node {
  50.     LL cnt;
  51.     int child[27];
  52.     node(){
  53.     }
  54. };
  55.  
  56. LL NC2(LL N){
  57.     if(N<=1) return 0;
  58.     return N*(N-1)/2LL;
  59. }
  60.  
  61. struct trie {
  62.     void clear_new_node() {
  63.         node newNode;
  64.         tree.pb(newNode);
  65.         tree[node_ID].cnt = 0;
  66.         CLR(tree[node_ID].child, -1);
  67.         node_ID++;
  68.     }
  69.  
  70.     vector<node> tree;
  71.     int node_ID;
  72.     void initialize() {
  73.         node_ID = 0;
  74.         clear_new_node();
  75.     }
  76.  
  77.     void insert_word(int idx, int pos, int Len) {
  78.         int cur = 0;
  79.         for (int i = pos; i < Len; ++i) {
  80.             int id = SS[idx][i] - 'a';
  81.             if (tree[cur].child[id] == -1) {
  82.                 tree[cur].child[id] = node_ID;
  83.                 clear_new_node();
  84.             }
  85.             cur = tree[cur].child[id];
  86.             LL prev = DP[pos][i];
  87.             DP[pos][i] -= NC2(tree[cur].cnt);
  88.             tree[cur].cnt++;
  89.             DP[pos][i] += NC2(tree[cur].cnt);
  90.         }
  91.     }
  92.  
  93.     void delete_word(int idx, int pos, int Len) {
  94.         int cur = 0;
  95.         for (int i = pos; i < Len; ++i) {
  96.             int id = SS[idx][i] - 'a';
  97.             if (tree[cur].child[id] == -1) {
  98.                 return;
  99.             }
  100.             cur = tree[cur].child[id];
  101.             DP[pos][i] -= NC2(tree[cur].cnt);
  102.             tree[cur].cnt--;
  103.             DP[pos][i] += NC2(tree[cur].cnt);
  104.         }
  105.     }
  106. };
  107.  
  108. trie root[55];
  109.  
  110. void solve(){
  111.     for(int i = 0;i<55;i++) root[i].initialize();
  112.     sort(ALL(List),cmp);
  113.     CLR(DP,0);
  114.  
  115.     for(int i = 0;i<List.size();i++){
  116.         PRR cur = List[i];
  117.         if(cur.typ == 2){ /// Query:
  118.             RES[cur.idx] = DP[cur.U][cur.V];
  119.         }else if(cur.typ == 1){ /// Insert:
  120.             int Len = strlen(SS[cur.strIdx]);
  121.             for(int p = 0;p<Len;p++){
  122.                 root[p].insert_word(cur.strIdx,p,Len);
  123.             }
  124.         }else{ /// Delete:
  125.             int Len = strlen(SS[cur.strIdx]);
  126.             for(int p = 0;p<Len;p++){
  127.                 root[p].delete_word(cur.strIdx,p,Len);
  128.             }
  129.         }
  130.     }
  131.  
  132.     for(int i = 0;i<Q;i++){
  133.         printf("%lld\n",RES[i]);
  134.     }
  135. }
  136.  
  137. int main () {
  138.  
  139.     scanf("%d",&N);
  140.     PRR P;
  141.     for(int i = 0;i<N;i++){
  142.         scanf("%s %d %d",SS[i],&U,&V);
  143.         P.strIdx = i; P.typ = 1; P.Tm = U;
  144.         List.pb(P);
  145.         P.strIdx = i; P.typ = 3; P.Tm = V;
  146.         List.pb(P);
  147.     }
  148.  
  149.     scanf("%d",&Q);
  150.     for(int i = 0;i<Q;i++){
  151.         scanf("%d %d %d",&U,&V,&Tm);
  152.         U--;V--;
  153.         P.U = U; P.V = V; P.Tm = Tm ;P.typ = 2; P.idx = i;
  154.         List.pb(P);
  155.     }
  156.     solve();
  157.     return 0;
  158. }
  159.  
Success #stdin #stdout 0s 10472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yJ49A3
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!