后缀平衡树 bzoj3682 Phorni
Description
Phorni 是一个音之妖精,喜欢在你的打字机上跳舞。
一天,阳光映射到刚刚淋浴过小雨的城市上时,Phorni 用魔法分裂出了许多个幻影,从 1 到 n 编号。
她的每一个幻影都站在打出的字符串的一个位置上,多个幻影可以站在同一个位置上。
每一个幻影代表的字符串即为从它站立位置开始的后缀,注意站立位置是从右往左数的。
让我们形式化地描述一下,若第 i 个幻影站在 Pi 上,那么它所代表的字符串就是 S[L-Pi+1…L],其中 L 是字符串 S 的长度。
每一次,她会选一段编号区间 [l..r],而编号在这个区间中的幻影中,字典序最小的一个将跳一支舞,若有多个幻影字典序相同,选编号最小的。
当然由于 Phorni 还会在打字机上跳动,所以有时字符串的前面会加入一个字符。
当然这个打字机是带加密功能的。
字典序的比较:
将两个字符串逐位比较,长度不足的向后补 0 ( 0 小于任何字符) 。直到比出大小或判定相等。
比如 “pho” > “ph” , “pb” > “pab” 。
下标从 1 开始,保证涉及到的所有字符都为小写字母。
Input
输入共 m + 3 行,
第一行为三个整数 n, m, len, type, 分别代表幻影个数,操作次数,初始字符串长度。type = 1 时表示所有的字符都经过了加密。
第二行为初始字符串 S 。
第三行,n 个数 Pi ,意义如题面所示。
接下来 m 行,每行表示一个操作。
1. I c 若 type = 0 表示在字符串前面加入第 c + 1 个小写字母,若 type = 1 则表示加入第 (c xor lastans) + 1 个小写字母,lastans 表示上一次的答案,初始为 0 。
2. C x pos 表示第 x 个幻影跳到了从右向左数 pos 的位置上。
3. Q l r 表示询问[l..r] 。
Output
对于每个询问操作输出一行,表示去跳舞的幻影编号。
Sample Input
3 3 5 0
horni
3 2 5
I 15
C 1 6
Q 1 3
Sample Output
3
HINT
样例解释
前2个操作后，三个幻影代表的后缀分别为phorni,ni,horni。
数据范围与约定
数据范围与约定
对于 100% 的数据, 1 ≤ n ≤ 500000, 1 ≤ m ≤ 800000, 1 ≤ Pi ≤ len ≤ 100000。
若 type = 0,保证 I 操作中 0 ≤ c ≤ 25;否则 0 ≤ c xor lastans ≤ 25 。
C 操作中 1 ≤ x ≤ n, 1 ≤ pos ≤ 当前字符串长度。
Q 操作中 1 ≤ l, r ≤ n,I 操作数量约占总操作数量的 1/5,C,Q 操作数量约各占总操作数量的 2/5。
Source
Shinrein祭 #1
后缀平衡树。
具体关于后缀平衡树可以去看陈立洁的论文。
这里大概说一下。
后缀平衡树就是建立一颗平衡树来维护一个字符串后缀的顺序。
对于离线，就非常简单了。先求出所以有后缀的排序，然后根据求出递后缀数组就可以轻易的求出后缀平衡树来。
对于在线，我们在字符串的开头加进去字符ch。我们就会发现它产生了一个新的后缀 chS。然后根据后缀的排序加到后缀平衡树里就行了。
#include <bits/stdc++.h>
#define N 500010
#define ll long long
using namespace std;
inline int read()
{
int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
int n, m, len, type, lastans;
int ch[N][2], h[N], c[N], cnt, rt;
ll rk[N];
void rebuild(int& rt,ll l,ll r)
{
if(!rt) return;
rk[rt] = l + r;
ll mid = (l + r) >> 1;
rebuild(ch[rt][0], l, mid);
rebuild(ch[rt][1], mid, r);
}
void rotate(int& rt,int d,ll l,ll r)
{
int k = ch[rt][d ^ 1];
ch[rt][d ^ 1] = ch[k][d];
ch[k][d] = rt;
rt = k;
rebuild(rt,l,r);
}
int cmp(int x,int y)
{
return c[x] < c[y] || (c[x] == c[y] && rk[x - 1] < rk[y - 1]);
}
void insert(int& rt,ll l,ll r)
{
ll mid = (l + r) >> 1;
if(!rt) {rt = cnt; rk[rt] = l + r; return;}
if(cmp(cnt,rt)) {insert(ch[rt][0], l, mid); if(h[ch[rt][0]] > h[rt]) rotate(rt, 1, l, r);}
else {insert(ch[rt][1], mid, r); if(h[ch[rt][1]]> h[rt]) rotate(rt, 0, l, r);}
}
void insert(int v)
{
c[++ cnt] = v;
h[cnt] = rand() * rand();
insert(rt, 1, 1ll << 61);
}
int minv[N*3],p[N];
void build(int o,int l,int r)
{
if(l == r) p[l] = read(), minv[o] = l;
else
{
int mid = (l + r) >> 1,lc = o << 1, rc = lc | 1;
build(lc, l, mid);
build(rc, mid + 1, r);
minv[o] = rk[ p[ minv[lc] ] ] <= rk[ p[ minv[rc] ] ]? minv[lc]: minv[rc];
}
}
void update(int rt,int l,int r,int dd)
{
if(l == r) return;
int lc = rt << 1, rc = rt << 1 | 1;
int mid = (l + r) >> 1;
if(dd <= mid) update(lc, l, mid, dd);
else update(rc, mid + 1, r, dd);
minv[rt] = rk[p[minv[lc]]] <= rk[p[minv[rc]]]? minv[lc]: minv[rc];
}
int query(int rt,int l,int r,int ql,int qr)
{
if(ql <= l && r <= qr) return minv[rt];
int lc = rt << 1, rc = rt << 1 |1;
int mid = (l + r) >> 1;
if(qr <= mid) return query(lc, l, mid, ql, qr); if(ql > mid) return query(rc, mid + 1, r, ql, qr);
int v1 = query(lc,l,mid,ql,qr), v2 = query(rc,mid + 1,r,ql,qr);
return rk[p[v1]] <= rk[p[v2]]?v1:v2;
}
char s[N],cmd[5];
int main()
{
n = read();
m = read();
len = read();
type = read();
scanf("%s", s);
for(int i = 1; i <= len; i ++)
insert(s[len - i] - 'a');
build(1, 1, n);
while(m --)
{
scanf("%s",cmd);
if(!type) lastans = 0;
if(cmd[0] == 'I') insert(read() ^ lastans), len ++;
else
if(cmd[0] == 'C')
{
int x = read();
p[x] = read();
update(1, 1, n, x);
}
else
{
int x = read(), y = read();
printf("%d\n",lastans = query(1,1,n,x,y));
}
}
return 0;
}
投递字节跳动等公司10个岗位 >
阿里巴巴一面146人在聊