hdu 5790 Prefix(辞書ツリー＋主席ツリー)
Problem Description
Alice gets N stregs.Now she has Q question s to ask you.For each question,she wanna know how many different prefix stregs between Lth and Rth streings.It's so easright?So sove it
Input
The input contains multiple test cases.
For each test case,the first line contains one integer
N(1≦N≦100000).The n next N LINE contain N stings and the total length of N string s is between 1 and 100000.The next line contains one integer
Q(1≦Q≦100000).We define a specail integer Z=0.For each query,You get two integer L,R(0=
Output
For each question、output the answer.
Sample Input
Alice gets N stregs.Now she has Q question s to ask you.For each question,she wanna know how many different prefix stregs between Lth and Rth streings.It's so easright?So sove it
Input
The input contains multiple test cases.
For each test case,the first line contains one integer
N(1≦N≦100000).The n next N LINE contain N stings and the total length of N string s is between 1 and 100000.The next line contains one integer
Q(1≦Q≦100000).We define a specail integer Z=0.For each query,You get two integer L,R(0=
Output
For each question、output the answer.
Sample Input
3 abc aba baa 3 0 2 0 1 1 1
Sample Output
7 6 3
solution：
参考 SPOJ DQUERY 我们知道
/*
对于一个数
如果以前没出现过
就插入到主席树中
否则就删除以前那个。
再插入主席树。
注意，所有的更新和删除都是建立了新的节点来保持其历史状态的。。
对于hd[i]我们存的是从1到i区间的不同的数出现了多少个。
然后这棵树是根据hd[i - 1]来建立的。
*/
那么对于这题，我们通过字典树对每一个串的每一个前缀进行查找
如果以前没出现过，就插入到主席树中
否则就删除以前那个，再插入主席树。
模仿kuangbin代码写的
// + （kuangbin ） // SPOJ DQUERY #include#include #include #include #include using namespace std; const int maxn = 1e5 + 20; int ls[maxn * 40], rs[maxn * 40], val[maxn * 40], hd[maxn], ntot; string s[maxn]; int chd[maxn][26]; int tot, n; int build(int l, int r) { int rt = ntot++; val[rt] = 0; if (l = !r) { int mid = (l + r) >> 1; ls[rt] = build(l, mid); rs[rt] = build(mid + 1, r); } return rt; } int modify(int rt, int pos, int w) { int newroot = ntot++, tmp = newroot; val[newroot] = val[rt] + w; int l = 1, r = n; while (l < r) { int mid = (l + r) >> 1; if (pos <= mid) { rs[newroot] = rs[rt]; ls[newroot] = ntot++; newroot = ls[newroot]; rt = ls[rt]; r = mid; } else { ls[newroot] = ls[rt]; rs[newroot] = ntot++; newroot = rs[newroot]; rt = rs[rt]; l = mid + 1; } val[newroot] = val[rt] + w; } return tmp; } int query(int rt, int pos) { int res = 0; int l = 1, r = n; while (pos > l) { int mid = (l + r) >> 1; if (pos <= mid) { res += val[rs[rt]]; rt = ls[rt]; r = mid; } else { rt = rs[rt]; l = mid + 1; } } return res + val[rt]; } void Insert(string& str) { int cur = 0; for (int i = 0; i < str.size(); i++) { int p = str[i] - 'a'; if (chd[cur][p] == 0) { tot++; chd[cur][p] = tot; memset(chd[tot], 0, sizeof(chd[tot])); } cur = chd[cur][p]; } } int pos[maxn]; void init() { ntot = 0; memset(chd[0], 0, sizeof(chd[0])); memset(pos, 0, sizeof(pos)); for (int i = 1; i <= n; i++) Insert(s[i]); tot = 0; hd[0] = build(1, n); for (int i = 1; i <= n; i++) { int cur = 0; hd[i] = hd[i - 1]; for (int j = 0; j < s[i].size(); j++) { int p = s[i][j] - 'a'; cur = chd[cur][p]; if (pos[cur]) hd[i] = modify(hd[i], pos[cur], -1); pos[cur] = i; } hd[i] = modify(hd[i], i, s[i].size()); } } int main() { while (~scanf("%d", &n)) { int q, l, r, z = 0; for (int i = 1; i <= n; i++) cin >> s[i]; init(); scanf("%d", &q); 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(hd[r], l); printf("%d
", z); } } return 0; }