【Codeforces 817E】Choosing The Commander

相关链接

题目传送门:http://codeforces.com/contest/817/problem/E

解题报告

考虑异或之后小于的话
把士兵插入到Trie树里面,然后走一条链即可
时间复杂度:$O(n \log 10^8)$

Code

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

const int N = 100009 * 32;

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

class Trie{
int root, cnt;
struct Node{
	int sum, ch[2];
}p[N];
public:
	inline void modify(int v, int d) {
		modify(root, 30, v, d);
	}
	inline int query(int buf, int lim) {
		return query(root, 30, buf, lim);
	}
private:
	inline void modify(int &w, int t, int v, int d) {
		w = w? w: ++cnt;
		p[w].sum += d;
		if (t >= 0) {
			modify(p[w].ch[(v >> t) & 1], t - 1, v, d);
		}
	}
	inline int query(int w, int t, int buf, int lim) {
		if (!w || t == -1) {
			return 0;
		} else {
			int ret = 0, t2 = (buf >> t) & 1, t1 = (lim >> t) & 1;
			if (t1) {
				ret += p[p[w].ch[t2]].sum;
				ret += query(p[w].ch[t2 ^ 1], t - 1, buf, lim);
			} else {
				ret += query(p[w].ch[t2], t - 1, buf, lim);
			}
			return ret;
		}
	}
}trie;

int main() {
	int n = read();
	for (int i = 1; i <= n; i++) {
		int ty = read();
		if (ty == 1) {
			trie.modify(read(), 1);
		} else if (ty == 2) {
			trie.modify(read(), -1);
		} else {
			int p = read(), l = read();
			printf("%d\n", trie.query(p, l));
		}
	}
	return 0;
}

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

【BZOJ 3926】[ZJOI2015] 诸神眷顾的幻想乡

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3926
神犇题解:http://wjmzbmr.com/archives/zjoi-2015-day-1题解/

解题报告

陈老师的语文真刺激!
把叶节点最多只有20个这个条件埋得那么深 QwQ
一开始以为那个条件意思是度数不超过20,于是想边分治,后来都想到”万径人踪灭”去了……

考虑树上每一条路径,至少存在一个叶子结点,使得将该叶子结点作为根后,这条路径上的结点深度递减
于是对于每一个叶节点都DFS一遍,然后建广义后缀自动机
广义自动机的话,直接看这份代码就好吧!
或者想全面学习的话,可以看这里:传送门

另外,这题据陈老师说,后缀数组也可以做
但我不会啊,跪求神犇带 _(:з」∠)_

Code

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

const int N = 200000+9;
const int M = 2000000;
const int C = 10;

int n,c,col[N],head[N],to[N],nxt[N],in[N];

class Suffix_Automaton{
	int ch[M][C],pre[M],len[M],cnt;
	public:
		inline int insert(int last, int t) {
			int w = ++cnt; len[w] = len[last] + 1; pre[0] = -1;
			for (;~last&&!ch[last][t];last=pre[last]) ch[last][t] = w;
			if (~last) {
				if (len[ch[last][t]] == len[last] + 1) {
					pre[w] = ch[last][t];
				} else {
					int nw = ++cnt, tmp = ch[last][t];
					len[nw] = len[last] + 1; 
					pre[nw] = pre[tmp]; pre[tmp] = pre[w] = nw; 
					memcpy(ch[nw],ch[tmp],sizeof(ch[nw]));
					for (;~last&&ch[last][t]==tmp;last=pre[last]) ch[last][t] = nw;
				}
			} return w;
		} 
		inline LL solve() {
			LL ret = 0;
			for (int i=1;i<=cnt;i++)
				ret += len[i] - len[pre[i]];
			return ret; 
		}
}SAM;

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

inline void Add_Edge(int u, int v) {
	static int E = 1; in[u]++; in[v]++;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

void DFS(int w, int f, int s) {
	int rt = SAM.insert(s, col[w]);
	for (int i=head[w];i;i=nxt[i]) 
		if (to[i] != f) DFS(to[i], w, rt);
}

int main() {
	n = read(); c = read();
	for (int i=1;i<=n;i++) col[i] = read();
	for (int i=1;i<n;i++) Add_Edge(read(),read());
	for (int i=1;i<=n;i++) if (in[i] == 1) DFS(i, i, 0);
	printf("%lld\n",SAM.solve());
	return 0;
}

【BZOJ 4571】[SCOI2016] 美味

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4571

考试的时候,找了一个小时的规律,总觉得加法在二进制下有奇特的规律
考完试后知道真相的我,哭晕在厕所…

仍然考虑按位贪心
于是发现高位确定,低位不确定在十进制下是一个区间,于是搞一搞函数式线段树
仔细想一想,一般的Xor问题也可以这么做,trie树只是一个特殊的优化

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

const int N = 200000+9;
const int M = N * 18;

int arr[N],n,m,MX; 

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

namespace Chair_Tree{
	#define CT Chair_Tree
	int ch[M][2],sum[M],cnt,root[N];
	int ans_tmp,L,R;
	
	void build(int p, int &w, int l, int r, int cur) {
		w = ++cnt; memcpy(ch[w],ch[p],sizeof(ch[w]));
		sum[w] = sum[p] + 1; if (l < r) {
			int mid = l + r + 1 >> 1;
			if (cur < mid) build(ch[p][0],ch[w][0],l,mid-1,cur);
			else build(ch[p][1],ch[w][1],mid,r,cur);
		}
	}
	
	inline void Build_Tree() {
		for (int i=1;i<=n;i++) 
			build(root[i-1],root[i],0,MX,arr[i]);
	}
	
	void ask(int w, int l, int r, int f) {
		if (L <= l && r <= R) ans_tmp += sum[w]*f;
		else if (w) {
			int mid = l + r + 1 >> 1;
			if (L < mid) ask(ch[w][0],l,mid-1,f);
			if (R >= mid) ask(ch[w][1],mid,r,f);
		}
	}
	
	inline int Query(int r1, int r2, int l, int r) {
		l = max(0,l); r = min(MX,r); 
		if (l > r) return 0;
		
		ans_tmp = 0; L = l; R = r;
		ask(r1,0,MX,-1); ask(r2,0,MX,1);
		return ans_tmp;
	}
	
	inline int query(int b, int x, int l, int r){
		int ret = 0, r1 = root[l-1], r2 = root[r];
		for (int i=17;~i;i--) {
			int c = (b & (1<<i)) ^ (1<<i); 
			if (Query(r1,r2,ret+c-x,ret+c+(1<<i)-1-x)) ret += c;
			else ret += c ^ (1<<i);
		} return ret^b;
	}
};

int main(){
	n = read(); m = read();
	for (int i=1;i<=n;i++) MX = max(MX, arr[i]=read());
	CT::Build_Tree();
	for (int i=1,b,x,l,r;i<=m;i++) {
		b = read(); x = read(); 
		l = read(); r = read();
		printf("%d\n",CT::query(b,x,l,r));
	}
	return 0;
}

【BZOJ 4523】[Cqoi2016] 路由表

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4523
数据生成器:http://paste.ubuntu.com/23140079/

这个题,Trie树的做法很显然,可以持久,也可以不持久
但此题卡常QAQ
在BZOJ上过的不算,是男人就上Super OJ去交
我被逼着优化成了BZOJ上的Rank11才在SOJ上刚好卡过 (╯‵□′)╯︵┻━┻

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

const int N = 1000000+9;
const int M = 33000000;

int Stack[N];
bool ip[40];

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

namespace Trie{
	#define TRE Trie
	int tot=1,ch[M][2],cnt,root=1,end[M];
	
	inline void modify(int len){
		int w = root; 
		for (int i=1;i<=len;i++) {
			int c = ip[i];
			if (ch[w]) w = ch[w];
			else w = ch[w] = ++tot;
		}
		end[w] = ++cnt;
	}
	
	inline int query(int l, int r){
		int top = 0, w = root, t = 1;
		while (w) {
			if (end[w]) {
				while (top && Stack[top] > end[w]) top--;
				Stack[++top] = end[w];
			}	
			w = ch[w][ip[t]]; t++;
		} t = 0;
		for (int i=1;i<=top;i++) 
			if (Stack[i] > r) break;
			else if (Stack[i] >= l) t++;
		return t;
	}
};

inline void Get_IP(){
	memset(ip,0,sizeof(ip));
	for (int j=1,sta=9;j<=4;j++,sta+=8) {
		int TP = read(), i = 1;
		while (TP) ip[sta-i] = TP & 1, TP >>= 1, i++; 
	}
}

int main(){
	for (int k=read(),a,b;k;k--) {
		char c=getchar(); 
		while (c != 'A' && c != 'Q') c=getchar();
		if (c == 'A') {
			Get_IP();
			TRE::modify(read());
		} else {
			Get_IP();
			a = read(); b = read();
			printf("%d\n",TRE::query(a,b));
		}
	}
	return 0;
}