网站 验证码 错误,如何制作自己的网址链接,网站先做前端还是后端,网站开发深圳传送门
#xff08;bzoj上不去我也很无奈啊#xff09;
题意#xff1a;维护一个字符串#xff0c;支持后面加字符串#xff0c;给定串询问出现次数。强制在线。
数据范围#xff1a;暴力跑不过
前置知识#xff1a;重量平衡树
众所周知#xff0c;平衡树都用了一…传送门
bzoj上不去我也很无奈啊
题意维护一个字符串支持后面加字符串给定串询问出现次数。强制在线。
数据范围暴力跑不过
前置知识重量平衡树
众所周知平衡树都用了一些策略保证平衡。
平衡有三种严格平衡均摊平衡期望平衡
其中严格平衡和期望平衡的当然不是很严格规模上是平衡的就可以了称为重量平衡树。该定义存疑
这种平衡树每次操作对树的结构影响很小最大的子树为log级别。这意味着你可以用它维护子树规模的集合。
也就是说可以在里面套一个动态开点线段树维护子树的所有权值。
常见的有替罪羊树和treap。
fhq好像也可以但好像没人用……
以维护子树集合为例替罪羊树每次重构的时候暴力更新集合。
treap就比较玄学旋转完后暴力更新期望是log的…… 回到这道题我们需要一个叫后缀平衡树的黑科技。
其实就是用重量平衡树维护后缀数组。
首先把所有串倒序注意是假装一来就是倒的显然不影响答案只是改成了在前面加。
把字符一个一个添加这样每添加一个只会多一个后缀只需要把这个后缀插入平衡树。
注意把添加的字符按顺序记下来这样得到的串是输入顺序但实际上是倒着存的。
现在的问题是如何快速比较两个后缀。
由于新来的后缀不在树上但之前的树上的后缀是可以快速比较的。
所以我们比较第一个字符如果一样就丢掉然后在树上比较。
显然可以O(logn)O(logn)O(logn)做。一个技巧对于每个节点维护(l,r)(l,r)(l,r),其权值为vallr2val\frac{lr}2val2lr,左儿子(l,val)(l,val)(l,val),右儿子(val,r)(val,r)(val,r),可以直接用权值O(1)O(1)O(1)比较因为深度是logloglog的精度可以保证。 重构时暴力更新。
询问的时候查比SSS小的后缀数再在后面加一个很大的字符再查一次两个减一下。由于深度是logloglog的所以直接暴力比较复杂度是O(∣S∣logn)O(|S|logn)O(∣S∣logn)
莫名觉得比后缀数组好写是怎么回事
#include iostream
#include cstdio
#include cstring
#include cctype
#include algorithm
//#include windows.h
#include cassert
#define MAXN 3600005
using namespace std;
const double alpha0.7;
char c[MAXN];
int ch[MAXN][2],siz[MAXN],rt,tot;
double L[MAXN],R[MAXN];
inline double val(const int x){return x?L[x]R[x]:-1e6;}
inline bool cmp(const int x,const int y){return c[x]c[y]||(c[x]c[y]val(x-1)val(y-1));}
int p[MAXN];
void dfs(int u)
{if (ch[u][0]) dfs(ch[u][0]);p[p[0]]u;if (ch[u][1]) dfs(ch[u][1]);
}
void build(int x,int l,int r,double vl,double vr)
{if (lr) return (void)(x0);int mid(lr)1;xp[mid];siz[x]r-l1;L[x]vl;R[x]vr;double vmid(vlvr)/2;build(ch[x][0],l,mid-1,vl,vmid);build(ch[x][1],mid1,r,vmid,vr);
}
void insert(int x,int i,double l,double r)
{if (!x) return (void)(siz[xi]1,L[x]l,R[x]r);if (siz[ch[x][0]]siz[x]*alpha||siz[ch[x][1]]siz[x]*alpha){p[0]0;dfs(x);build(x,1,p[0],l,r);}siz[x];L[x]l;R[x]r;double mid(lr)/2;if (cmp(i,x)) insert(ch[x][0],i,l,mid);else insert(ch[x][1],i,mid,r);
}
inline void insert(char i){c[tot]i;insert(rt,tot,0,1e6);}
int de;
int query(int x,char *s,int len)
{if (!x) return 0;int i;for (i0;s[i]c[x-i]ilen;i);if (ilen||s[i]c[x-i]) return query(ch[x][0],s,len);else{dex;int ressiz[ch[x][0]]1query(ch[x][1],s,len);return res;}
}
char s[MAXN];
int len,mask;
inline void read(int type)
{#ifndef ONLINE_JUDGE type0;#endifscanf(%s,s);lenstrlen(s);if (type){int tmask;for (int i0;ilen;i) swap(s[i],s[t(t*131i)%len]); }
}
int main()
{int q;scanf(%d,q);read(0);for (int i0;ilen;i) insert(s[i]);while (q--){read(0);if (s[0]A){read(1);for (int i0;ilen;i) insert(s[i]);}else{read(1);reverse(s,slen);int ans-query(rt,s,len);int tde;s[len]Z1;ansquery(rt,s,len1);printf(%d\n,ans);mask^ans;}}return 0;
}
