【Codeforces 706D】Vasiliy’s Multiset

Qizy 可持久化数据结构, 数据结构, 解题报告

题目传送门：http://codeforces.com/contest/706/problem/D

可持久化字典树，解决xor

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
using namespace std;

const int MAXN = 7000000;
const int SGZ = 40;

int n;

map<int,int> M;

inline int read(){
	char c=getchar(); int ret = 0;
	while (c<'0'||c>'9'){c=getchar();}
	while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
	return ret;
}

inline int Get(){
	char c=getchar(); 
	while (c != '+' && c != '-' && c != '?') c=getchar();
	if (c == '+') return 1;
	else if (c == '-') return -1;
	else return 0;
}

namespace Chair_Tree{
	#define CT Chair_Tree
	int ans_tmp,cnt,ch[MAXN][2],buf[SGZ],root,sum[MAXN];
	
	void modify(int pre, int &w, int step, int delta){
		w = ++cnt; sum[w] = sum[pre] + delta; ch[w][0] = ch[pre][0]; ch[w][1] = ch[pre][1];
		if (step <= 31) modify(ch[pre][buf[step]],ch[w][buf[step]],step+1,delta);
	}
	
	inline void modify(int val, int delta){
		for (int i=1;i<=31;i++) buf[31-i+1] = val & 1, val >>= 1;
		modify(root, root, 1, delta); 	
	}
	
	void query(int w, int step){
		if (step <= 31) {
			if (sum[ch[w][buf[step]]]) ans_tmp += 1<<(31-step), query(ch[w][buf[step]],step+1);
			else query(ch[w][buf[step]^1],step+1);
		}
	}
	
	inline int query(int val){
		ans_tmp = 0;
		for (int i=1;i<=31;i++) buf[31-i+1] = (val & 1) ^ 1, val >>= 1;
		query(root, 1); 
		return ans_tmp;
	}
};

int main(){
	n = read(); CT::modify(0,1);
	for (int i=1,tp,val;i<=n;i++) {
		tp = Get(); val = read();
		if (tp == 1) {
			M[val] = M[val] + 1;
			if (M[val] == 1) CT::modify(val,1);
		} else if (tp == -1) {
			M[val] = M[val] - 1;
			if (M[val] == 0) CT::modify(val,-1);
		} else printf("%d\n",CT::query(val));
	}
	return 0;
}

229 thoughts to “【Codeforces 706D】Vasiliy’s Multiset”

  1. I am really impressed with your writing skills
    as well as with the layout on your blog.
    Is this a paid theme or did you modify it yourself? Anyway keep up the excellent quality writing, it’s rare to see a nice blog like this
    one nowadays.

    Reply

  4. Good post. I learn something totally new and challenging
    on blogs I stumbleupon every day. It’s always helpful to read articles from other writers and practice something
    from other web sites.

    Reply

  5. Have you ever considered creating an e-book or guest authoring on other sites?
    I have a blog centered on the same ideas you discuss and would love to have you share some stories/information. I know my visitors would value your work.

    If you are even remotely interested, feel free to shoot me an e mail.

    Reply

  6. You’re so awesome! I don’t think I’ve truly read through something like that
    before. So great to find somebody with original thoughts on this
    subject. Seriously.. thanks for starting this up. This web site is one
    thing that is required on the internet, someone with a little
    originality!

    Reply

  10. Nice post. I learn something new and challenging on websites I stumbleupon on a daily basis.
    It will always be helpful to read through articles from other writers
    and practice something from other sites.

    Reply

  11. Remarkable issues here. I’m very satisfied to peer your post.
    Thank you a lot and I’m having a look forward to contact you.
    Will you please drop me a e-mail?

    Reply

  12. Undeniably consider that which you stated. Your favourite reason appeared to be at the web the simplest thing to be mindful of.
    I say to you, I definitely get irked while other folks think about
    issues that they just don’t recognize about. You managed to hit the nail upon the highest and defined out
    the entire thing without having side-effects , other people could take a signal.
    Will likely be again to get more. Thank you

    Reply

  15. Howdy! This post couldn’t be written any better!
    Reading through this post reminds me of my good old
    room mate! He always kept talking about this. I will forward this page to him.
    Fairly certain he will have a good read. Thank you for sharing!

    Reply

  18. Hello, i feel that i saw you visited my site so i got here to go back the favor?.I am attempting to find things to improve my
    website!I assume its ok to use a few of your concepts!! pof natalielise

    Reply

  20. I used to be suggested this blog by means of my cousin. I’m no longer sure
    whether this post is written by him as nobody else recognise such special about my difficulty.

    You’re wonderful! Thank you! natalielise pof

    Reply

  22. excellent publish, very informative. I wonder why the opposite experts
    of this sector do not understand this. You should continue your writing.

    I am confident, you’ve a great readers’ base already!

    Reply

  23. Hey there would you mind letting me know which hosting company you’re working
    with? I’ve loaded your blog in 3 completely different internet
    browsers and I must say this blog loads a lot faster then most.
    Can you suggest a good web hosting provider at a fair price?
    Thanks, I appreciate it!

    Reply

  28. I am not sure where you’re getting your info,
    but good topic. I needs to spend some time learning more or
    understanding more. Thanks for magnificent information I
    was looking for this info for my mission.

    Reply

  32. My programmer is trying to persuade me to move to .net from PHP.

    I have always disliked the idea because of
    the costs. But he’s tryiong none the less. I’ve been using WordPress
    on numerous websites for about a year and am concerned about switching to another platform.
    I have heard fantastic things about blogengine.net.
    Is there a way I can import all my wordpress posts into it?
    Any kind of help would be really appreciated!

    Reply

  33. I am not certain the place you are getting your info, however good topic.
    I must spend some time learning much more or figuring out more.
    Thanks for fantastic info I was on the lookout for this information for my mission.

    Reply

  35. I’ll right away take hold of your rss feed as I can’t to find your email subscription hyperlink or e-newsletter service.
    Do you have any? Kindly permit me realize
    so that I may subscribe. Thanks.

    Reply

  36. Whats up are using WordPress for your site platform?
    I’m new to the blog world but I’m trying to get started and
    set up my own. Do you need any html coding expertise to make your own blog?
    Any help would be greatly appreciated!

    Reply

  37. I know this if off topic but I’m looking into starting my
    own weblog and was wondering what all is needed to get setup?
    I’m assuming having a blog like yours would cost a pretty penny?
    I’m not very web savvy so I’m not 100% positive.
    Any recommendations or advice would be greatly appreciated.
    Many thanks

    Reply

  38. Hi there, just became aware of your blog through Google,
    and found that it is truly informative. I am gonna watch out for brussels.
    I will be grateful if you continue this in future.
    A lot of people will be benefited from your writing.

    Cheers!

    Reply

  39. I was suggested this blog by my cousin. I’m not sure whether this post is written by him as
    no one else know such detailed about my difficulty.
    You’re wonderful! Thanks!

    Reply

  40. Hello! I could have sworn I’ve been to your blog before but after going
    through some of the articles I realized it’s new to me.
    Anyways, I’m definitely happy I stumbled upon it and I’ll be book-marking
    it and checking back frequently!

    Reply

  42. Right here is the right webpage for anybody who really wants to understand this topic.
    You realize so much its almost hard to argue with you (not
    that I personally will need to…HaHa). You certainly put a new spin on a subject which has been written about for a long time.
    Excellent stuff, just wonderful!

    Reply

  43. Hello are using WordPress for your blog platform?
    I’m new to the blog world but I’m trying to get started and set up my own. Do
    you require any coding knowledge to make your own blog?
    Any help would be greatly appreciated!

    Reply

  45. Hmm is anyone else experiencing problems with
    the pictures on this blog loading? I’m trying to determine if its a problem on my end or if it’s the blog.

    Any responses would be greatly appreciated.

    Reply

  59. Hi! I could have sworn I’ve been to this site before
    but after reading through some of the post I realized it’s new to me.
    Nonetheless, I’m definitely glad I found it and I’ll be bookmarking
    and checking back frequently!

    Reply

  77. Wonderful blog! I found it while surfing around on Yahoo News.
    Do you have any tips on how to get listed in Yahoo News? I’ve been trying for a while but I never seem to get there!
    Thanks

    Reply

  84. Hello! I’m at work browsing your blog from my new iphone 4!
    Just wanted to say I love reading your blog and look forward to all
    your posts! Keep up the fantastic work!

    Reply

  101. It is perfect time to make some plans for the future and it is time to be happy.
    I’ve read this post and if I could I desire to suggest you few interesting things or
    suggestions. Perhaps you can write next articles referring to this article.
    I wish to read even more things about it!

    Reply

  113. I believe that is among the most significant information for me.
    And i am glad reading your article. However wanna statement on few
    basic issues, The website taste is great, the articles is really nice
    : D. Good job, cheers

    Reply

  116. My partner and I stumbled over here coming from a different pageand thought I may as well check things out. I like what I see so now i’m following you.Look forward to going over your web page repeatedly.

    Reply

  119. When I originally commented I clicked the “Notify me when new comments are added” checkbox
    and now each time a comment is added I get several emails with the
    same comment. Is there any way you can remove me from that service?

    Many thanks!

    Reply

  120. Hiya, I am really glad I have found this info. Today bloggers publish only about gossip and internet stuff and this is really irritating. A good site with interesting content, that is what I need. Thank you for making this site, and I’ll be visiting again. Do you do newsletters by email?

    Reply

  121. [url=http://viagraly6.com]gay porn viagra for sale [/url][url=http://lasix0i0.com]similar over the counter drugs to lasix [/url][url=http://viagrao0o.com]where is best place to buy viagra online [/url][url=http://tetracyclineby6.com]tetracycline poder [/url][url=http://lexaprod7k.com]lexapro and pain in arms [/url]

    Reply

  124. I’ve been surfing online more than 3 hours today, yet I never found any interesting article like yours. It is pretty worth enough for me. In my view, if all website owners and bloggers made good content as you did, the net will be much more useful than ever before.

    Reply

  137. Palletized UK Goods Storage for International Shoppers, International shipping, Shipping items, Shipping items on a pallet, too heavy, too large, normal parcel, shipping palletized goods, international destination, packing a pallet, Palletized UK goods, Storage for international shoppers, Shipping service from the UK, Shipping service

    Reply

  138. What?s Taking place i am new to this, I stumbled upon this I have discovered It absolutely useful and it has aided me out loads. I’m hoping to contribute & help other customers like its aided me. Good job.

    Reply

  140. I used to be recommended this website through my
    cousin. I am now not certain whether this submit is written via
    him as no one else understand such targeted approximately my difficulty.
    You are incredible! Thank you!

    Reply

  147. Hi! I’ve been following your blog for a while now and finally got
    the courage to go ahead and give you a shout out from Kingwood Tx!
    Just wanted to mention keep up the excellent work!

    Reply

  148. Hiya, I’m really glad I have found this information. Today bloggers publish just about gossip and net stuff and this is actually irritating. A good blog with exciting content, this is what I need. Thanks for making this web-site, and I will be visiting again. Do you do newsletters by email?

    Reply

  150. Somebody essentially lend a hand to make seriously articles I might state.
    This is the very first time I frequented your web page
    and up to now? I amazed with the analysis you made to make this particular put up extraordinary.

    Wonderful process!

    Reply

  153. You actually make it seem so easy with your presentation but I find this topic to be actually something which I think I would never understand.
    It seems too complex and very broad for me. I am looking forward for your next post, I’ll try to get the hang of it!

    Reply

  154. Hi there just wanted to give you a quick heads up and let you know a few of the images aren’t loading correctly.
    I’m not sure why but I think its a linking issue.
    I’ve tried it in two different browsers and both
    show the same results.

    Reply

  156. Hello There. I found your blog using msn. This is an extremely well written article.
    I will be sure to bookmark it and return to read more of your useful information. Thanks for
    the post. I’ll certainly return.

    Reply

  159. What i don’t understood is in truth how you are now not actually a lot more well-favored than you might be right now.
    You’re very intelligent. You realize therefore significantly
    in relation to this matter, produced me for my part
    believe it from so many varied angles. Its like women and men are not involved
    until it is something to accomplish with Girl gaga!
    Your personal stuffs outstanding. At all times maintain it up!

    Reply

  160. Hiya, I am really glad I’ve found this info. Nowadays bloggers publish only about gossip and internet stuff and this is actually irritating. A good website with exciting content, that’s what I need. Thanks for making this web site, and I’ll be visiting again. Do you do newsletters by email?

    Reply

  163. Does your blog have a contact page? I’m having a tough time locating it but, I’d like
    to shoot you an email. I’ve got some ideas for your blog you might be
    interested in hearing. Either way, great blog and I look forward to seeing it develop over time.

    Reply

  164. Today, I went to the beach front with my kids. I found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She placed the shell to her ear
    and screamed. There was a hermit crab inside and it pinched her ear.
    She never wants to go back! LoL I know this is completely off topic but I
    had to tell someone!

    Reply

  165. I’m extremely impressed together with your writing abilities and
    also with the format in your weblog. Is that this a paid subject matter
    or did you customize it yourself? Either way stay up the nice
    quality writing, it is rare to peer a nice blog like this one these days..

    Reply

  167. Hi! This is my first comment here so I just wanted to
    give a quick shout out and tell you I genuinely enjoy reading your blog
    posts. Can you suggest any other blogs/websites/forums that go over the same subjects?
    Thanks a ton!

    Reply

  168. Excellent blog here! Also your site loads up fast!
    What web host are you using? Can I get your affiliate link to your host?
    I wish my website loaded up as fast as yours lol

    Reply

  170. I think this is one of the most vital info for
    me. And i’m glad reading your article. But wanna remark on few general
    things, The web site style is perfect, the articles is
    really great : D. Good job, cheers

    Reply

  174. [url=http://viagraly6.com]gay porn viagra for sale [/url][url=http://lasix0i0.com]similar over the counter drugs to lasix [/url][url=http://viagrao0o.com]where is best place to buy viagra online [/url][url=http://tetracyclineby6.com]tetracycline poder [/url][url=http://lexaprod7k.com]lexapro and pain in arms [/url]

    Reply

  180. I do enjoy the manner in which you have presented this challenge and it really does provide me personally some fodder for consideration. On the other hand, through just what I have witnessed, I simply just trust as the actual comments stack on that individuals stay on point and don’t get started upon a tirade of some other news du jour. Yet, thank you for this outstanding point and while I do not necessarily concur with the idea in totality, I value your viewpoint.

    Reply

  181. Hi, i feel that i saw you visited my website thus i
    came to return the want?.I’m trying to find things to improve my site!I assume its
    good enough to make use of a few of your ideas!!

    Reply

  182. You really make it seem so easy with your presentation but I find this matter to be actually something that Ithink I would never understand. It seems too complex and extremely broad forme. I’m looking forward for your next post, I’ll try to get the hang of it!

    Reply

  185. Nice post. Thanks for sharing this fantastic post with us. I enjoy at the time of reading this article. You have done a awesome job by sharing this post with us. Keep it up.

    Reply

  187. Hey there I am so grateful I found your blog, I really found you by error, while I was looking on Digg for something else, Anyhow I am here now and would just like to say kudos for a marvelous
    post and a all round thrilling blog (I also love the theme/design), I don’t have time to read it all at the minute but I have saved it
    and also included your RSS feeds, so when I have time I will be back to read much more,
    Please do keep up the superb work.

    Reply

  188. Thanks so much for providing individuals with an exceptionally terrific possiblity to read from this blog. It’s usually very good and as well , full of fun for me and my office friends to visit your blog minimum thrice in 7 days to find out the new guides you have. And lastly, I am certainly motivated with your spectacular principles served by you. Selected 2 tips in this posting are surely the most beneficial I’ve had.

    Reply

  189. Nice post. I used to be checking continuously this weblog and I
    am impressed! Extremely useful info particularly the closing part 🙂 I care for such information much.
    I used to be looking for this particular info for a very long time.
    Thank you and best of luck.

    Reply

  190. Usually I don at learn post on blogs, however I would like to say that this write-up very forced me to take a look at and do it! Your writing style has been amazed me. Thank you, quite nice article.

    Reply

  191. Link exchange is nothing else but it is simply placing the other person’s
    web site link on your page at appropriate place and other person will also do similar
    in favor of you.

    Reply

  192. I’m not that much of a internet reader to be honest but your blogs really nice, keep it up! I’ll go ahead and bookmark your website to come back in the future. All the best

    Reply

  193. Just want to say your article is as astonishing. The clarity on your post is
    just nice and that i can suppose you’re an expert in this subject.
    Well along with your permission let me to grab your feed
    to stay updated with impending post. Thanks 1,000,000 and please keep up the
    rewarding work.

    Reply

  196. Excellent blog you have here but I was wanting to know if you knew ofany community forums that cover the same topics discussed here?I’d really love to be a part of group where I can get suggestions fromother experienced people that share the same interest. If you have any suggestions,please let me know. Bless you!

    Reply

  197. Hi there! This post couldn’t be written any better! Reading through this post reminds me of my previous room mate! He always kept talking about this. I will forward this article to him. Pretty sure he will have a good read. Thank you for sharing!

    Reply

  198. I think this is among the most significant information for me. And i’m glad reading your article. But want to remark on some general things, The web site style is great, the articles is really nice : D. Good job, cheers

    Reply

  199. Hi are using WordPress for your blog platform? I’m new to the blog world but I’m trying to get started and create my own. Do you need any html coding expertise to make your own blog? Any help would be greatly appreciated!

    Reply

  200. I have not checked in here for some time since I thought it was getting boring, but the last several posts are great quality so I guess I will add you back to my everyday bloglist. You deserve it my friend 🙂

    Reply

  201. 日本女生都買它！ 髮帶多用途 遮布丁髮型30秒教學 Marie Claire (HK) Edition 之前一陣子因為日劇關係，一眾日本女生都在瘋買髮帶！但可能買了也不太懂用，而且變化也不多！這次就要教大家一個很簡單、30秒即成的髮型啦！而且這個髮型更可遮掉礙眼的布丁頭！簡直就是一舉兩得呀！

    Reply

  205. Thank you, I have recently been searching for information aboutthis subject for ages and yours is the greatest Ihave came upon till now. But, what in regards to the bottom line?Are you sure concerning the source?

    Reply

  210. My partner and I stumbled over here from a different page and thought I might check things out.
    I like what I see so i am just following you. Look forward to looking at your web page for a second time.

    Reply

  212. You actually make it seem so easy with your presentation but I find this matter to be really something that I think I would never understand. It seems too complex and very broad for me. I am looking forward for your next post, I will try to get the hang of it!

    Reply

  221. Hey I am so thrilled I found your webpage, I really found you by mistake,while I was browsing on Google for something else, Regardless I am here now and would justlike to say many thanks for a incredible post and a all round entertaining blog (Ialso love the theme/design), I don’t have time to browseit all at the minute but I have saved it andalso added in your RSS feeds, so when I have time I will be back to read much more,Please do keep up the awesome job.

    Reply

  225. Today, I went to the beachfront with my children. I found asea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put the shell to her ear and screamed.There was a hermit crab inside and it pinchedher ear. She never wants to go back! LoL I know this is totally off topic but I had to tell someone!

    Reply

Leave a Reply

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