【Codeforces 817E】Choosing The Commander

相关链接

题目传送门: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;
}

16 thoughts to “【Codeforces 817E】Choosing The Commander”

  1. 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

  2. 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

  3. 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

  4. 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

  5. 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

  6. 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!

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

Leave a Reply

Your email address will not be published. Required fields are marked *