Sonya and Queries [Codeforces 371 : Div1 A, Div2 C]

問題

http://codeforces.com/contest/713/problem/A

t個のクエリを処理する。

1. + a : 自然数aをmultisetに入れる
2. - a : 自然数aをmultisetから1つ消す
3. ? s : 文字列sのパターンに当てはまる自然数aがmultisetに何個あるか出力する

文字列sのパターンとは、
010であれば、偶数・奇数・偶数と各桁なっている数を指す（414など）
もし、文字列の方が数より長さが小さいなら、文字列の先頭に0を追加して判断する
もし、数の方が文字列より長さが小さいなら、数の先頭は0であるものとして考える

1 <= t <= 10^5
0 <= a <= 10^18
1 <= |s| <= 18

考察

1. まず、3番目のクエリが独特なので、ここから考えてみる
2. 3番目のクエリで与えられる文字列の組合せは最大2^18(=262144)個で、これならメモリ上に乗る
3. 3番目のクエリは答えるだけで、+とか-とかで計算する方針が良いのでは？

4. +a[i]について考えてみると、各a[i]においてヒットするsがある

例
92 -> 10, 010, 0010, ...
2212 -> 10, 010, 0010, ...

5. この個数は18個を越えることは無いから、O(18)の定数倍で余裕かな？

実装

http://codeforces.com/contest/714/submission/20584481

int n;
map<string, int> ans;
//-----------------------------------------------------------------
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;

	rep(_n, 0, n) {
		char c; cin >> c;
		string s; cin >> s;

		if (c == '?') {
			printf("%d\n", ans[s]);
			continue;
		}

		int line = 0;
		rep(i, 0, s.length()) {
			int a = s[s.length() - 1 - i] - '0';
			if (a % 2 == 1) line = i;
		}

		string ss = "";
		rep(i, 0, 18) {
			int a;
			if (i < s.length())
				a = s[s.length() - 1 - i] - '0';
			else
				a = 0;

			if (a % 2 == 0)
				ss = "0" + ss;
			else
				ss = "1" + ss;

			if (line <= i) {
				if(c == '+')
					ans[ss]++;
				else
					ans[ss]--;
			}
		}
	}
}