此文章可以使用目录功能哟↑(点击上方[+])

比赛链接→Codeforces Round #371 (Div. 2)

Codeforces Problem 713A Sonya and Queries

Accept: 0 Submit: 0
Time Limit: 1 second Memory Limit : 256 megabytes

Problem Description

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:

+?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.
-? 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.
? 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.

Input

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?<?1018) 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.

Output

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.

Sample Input

Sample Output

1

Hint

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.

Problem Idea

解题思路:

【题意】

t次操作,每次操作有下述三种类型:

1. + a 往multiset中增加一个非负整数a,允许相同的数出现

2. - a 从multiset中减去一个非负整数a,执行此操作时保证multiset存在该非负整数a

3. ? s 询问multiset中有多少个数与模式串s匹配(匹配的定义:模式串中,'0'表示该位为偶数,'1'表示该位为奇数)

即一个数从右往左,每位数的奇偶性与模式串一致时(长度不一致时,在前面补0),称为二者匹配

输出与模式串s匹配的数的个数

【类型】
字典树

【分析】

三种操作中,显然入手点在第三种操作

如何与模式串s匹配是此题关键

因为模式串s只有'0'和'1'两种情况,可以想到用二叉树

而这种匹配又可以采用字典树来解决

对于每个插入的数,因为只有每位数的奇偶性是我们要用的

因此,我们可以在字典树中只保存其奇偶性

例如样例1

大致过程就是这样子,希望能有助于大家理解

【时间复杂度&&优化】
O(18t)

题目链接→Codeforces Problem 713A Sonya and Queries

Source Code

/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 2;
const int M = 2;
const int inf = 1000000007;
const int mod = 1000000007;
struct tree
{int a[M],t;
}s[1000005];
char ch[N];
int p;
void init(int x)
{s[x].t=0;memset(s[x].a,-1,sizeof(s[x].a));
}
void buildtree(__int64 x)
{int i,k=0;for(i=0;i<18;i++){if(s[k].a[x%2]==-1){s[k].a[x%2]=p;init(p++);}k=s[k].a[x%2];s[k].t++;x/=10;}
}
void deletetree(__int64 x)
{int i,k=0;for(i=0;i<18;i++){k=s[k].a[x%2];s[k].t--;x/=10;}
}
void query(__int64 x)
{int i,k=0;for(i=0;i<18;i++){if(s[k].a[x%2]==-1){puts("0");return ;}k=s[k].a[x%2];x/=10;}printf("%d\n",s[k].t);
}
int main()
{int t;__int64 x;p=0;init(p++);scanf("%d",&t);while(t--){scanf("%s%I64d",ch,&x);if(ch[0]=='+')buildtree(x);else if(ch[0]=='-')deletetree(x);elsequery(x);}return 0;
}

菜鸟成长记

Codeforces Problem 713A Sonya and Queries(字典树)