【Codeforces 707D】Persistent Bookcase

题目链接:http://codeforces.com/problemset/problem/707/D

这个东西,一开始写了一个严格小于O(n*q*log(q))的算法,结果T到死QAQ
然后看到了这一篇blog:http://h0rnet.hatenablog.com
发现严格O(n*q)的暴力都可过QAQ
然而感觉这样暴力一点都不清真啊!虽然只跑了200ms多一点

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

int n,m,q;

namespace Chair_Tree{
	#define CT Chair_Tree
	const int MAXN = 2000000;
	const int N = 1000+9;
	const int Q = 100000+9;
	
	int ls[MAXN],rs[MAXN],sum[MAXN],TY,ans_tmp,cnt,tmp_root,pr[N],pv[N],vout[Q];
	int root[Q][N]; bool rev[Q][N];
	
	inline void Clone(int p, int w) {
		memcpy(root[w],root[p],sizeof(root[w]));
		memcpy(rev[w],rev[p],sizeof(rev[w]));
		vout[w] = vout[p];
	}
	
	void modify(int p, int &w, int l, int r, int pos){
		w = ++cnt; ls[w] = ls[p]; rs[w] = rs[p]; sum[w] = sum[p];
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (pos < mid) modify(ls[p],ls[w],l,mid-1,pos);
			else modify(rs[p],rs[w],mid,r,pos);
			sum[w] = sum[ls[w]] + sum[rs[w]];
		} else if (sum[w] + TY == 1) sum[w] ^= 1, ans_tmp = 1;
	}
	
	inline int modify(int i, int j, int ty, int k){
		Clone(k-1,k); ans_tmp = 0; TY = ty^rev[k][i]; 
		modify(root[k][i],tmp_root,1,m,j); root[k][i] = tmp_root;
		if (ty == 1) vout[k] += ans_tmp;
		else vout[k] -= ans_tmp;
		return vout[k];
	}
	
	inline int REV(int i,int k){
		Clone(k-1,k); rev[k][i] ^= 1;
		int tmp = sum[root[k-1][i]], w=tmp;
		if (rev[k-1][i]) tmp = m - tmp;
		else w = m - w; vout[k] += w - tmp;
		return vout[k];
	}	
};

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;
}

int main(){
	cin>>n>>m>>q; 
	for (int i=1,ty,x,y;i<=q;i++) {
		ty = read();
		if (ty == 1) {
			x = read(); y = read();
			printf("%d\n",CT::modify(x,y,1,i));
		} else if (ty == 2) {
			x = read(); y = read();
			printf("%d\n",CT::modify(x,y,0,i));
		} else if (ty == 3) printf("%d\n",CT::REV(read(),i));
		else CT::Clone(read(),i), printf("%d\n",CT::vout[i]);
	} 
	return 0;
}

还有那个离线的版本,真的是一点都不清真啊!

13 thoughts to “【Codeforces 707D】Persistent Bookcase”

  1. 838627 844807Although you are any with the lucky enough choices, it comes evidently, although capture the fancy of the particular coveted by ly folks other helpful you you meet might possibly nicely have hard times this particular problem. pre owned awnings 315376

  2. 296901 637030Spot lets start on this write-up, I seriously believe this amazing website requirements much much more consideration. Ill far more likely once once more to read a terrific deal much more, a lot of thanks that information. 431317

  3. 145742 464445There exist a couple of a lot of different distinct levels among the California Weight loss program and each and every a person is pretty crucial. Youre procedure stands out as the the actual giving up with all the power. weight loss 552292

  4. 475926 278285Good day! This post could not be written any much better! Reading this post reminds me of my previous room mate! He always kept chatting about this. I will forward this write-up to him. Fairly certain he will have a great read. Thanks for sharing! 681113

  5. 458604 333646Hi this is somewhat of off topic but I was wondering if blogs use WYSIWYG editors or should you need to manually code with HTML. Im starting a blog soon but have no coding expertise so I wanted to get guidance from someone with experience. Any support would be greatly appreciated! 196520

  6. 202550 331049I ran into this page accidentally, surprisingly, this is a great website. The website owner has done an excellent job writing/collecting articles to post, the info here is genuinely insightful. You just secured yourself a guarenteed reader. 154107

  7. 719278 675913I discovered your blog web site internet website on the internet and appearance some of your early posts. Continue to keep in the excellent operate. I just now additional increase your Rss to my MSN News Reader. Seeking toward reading far much more from you locating out at a later date! 622083

Leave a Reply to Nicole Cancel reply

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