HDU5790Prefix(主席树+单词Trie)

给出n个字符串, 编号从1~n.

每次询问编号在[l, r]区间的所有字符串中, 不同前缀的数目. (强制在线)

解题思路

思维

首先考虑到字符串的总长度为1E5, 因此不同前缀的数量最多为1E5.

如果不加以区间的限制, 询问所有的字符串有多少不同的前缀. 则我们可以通过Trie来完成. 我们把字符串插入Trie中, 如果此时我们为当前字符开辟了新节点, 则不同前缀数目&＃43;1.

考虑区间限制, 如果我们把不同的前缀 修改为 不同的数字(即: 询问[l, r]区间不同数字的数目), 则这个题变成了HH的项链, 只不过是强制在线了, 我们可以通过主席树来解决.

主席树 &＃43; Tire

我们考虑通过Trie树来存储字符串, 对于每个节点我们都存储上一次出现的位置.

这样用HH的项链中的解法三来维护区间不同数字的个数即可.

AC代码

#include
#define rep(i, n) for (int i &＃61; 1; i <&＃61; (n); &＃43;&＃43;i)
using namespace std;
typedef long long ll;
const int N &＃61; 1E5 &＃43; 5, L &＃61; 0, R &＃61; N - 5;
int root[N], ind;
struct node {int l, r;int val;
}t[N * 18];
int build(int a, int c, int tl, int tr, int p) {int x &＃61; &＃43;&＃43;ind; t[x] &＃61; t[p];t[x].val &＃43;&＃61; c;if (tl &＃61;&＃61; tr) return x;int mid &＃61; tl &＃43; tr >> 1;if (a <&＃61; mid) t[x].l &＃61; build(a, c, tl, mid, t[p].l);else t[x].r &＃61; build(a, c, mid &＃43; 1, tr, t[p].r);return x;
}
int ask(int l, int r, int tl, int tr, int p, int x) {if (l <&＃61; tl and r >&＃61; tr) return t[x].val - t[p].val;int mid &＃61; tl &＃43; tr >> 1;int res &＃61; 0;if (l <&＃61; mid) res &＃43;&＃61; ask(l, r, tl, mid, t[p].l, t[x].l);if (r > mid) res &＃43;&＃61; ask(l, r, mid &＃43; 1, tr, t[p].r, t[x].r);return res;
}
void initct(int n) {rep(i, n) root[i] &＃61; 0;rep(i, ind) t[i] &＃61; { 0, 0, 0 };ind &＃61; 0;
}namespace {int t[N][26], ind;int pos[N];void insert(int a, const string& s) {int x &＃61; 0; int pre &＃61; a - 1;for (auto& op : s) {char c &＃61; op - &＃39;a&＃39;;if (!t[x][c]) t[x][c] &＃61; &＃43;&＃43;ind;x &＃61; t[x][c];root[a] &＃61; build(pos[x], 1, L, R, root[pre]);pre &＃61; a; pos[x] &＃61; a;}}void clear(int x &＃61; 0) {for (int i &＃61; 0; i < 26; &＃43;&＃43;i) {if (t[x][i]) {pos[t[x][i]] &＃61; 0;clear(t[x][i]), t[x][i] &＃61; 0;}}}void inittrie() { ind &＃61; 0, clear(); }
}
char s[N];
int main()
{int n;while (~scanf("%d", &n)) {inittrie(), initct(n);rep(i, n) {scanf("%s", s);insert(i, s);}int m; scanf("%d", &m);int res &＃61; 0;rep(i, m) {int l, r; scanf("%d %d", &l, &r);l &＃61; (l &＃43; res) % n &＃43; 1, r &＃61; (r &＃43; res) % n &＃43; 1;if (l > r) swap(l, r);printf("%d\n", res &＃61; ask(0, l - 1, L, R, root[l - 1], root[r]));}}return 0;
}


END