HDU 5790 Prefix【主席树+字典树】

ACM_数据结构

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5790

题意：

给定$n$个字符串，所有字符串长度和小于$100000$, $Q$个询问，对于每个询问中的区间，求区间内不同前缀的个数，强制在线。
数据范围：$1 \le N \le 100000, 1 \le Q \le 100000$

分析：

首先明确字符串长度和小于100000，那么就是说最多有$100000$个不同前缀。
那么我们可以给每个不同的前缀赋一个值，最多有$100000$个不同的数，问题就转化为求给定区间内不同数个数，接下来就是主席树的经典套路。
赋值过程可以使用哈希或者Trie树，Trie树的话对于每个字符串每经过一个结点即对应唯一的一段前缀，即用该结点标号作为该前缀的值。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
/*************************************************************************
    > File Name: 5790.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/10/6 19:03:47
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;//[]
typedef unsigned long long ull;
const int maxn = 1e5 + 5, maxm = 50 * maxn;
int lson[maxm], rson[maxm], t[maxn], tree[maxm];
int tot;
//lson,rson记录左右节点标号，t记录每一个前缀构成的线段树的根节点标号
int build(int l, int r)
{
    int root = tot++; tree[root] = 0;
    int mid = l + r >> 1;
    if(l == r) return root;
    lson[root] = build(l, mid);
    rson[root] = build(mid + 1, r);
    return root;
}
int update(int root, int l, int r, int num, int val)
{
	int newroot = tot++;
	tree[newroot] = tree[root] + val;
	if(l == r)	return newroot;
    int mid = l + r >> 1;
    if(num <= mid){
        lson[newroot] = update(lson[root], l, mid, num, val);//有变动，重新建立
        rson[newroot] = rson[root];//右边不变
        
    }else{
        rson[newroot] = update(rson[root], mid + 1, r, num, val);//有变动，重新建立
        lson[newroot] = lson[root];//左边不变
    }
	return newroot;
}
int query(int L, int R, int l, int r, int i)
{
	if(l == L && r == R) return tree[i];
	int mid = l + r >> 1;
	if(R <= mid) return query(L, R, l, mid, lson[i]);
	else if(L > mid) return query(L, R, mid + 1, r, rson[i]);
	else return query(L, mid, l, mid, lson[i]) + query(mid + 1, R, mid + 1, r, rson[i]);
}
char s[maxn];
int last[maxn];
int son[maxn][26];
int n;
int root, alloc;
int newnode()
{
	memset(son[alloc], -1, sizeof(son[alloc]));
    return alloc++;
}
void init()
{
	alloc = 0;
	root = newnode();
}
void insert(int id)
{
	int len;
	int p = root;
	t[id] = t[id - 1];
    for(int i = 0; s[i]; ++i){
        int nx = s[i]-'a';
		int &node = son[p][nx];
		if(node == -1) node = newnode();
		if(last[node] != -1) t[id] = update(t[id], 1, n, last[node], -1);
		t[id] = update(t[id], 1, n, id, 1);
		last[node] = id;
		p = son[p][nx];
    }
}
int main (void)
{
	while(~scanf("%d", &n)){
		tot = 0;
		init();
		memset(last, -1, sizeof(last));
		t[0] = build(1, n);
		for(int i = 1; i <= n; ++i){
			scanf("%s", s);
			insert(i);
		}
		int q;scanf("%d", &q);
		int l, r;
		int z = 0;
		while(q--){
			scanf("%d%d", &l, &r);
			l = (z + l) % n + 1;
			r = (z + r) % n + 1;
			if(l > r) swap(l, r);
			z = query(l, r, 1, n, t[r]);
			printf("%d\n", z);
		}
	}
	return 0;
}
文章目录
  1. 1. 题目链接：
  2. 2. 题意：
  3. 3. 分析：
  4. 4. 代码：