相关链接
题目传送门:http://codeforces.com/contest/817/problem/E
解题报告
考虑异或之后小于的话
把士兵插入到Trie树里面,然后走一条链即可
时间复杂度:$O(n \log 10^8)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100009 * 32; inline int read() { char c = getchar(); int ret = 0, f = 1; while (c < '0' || c > '9') { f = c == '-'? -1: 1; c = getchar(); } while ('0' <= c && c <= '9') { ret = ret * 10 + c - '0'; c = getchar(); } return ret * f; } class Trie{ int root, cnt; struct Node{ int sum, ch[2]; }p[N]; public: inline void modify(int v, int d) { modify(root, 30, v, d); } inline int query(int buf, int lim) { return query(root, 30, buf, lim); } private: inline void modify(int &w, int t, int v, int d) { w = w? w: ++cnt; p[w].sum += d; if (t >= 0) { modify(p[w].ch[(v >> t) & 1], t - 1, v, d); } } inline int query(int w, int t, int buf, int lim) { if (!w || t == -1) { return 0; } else { int ret = 0, t2 = (buf >> t) & 1, t1 = (lim >> t) & 1; if (t1) { ret += p[p[w].ch[t2]].sum; ret += query(p[w].ch[t2 ^ 1], t - 1, buf, lim); } else { ret += query(p[w].ch[t2], t - 1, buf, lim); } return ret; } } }trie; int main() { int n = read(); for (int i = 1; i <= n; i++) { int ty = read(); if (ty == 1) { trie.modify(read(), 1); } else if (ty == 2) { trie.modify(read(), -1); } else { int p = read(), l = read(); printf("%d\n", trie.query(p, l)); } } return 0; }
582871 459097View the following tips less than and uncover to know how to observe this situation whilst you project your home business today. Earn funds from home 652343
24673 161675youve gotten an critical weblog correct here! would you wish to make some invite posts on my weblog? 223215
628221 435236If you happen to significant fortunate individuals forms, referring by natural indicates, additionally you catch the attention of some sort of envy in consideration of those types the other campers surrounding you which have tough times about this subject. awnings 445346
215965 933374Youd outstanding guidelines there. I did a search about the field and identified that very likely the majority will agree together with your internet page. 27031
402791 529107Wow i like yur internet site. It genuinely helped me with the data i wus seeking for. Appcriciate it, will bookmark. 177377
202652 512980What cell telephone browser is this internet site page optimized for Internet explorer? 365303
363926 304661After study several of the weblog articles for your internet site now, and i also genuinely such as your strategy for blogging. I bookmarked it to my bookmark internet web site list and are checking back soon. Pls take a appear at my web page in addition and tell me what you believe. 212836
442171 429202I adore foregathering valuable information, this post has got me even more info! . 521937
676894 425091Some genuinely good info , Gladiola I observed this. 464513
285368 351302Interesting point of view. Im curious to think what type of impact this would have globally? Sometimes people get just a little upset with global expansion. Ill be around soon to check out your response. 330546
302499 929108wonderful post. Neer knew this, thanks for letting me know. 319495
157270 529523Empathetic for your monstrous inspect, in addition Im just seriously excellent as an alternative to Zune, and consequently optimism them, together with the very good critical reviews some other players have documented, will let you determine whether it does not take right choice for you. 243913
471299 464938Just wanna comment that you have a extremely nice internet site , I love the style it actually stands out. 806164
598406 910353I like this internet site because so much useful stuff on here : D. 997943
Those are yours alright! . We at least need to get these people stealing images to start blogging! They probably just did a image search and grabbed them. They look good though!
Unquestionably believe that which you said. Your favorite justification seemed to be on the net the easiest thing to be aware of. I say to you, I definitely get annoyed while people consider worries that they just do not know about. You managed to hit the nail upon the top and defined out the whole thing without having side effect , people can take a signal. Will probably be back to get more. Thanks