【Codeforces 703D】Mishka and Interesting sum

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

题目传送门：http://codeforces.com/contest/703/problem/D
中文题面：http://www.cnblogs.com/zqy123/p/5746481.html

这题，第一眼看到就感觉是莫队
然后算一算复杂度感觉能卡过，于是死坑莫队，遂卒
然后看题解，突然想起来以前做过这么一道题，还有分块的解法
不过最简单的做法，可以记录pre[]，然后维护区间的unique之后的值
离线的话，一维BIT即可，不离线的话，可以上函数式线段树

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<map>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 1000000+9;

int arr[N],n,m,sum[N],vout[N];
struct Query{
	int l,r,num;
	inline bool operator < (const Query &B) const {
		return r < B.r;
	}
}q[N];
map<int,int> pre;

namespace Fenwick_Tree{
	#define BIT Fenwick_Tree
	#define lowbit(x) ((x)&-(x))
	int v[N];
	
	inline void modify(int i) {
		int tmp = pre[arr[i]]; pre[arr[i]] = i;
		if (tmp) for (int j=tmp;j<=n;j+=lowbit(j)) v[j] ^= arr[i]; 
		for (int j=i;j<=n;j+=lowbit(j)) v[j] ^= arr[i];
	}
	
	inline int query(int l, int r) {
		int ret = 0; l--;
		for (;r;r-=lowbit(r)) ret ^= v[r];
		for (;l;l-=lowbit(l)) ret ^= v[l];
		return ret;
	}
};

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

int main(){
	n = read(); for (int i=1;i<=n;i++) arr[i] = read(); 
	m = read(); for (int i=1;i<=m;i++) q[i].l=read(), q[i].r=read(), q[i].num = i;
	sort(q+1,q+1+m); 
	for (int i=1,cur=1;i<=n;i++) {
		sum[i] = sum[i-1] ^ arr[i]; BIT::modify(i);
		for (;cur <= m && q[cur].r == i;cur++) 
			vout[q[cur].num] = sum[i]^sum[q[cur].l-1]^BIT::query(q[cur].l,q[cur].r);
	}
	for (int i=1;i<=m;i++) printf("%d\n",vout[i]);
	return 0;
}

把BZOJ上那题翻出来了，分块的做法让我们召唤黄学长：http://hzwer.com/3663.html

263 thoughts to “【Codeforces 703D】Mishka and Interesting sum”

  90. Excellent read, I just passed this onto a colleague who was doing some research on that. And he just bought me lunch as I found it for him smile Therefore let me rephrase that: Thank you for lunch! “We know what happens to people who stay in the middle of the road. They get run over.” by Ambrose Gwinett Bierce.

    Reply

  193. I was curious if you ever thought of changing the page layout of your site? Its very well written; I love what youve got to say. But maybe you could a little more in the way of content so people could connect with it better. Youve got an awful lot of text for only having one or two pictures. Maybe you could space it out better?

    Reply

  195. I don’t even understand how I stopped up rignt here, howewver I assumed thispublish used to be good. I don’t recognise who you’re butcertaily you are going to a well-known blogger iif you aren’t already.Cheers!

    Reply

  197. The Zune concentrates on being a Portable Media Player. Not a web browser. Not a game machine. Maybe in the future it’ll do even better in those areas, but for now it’s a fantastic way to organize and listen to your music and videos, and is without peer in that regard. The iPod’s strengths are its web browsing and apps. If those sound more compelling, perhaps it is your best choice.

    Reply

  198. Hey there. I discovered your web site by way of Google while looking for a related subject, your website got here up. It seems great. I have bookmarked it in my google bookmarks to visit then.

    Reply

  199. I loved as much as you will receive carried out right here. The sketch is tasteful, your authored material stylish. nonetheless, you command get bought an nervousness over that you wish be delivering the following. unwell unquestionably come further formerly again as exactly the same nearly a lot often inside case you shield this increase.

    Reply

  200. Hey there! I’ve been following your website for a long timenow and finally got the bravery to go ahead and giveyou a shout out from Huffman Tx! Just wanted to tell youkeep up the great work!

    Reply

  209. I would like to thnkx for the efforts you have put in writing this blog. I’m hoping the same high-grade web site post from you in the upcoming also. In fact your creative writing abilities has inspired me to get my own website now. Really the blogging is spreading its wings rapidly. Your write up is a good example of it.

    Reply

  217. That is a very good tip especially to those fresh to the blogosphere. Short but very accurate info… Thanks for sharing this one. A must read article!|

    Reply

  221. It is appropriate time to make some plans for the future and it’s time to be happy. I have read this post and if I could I desire to suggest you few interesting things or suggestions. Maybe you could write next articles referring to this article. I wish to read more things about it!|

    Reply

  224. Nice post. I was checking constantly this blog and I am impressed! Extremely helpful information specifically the last part 🙂 I care for such information a lot. I was looking for this particular info for a very long time. Thank you and good luck.|

    Reply

  237. I’ve been browsing online greater than three hours as of late, but I by no means found any fascinating article like yours. It is beautiful price enough for me. In my opinion, if all site owners and bloggers made just right content as you probably did, the internet will probably be a lot more helpful than ever before.|

    Reply

  238. A fascinating discussion is worth comment. There’s no doubt that that you should publish more about this subject, it may not be a taboo subject but generally folks don’t discuss these subjects. To the next! Best wishes!!|

    Reply

  261. This is really interesting, You are a very skilled blogger. I have joined your rss feed and look forward to seeking more of your great post. Also, I have shared your web site in my social networks!|

    Reply

  262. I don’t even know how I stopped up right here, however I thought this submit used to be great. I do not know who you are but definitely you’re going to a well-known blogger should you are not already. Cheers!|

    Reply

  263. I’m really enjoying the design and layout of your site. It’s a very easy on the eyes which makes it much more pleasant for me to come here and visit more often. Did you hire out a developer to create your theme? Excellent work!|

    Reply

Leave a Reply

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