2016hdu多校赛第5场(hdu5790) 主席树(Persistent Segment Tree)

时间:2021-11-12 00:18:39

题意

给你N个字符串,问你第l个到第r个字符串中有多少个不同前缀。强制在线做,所以没法用树状数组来做。

主席树

也就是Persistent Segment Tree ,可持久化线段树。

一般来讲线段树更新之后不会使用历史版本的线段树的信息,但是有些问题里面需要。

可持久化线段树的做法是,新建一logn个节点,相当于一条链,线段树原本更新时是将这条链上的值更新,而主席树是新建一条链,其他部分连接原始的线段树,这样既完成了更新操作,又能保留历史版本。

做法

这个做法同在线查询一个区间内不同数的个数,T[i]这个树维护从i开始[i,r]不同数的个数,用一个数组bel维护出现那个前缀最后的位置,从T[i]转移到T[i-1]就是将当前所有前缀在后面出现过的话就消除影响,并且在当前位置加上当前字符串个数(也就是前缀个数)

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<iostream>

using namespace std;

namespace Trie {
const int SIZE = 100005;
int node[SIZE][26];
int tot, bel[SIZE];
void Insert(string& str) {
int cur = 0;
for(int i = 0; i < str.size(); i++) {
int p = str[i] - 'a';
if(node[cur][p] == 0) {
tot++;
node[cur][p] = tot; //指向新节点
memset(node[tot], 0, sizeof(node[tot]));
}
cur = node[cur][p];
bel[cur] = 0;
}
}
void init() {
tot = 0;
memset(node[0], 0, sizeof(node[0]));
}
// cur <- node[cur][p]
}

namespace PST {

const int MAXN = 100005;
const int M = MAXN * 40;
int tot;
int n;
int T[MAXN],lson[M],rson[M],c[M];
void init(int _n) {
tot = 0;
n = _n;
}
int build(int l,int r)
{
int root = tot++;
c[root] = 0;
if(l != r)
{
int mid = (l+r)>>1;
lson[root] = build(l,mid);
rson[root] = build(mid+1,r);
}
return root;
}
int update(int root,int pos,int val)
{
int newroot = tot++, tmp = newroot;
c[newroot] = c[root] + val;
int l = 1, r = n;
while(l < r)
{
int mid = (l+r)>>1;
if(pos <= mid)
{
lson[newroot] = tot++; rson[newroot] = rson[root];
newroot = lson[newroot]; root = lson[root];
r = mid;
}
else
{
rson[newroot] = tot++; lson[newroot] = lson[root];
newroot = rson[newroot]; root = rson[root];
l = mid+1;
}
c[newroot] = c[root] + val;
}
return tmp;
}
int query(int root,int pos)
{
int ret = 0;
int l = 1, r = n;
while(pos < r)
{
int mid = (l+r)>>1;
if(pos <= mid)
{
r = mid;
root = lson[root];
}
else
{
ret += c[lson[root]];
root = rson[root];
l = mid+1;
}
}
return ret + c[root];
}
}

string s[PST::MAXN];

int main() {
int N;
while(~scanf("%d",&N)) {
PST::init(N);
Trie::init();
for(int i = 1; i <= N; i++) {
cin >> s[i];
Trie::Insert(s[i]);
}
PST::T[N+1] = PST::build(1, N);
for(int i = N; i >= 1; i--) {
int cur = 0;
PST::T[i] = PST::T[i+1];
for(int j = 0; j < s[i].size(); j++) {
int p = s[i][j] - 'a';
cur = Trie::node[cur][p];
if(Trie::bel[cur]) {
//消除前面出现过的前缀的影响
PST::T[i] = PST::update(PST::T[i], Trie::bel[cur], -1);
}
Trie::bel[cur] = i;//通过字典树分配ID,记录这个前缀出现的最后一个位置
}

PST::T[i] = PST::update(PST::T[i],i,s[i].size());
}
int Q;
scanf("%d",&Q);
int Z = 0;
while(Q--) {
int l, r;
scanf("%d%d",&l,&r);
l += Z; l %= N;
r += Z; r %= N;
if(l > r) swap(l, r);
Z = PST::query(PST::T[l+1],r+1);
printf("%d\n",Z);
}
}
}