bzoj3439: Kpm的MC密码

SB题，网上都用了主席树………
其实只需要每个trie节点开一个vector，记录一下这个节点的子树有哪些字符串，
按顺序加入每个字符串，就可以保证vector是有序的，完了。

#include
#include
#include
#include
using namespace std;
const int N = 1e5 + 9, M = 3e5 + 9;int n;
char s[N];vector<int>V[M];
int ch[M][26], cnt, i, dy[N], j;void Add (int x, int l) {for (int y; 1; x = ch[x][y], --l) {V[x].push_back(i);if (l == -1) return void(dy[i] = x);y = s[l] - 'a';if (!ch[x][y]) ch[x][y] = ++cnt;}
}int Judge (vector<int>&V, int k) {printf("%d\n", k <= V.size() ? V[k - 1] : -1);return -1;
}int main () {scanf("%d", &n);for (i = 1; i <= n; ++i) scanf("%s", s), Add(0, strlen(s) - 1);for (i = 1; i <= n; ++i) scanf("%d", &j), Judge(V[dy[i]], j);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！