【BZOJ 4212】神牛的养成计划

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4212
神犇题解:http://www.cnblogs.com/yousiki/p/6550484.html

解题报告

这题如果没有强制在线,那么我们可以用$Trie + bitset$在$O(\frac{2000000n}{64})$的时间复杂度过
如果强制在线并且$s1,s2$等长,那么我们可以在$O(2000000 \log 2000000)$的时间复杂度过

现在解决原问题,先考虑一个暴力:
先把前缀能匹配上的串找出来,然后我们在其中找出后缀能匹配的串
考虑一下后缀数组:按字典序排序后,前缀能匹配上的一定是一个区间
于是我们可以先建一个正串的$Trie$,用来找出前缀合法的字符串区间
然后我们将反串建成一个持久化$Trie$,每一次用前缀合法的区间再去查后缀即可

另外还有一点$Trick$就是字符串排序:我们可以先将正串建成$Trie$,然后贪心$DFS$
这样排序的复杂度就可以是线性的,总的时间复杂度也就是线性的了

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2000009;
const int M = 2009;
const int SGZ = 26;

int n,m,tot,beg[M],sz[M],ord[M];
char s1[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	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;
}

class Trie{
	int cnt,ch[N][26],mn[N],mx[N];
	vector<int> id[N];
	public:
		inline void insert(char *s, int len, int ID) {
			int w = 0;
			for (int i=0;i<len;i++) {
				int c = s[i] - 'a';
				if (!ch[w]) ch[w] = ++cnt;
				w = ch[w];
			} 
			id[w].push_back(ID);
		}
		inline void sort(int w, int *arr, int &cur) {
			for (int i=0;i<id[w].size();i++) {
				arr[++cur] = id[w][i];
			}
			for (int i=0;i<SGZ;i++) {
				if (ch[w][i]) {
					sort(ch[w][i], arr, cur);
				}
			}
		}
		inline void mark(int val, char *s, int len) {
			int w = 0;
			for (int i=0;i<len;i++) {
				int c = s[i] - 'a';
				w = ch[w];
				if (!mn[w] || mn[w] > val) mn[w] = val;
				if (!mx[w] || mx[w] < val) mx[w] = val;
			}
		}
		inline void query(char *s, int len, int &l, int &r) {
			int w = 0;
			for (int i=0;i<len;i++) {
				int c = s[i] - 'a';
				if (!ch[w]) {
					l = 1; r = 0;
					return;
				} else {
					w = ch[w];
				}
			}
			l = mn[w]; 
			r = mx[w]; 
		}
	private:
}trie; 

class Persistent_Trie{
	int cnt,root[M],sum[N],ch[N][26];
	public:
		inline void insert(int p, int w, char *s, int len) {
			Insert(root[p], root[w], s, len); 
		}
		inline int query(int l, int r, char *s, int len) {
			if (l > r) return 0;
			int ret = 0, w = root[r]; 
			for (int i=0;i<len;i++) {
				w = ch[w][s[i]-'a']; 
			}
			ret += sum[w];
			w = root[l-1];
			for (int i=0;i<len;i++) {
				w = ch[w][s[i]-'a'];
			}
			ret -= sum[w];
			return ret;
		}
	private:
		void Insert(int p, int &w, char *s, int len) {
			w = ++cnt;
			sum[w] = sum[p] + 1;
			memcpy(ch[w], ch[p], sizeof(ch[w]));
			if (len <= 0) return;
			int c = s[len-1] - 'a'; 
			Insert(ch[p], ch[w], s, len - 1);
		}
}PTE; 

int main() {
	n = read();
	for (int i=1,last=0;i<=n;i++) {
		beg[i] = last;
		scanf("%s", s1+last);
		sz[i] = strlen(s1+last);
		trie.insert(s1+last, sz[i], i);
		last += sz[i];
	}
	tot = 0;
	trie.sort(0, ord, tot);
	for (int i=1;i<=n;i++) {
		trie.mark(i, s1+beg[ord[i]], sz[ord[i]]);
		PTE.insert(i-1, i, s1+beg[ord[i]], sz[ord[i]]);
	}
	m = read(); 
	for (int tt=1,last=0,l,r;tt<=m;tt++) {
		scanf("%s",s1);
		int len = strlen(s1);
		for (int i=0;i<len;i++) {
			s1[i] = (s1[i] - 'a' + last) % SGZ + 'a';
		} 
		trie.query(s1, len, l, r);
		scanf("%s",s1);
		len = strlen(s1);
		for (int i=0,j=len-1;i<j;i++,j--) {
			swap(s1[i], s1[j]);
		}
		for (int i=0;i<len;i++) {
			s1[i] = (s1[i] - 'a' + last) % SGZ + 'a';
		}
		last = PTE.query(l, r, s1, len);
		printf("%d\n",last);
	}
	return 0;
}

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

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

【Codeforces 706D】Vasiliy’s Multiset

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