题目地址：Codeforces：Problem – 714C – Codeforces、vjudge：Sonya and Queries – CodeForces 714C – Virtual Judge

题目描述

Today Sonya learned about long integers and invited all her friends to share the fun. Sonya has an initially empty multiset with integers. Friends give her t queries, each of one of the following type:

1. + ai — add non-negative integer ai to the multiset. Note, that she has a multiset, thus there may be many occurrences of the same integer.
2. - ai — delete a single occurrence of non-negative integer ai from the multiset. It’s guaranteed, that there is at least one ai in the multiset.
3. ? s — count the number of integers in the multiset (with repetitions) that match some pattern s consisting of 0 and 1. In the pattern, 0 stands for the even digits, while 1 stands for the odd. Integer x matches the pattern s, if the parity of the i-th from the right digit in decimal notation matches the i-th from the right digit of the pattern. If the pattern is shorter than this integer, it’s supplemented with 0-s from the left. Similarly, if the integer is shorter than the pattern its decimal notation is supplemented with the 0-s from the left.

For example, if the pattern is s = 010, than integers 92, 2212, 50 and 414 match the pattern, while integers 3, 110, 25 and 1030 do not.
用0代替十进制数中的偶数数码，1代替奇数数码，有三种操作：插入，插入一个十进制数；删除，删除一个已经插入的十进制数；查询，查询符合给定01串的数的个数，符合定义为从右往左与给定串的01数码相同，如果长度不一在左边补0。

输入输出格式

输入格式：
The first line of the input contains an integer t (1 ≤ t ≤ 100 000) — the number of operation Sonya has to perform.
Next t lines provide the descriptions of the queries in order they appear in the input file. The i-th row starts with a character ci — the type of the corresponding operation. If ci is equal to + or - then it’s followed by a space and an integer ai (0 ≤ ai < 10^{18}) given without leading zeroes (unless it’s 0). If ci equals ‘?’ then it’s followed by a space and a sequence of zeroes and onse, giving the pattern of length no more than 18.
It’s guaranteed that there will be at least one query of type ?.
It’s guaranteed that any time some integer is removed from the multiset, there will be at least one occurrence of this integer in it.
输出格式：
For each query of the third type print the number of integers matching the given pattern. Each integer is counted as many times, as it appears in the multiset at this moment of time.

输入输出样例

样例输入1：

12
+ 1
+ 241
? 1
+ 361
- 241
? 0101
+ 101
? 101
- 101
? 101
+ 4000
? 0

样例输出1：

2
1
2
1
1

样例输入2：

4
+ 200
+ 200
- 200
? 0

样例输出2：

1

说明

样例1说明：
Consider the integers matching the patterns from the queries of the third type. Queries are numbered in the order they appear in the input.

1. 1 and 241.
2. 361.
3. 101 and 361.
4. 361.
5. 4000.

题解

这个题乍看一下很有意思。分析一下三种操作，我们发现如果长度不一且长的那个多出来的部分里有1就不能加入答案，于是我们思考能不能把左边的前导0全删去，再反着插入Trie树，这样构建的01Trie直接查询就可以了。对于输入的每个字符串都如此操作，插入删除以及查找都是常规操作。

代码

// Code by KSkun, 2018/2
#include <cstdio>
#include <cstring>

const int tab[10] = {0, 1, 0, 1, 0, 1, 0, 1, 0, 1}; 

int trie[1800005][2], wrd[1800005], siz = 1;

inline bool isop(char c) {
    return c == '+' || c == '-' || c == '?';
}

inline void insert(char* str, int l, int r) {
    int t = 1;
    for(int i = r; i >= l; i--) {
        if(!trie[t][str[i] - '0']) {
            t = trie[t][str[i] - '0'] = ++siz;
        } else {
            t = trie[t][str[i] - '0'];
        }
    }
    wrd[t]++;
}

inline int search(char* str, int l, int r) {
    int t = 1;
    for(int i = r; i >= l; i--) {
        if(!trie[t][str[i] - '0']) {
            return 0;
        } else {
            t = trie[t][str[i] - '0'];
        }
    }
    return wrd[t];
}

inline void delet(char* str, int l, int r) {
    int t = 1;
    for(int i = r; i >= l; i--) {
        if(!trie[t][str[i] - '0']) {
            return;
        } else {
            t = trie[t][str[i] - '0'];
        }
    }
    wrd[t]--;
}

inline int proc(char* str) {
    int len = strlen(str), res = len - 1;
    for(int i = 0; i < len; i++) {
        str[i] = tab[str[i] - '0'] + '0';
        if(str[i] == '1' && res == len - 1) res = i;
    } 
    return res;
}

int t;
char op, str[20];

int main() {
    scanf("%d", &t);
    for(int i = 0; i < t; i++) {
        while(!isop(op = getchar()));
        scanf("%s", str);
        if(op == '+') {
            insert(str, proc(str), strlen(str) - 1);
        } else if(op == '-') {
            delet(str, proc(str), strlen(str) - 1);
        } else {
            printf("%d\n", search(str, proc(str), strlen(str) - 1));
        }
    }
    return 0;
}