建立一颗trie树，记录下来每个点以它为结尾的字符串的个数cnt，和它的子树内有多少字符串size

于是查询的时候就只需要把沿途的cnt加起来，再加上最后的size就好了

 

1 /************************************************************** 2     Problem: 1590 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:320 ms 7     Memory:3892 kb 8 ****************************************************************/ 9  10 #include 
      
       11  12 using namespace std;13  14 inline int read();15  16 struct trie {17     trie *son[2];18     int sz, tail;19      20     #define Len (1 << 16)21     void* operator new(size_t) {22         static trie *mempool, *c;23         if (c == mempool)24             mempool = (c = new trie[Len]) + Len;25         c -> son[0] = c -> son[1] = NULL;26         c -> sz = 0, c -> tail = 0;27         return c++;28     }29     #undef Len30      31     void insert(int x) {32         ++this -> sz;33         if (x == 0) {34             ++this -> tail;35             return;36         }37         int t = read();38         if (!this -> son[t]) this -> son[t] = new()trie;39         this -> son[t] -> insert(x - 1);40     }41      42     int query(int x) {43         if (x == 0) return this -> sz;44         int t = read();45         if (!this -> son[t]) {46             while (--x) read();47             return this -> tail;48         }49         return this -> son[t] -> query(x - 1) + this -> tail;50     }51 } *t;52  53 int n, m;54  55 int main() {56     int i;57     n = read(), m = read();58     t = new()trie;59     for (i = 1; i <= n; ++i) t -> insert(read());60     for (i = 1; i <= m; ++i) printf("%d\n", t -> query(read()));61     return 0;62 }63  64 inline int read() {65     static int x;66     static char ch;67     x = 0, ch = getchar();68     while (ch < '0' || '9' < ch)69         ch = getchar();70     while ('0' <= ch && ch <= '9') {71         x = x * 10 + ch - '0';72         ch = getchar();73     }74     return x;75 }