[BZOJ 3439]Kpm的MC密码

Kpm当年设下的问题是这样的：

    现在定义这么一个概念，如果字符串s是字符串c的一个后缀，那么我们称c是s的一个kpm串。

    系统将随机生成n个由a…z组成的字符串，由1…n编号（s1,s2…,sn），然后将它们按序告诉你，接下来会给你n个数字，分别为k1…kn，对于每一个ki，要求你求出列出的n个字符串中所有是si的kpm串的字符串的编号中第ki小的数，如果不存在第ki小的数，则用-1代替。（比如说给出的字符串是cd,abcd,bcd,此时k1=2，那么”cd”的kpm串有”cd”,”abcd”,”bcd”,编号分别为1,2,3其中第2小的编号就是2）（PS：如果你能在相当快的时间里回答完所有n个ki的查询，那么你就可以成功帮kpm进入MC啦~~）

我累个去你有重串不记得说一声！！***(虽然写的时候考虑了一下但是由于蒟蒻太懒自认为没有重串)

调死辣。。

呢。倒着建棵Tire

然后询问dfs序上一段区间的最第k小值

主席树妥妥的

#include #define maxn 500010
using namespace std;int n, root, size;int t[maxn][26], mark[maxn];
int Map[maxn];struct Edge{int to, next;
}edge[maxn];
int h[maxn], cnt;
void add(int u, int v){cnt ++;edge[cnt].to = v;edge[cnt].next = h[u];h[u] = cnt;
}char s[maxn];int par[maxn];
int getfa(int x){return par[x] == x ? x : par[x] = getfa(par[x]);}void Insert(int Id){int N = strlen(s+1), now = root;for(int i = N; i >= 1; i --){int p = s[i] - 'a';if(!t[now][p])t[now][p] = ++ size;now = t[now][p];}if(!mark[now]){mark[now] = true;Map[now] = Id;}else{par[getfa(Id)] = Map[now];}
}int que[maxn], fa[maxn];vectortmp[maxn];void BFS(){int head = 0, tail = 0, u, v;que[tail ++] = root;while(head < tail){u = que[head ++];if(mark[u])add(Map[fa[u]], Map[u]);for(int i = 0; i < 26; i ++){if(v = t[u][i]){que[tail ++] = v;if(mark[u])fa[v] = u;else fa[v] = fa[u];}}}for(int i = 1; i <= n; i ++)if(getfa(i) != i)tmp[getfa(i)].push_back(i);
}int In[maxn], Out[maxn], dfs_clock, dfn[maxn];void DFS(int u){In[u] = ++ dfs_clock;dfn[dfs_clock] = u;for(int i = 0; i < tmp[u].size(); i ++){int v = tmp[u][i];In[v] = In[u];dfn[++ dfs_clock] = v;}for(int i = h[u]; i; i = edge[i].next)DFS(edge[i].to);Out[u] = dfs_clock;for(int i = 0; i < tmp[u].size(); i ++){int v = tmp[u][i];Out[v] = dfs_clock;}
}namespace Segtree{#define M 3000000int L[M], R[M], C[M], T[maxn], size, k;int build(int l, int r){int root = ++ size;if(l == r)return root;int mid = l + r >> 1;L[root] = build(l, mid), R[root] = build(mid+1, r);return root;}int add(int root, int l, int r, int pos, int val){int cur = ++ size;L[cur] = L[root], R[cur] = R[root], C[cur] = C[root] + val;if(l == r)return cur;int mid = l + r >> 1;if(pos <= mid)L[cur] = add(L[root], l, mid, pos, val);else R[cur] = add(R[root], mid+1, r, pos, val);return cur;}int Find(int a, int b, int l, int r){if(l == r)return l;int mid = l + r >> 1;if(k <= C[L[b]] - C[L[a]])return Find(L[a], L[b], l, mid);k -= C[L[b]] - C[L[a]];return Find(R[a], R[b], mid+1, r);}void work(){T[0] = build(1, n);for(int i = 1; i <= dfs_clock; i ++)if(dfn[i])T[i] = add(T[i-1], 1, n, dfn[i], 1);for(int i = 1; i <= n; i ++){scanf("%d", &k);int l = In[i]-1, r = Out[i];if(C[T[r]] - C[T[l]] >= k)printf("%d\n", Find(T[l], T[r], 1, n));else printf("-1\n");}}
}int main(){scanf("%d", &n);for(int i = 1; i <= n; i ++)par[i] = i;for(int i = 1; i <= n; i ++)scanf("%s", s+1), Insert(i);BFS();DFS(root);Segtree::work();return 0;
}

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