Category: 数据结构

今天乱翻别人的Blog，然后翻到了这个：
http://acrossthesky.logdown.com/posts/712254-some-basic-data-structures
这货绝逼是神犇啊！感觉从NOIP到IOI的数据结构都讲完了！
是我有史以来看过的最荡气回肠的一篇文章！大赞！
本地网页备份：basic_data_structure
本地图片备份：http://oi.cyo.ng/wp-content/uploads/2016/09/47896453768412.png

题目链接：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;
}

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

题目传送门：http://codeforces.com/problemset/problem/706/E
官方题解：http://codeforces.com/blog/entry/46510

这个题感觉出得很好啊！
没想到链表还能这么考！秒啊！

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

const int MAXN = 1000+9;

int d[MAXN*MAXN],r[MAXN*MAXN],mat[MAXN*MAXN],m,n,q,vout[MAXN][MAXN];

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

#define id(x, y) ((x)+1 + (y)*(n+2))

inline void change(int x1, int y1, int x2, int y2, int x, int y){
	int p1 = id(0,0), p2 = id(0,0); 
	for (int j=1;j<y1;j++) p1 = d[p1]; for (int i=1;i<=x1;i++) p1 = r[p1];
	for (int j=1;j<y2;j++) p2 = d[p2]; for (int i=1;i<=x2;i++) p2 = r[p2];
	for (int i=1;i<=x;i++) swap(d[p1], d[p2]), p1 = r[p1], p2 = r[p2];
	p1 = id(0,0), p2 = id(0,0); 
	for (int j=1;j<y1+y;j++) p1 = d[p1]; for (int i=1;i<=x1;i++) p1 = r[p1];
	for (int j=1;j<y2+y;j++) p2 = d[p2]; for (int i=1;i<=x2;i++) p2 = r[p2];
	for (int i=1;i<=x;i++) swap(d[p1], d[p2]), p1 = r[p1], p2 = r[p2];
	
	
	p1 = id(0,0), p2 = id(0,0); 
	for (int i=1;i<x1;i++) p1 = r[p1]; for (int j=1;j<=y1;j++) p1 = d[p1]; 
	for (int i=1;i<x2;i++) p2 = r[p2]; for (int j=1;j<=y2;j++) p2 = d[p2];
	for (int j=1;j<=y;j++) swap(r[p1], r[p2]), p1 = d[p1], p2 = d[p2];
	p1 = id(0,0), p2 = id(0,0); 
	for (int i=1;i<x1+x;i++) p1 = r[p1]; for (int j=1;j<=y1;j++) p1 = d[p1]; 
	for (int i=1;i<x2+x;i++) p2 = r[p2]; for (int j=1;j<=y2;j++) p2 = d[p2];
	for (int j=1;j<=y;j++) swap(r[p1], r[p2]), p1 = d[p1], p2 = d[p2];
}

inline void trans(){
	int head = id(0,0); 
	for (int j=1;j<=m;j++) {
		head = d[head];
		for (int i=1,w=r[head];i<=n;i++,w=r[w])
			vout[i][j] = mat[w];
	}
	for (int j=1;j<=m;j++) {for (int i=1;i<=n;i++) printf("%d ",vout[i][j]); printf("\n");}
}

int main(){
	m = read(); n = read(); q = read();
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) mat[id(i,j)] = read();
	for (int j=0;j<=m+1;j++) for (int i=0;i<=n+1;i++) d[id(i,j)] = id(i,j+1), r[id(i,j)] = id(i+1,j);
	
	for (int k=1,x1,x2,y1,y2,lh,lw;k<=q;k++) {
		y1 = read(), x1 = read();
		y2 = read(), x2 = read();
		lh = read(), lw = read();
		change(x1,y1,x2,y2,lw,lh);
	} trans();
	return 0;
}

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