今天是第二天集训。（其实已经是第三天了，只是昨天并没有机会来写总结，现在补上）
上午大家心情都很愉快，因为老师讲了splay树和ac自动机。
但到了下午，我们的教练竟然跑出去耍了（excuse me？），害的我们在一些不懂的地方冥思苦想浪费时间，效率极其低下，所以说只做了点模板题，以后这方面的知识还需要多多练习0.0
1.ac自动机
这东西是kmp的升级版本，由一个模式串升级到了多个模式串，效率依然高。
只要掌握了kmp，ac自动机一般不会有问题。哦，当然你也必须会trie树，这是自动机的基础
首先，和kmp一样，构造fail数组，也就是next数组。注意：这个fail数组不止能够跳到自己的最大相同前缀上，还能跳到别的串。
有了fail数组，就可以匹配了，过程也和kmp类似，只不过加一些处理令得模式串之间可以互相到达
所以，以上我说的全是废话[滑稽]。
话不多说，上代码（标准模板）
CODE： HDU2222
#include<bits/stdc++.h>
using namespace std;
#define N 10005
int tr[N*][],ls[N*],n,tot,f[N*],val[N*],ans;
char s[],ch[]; void adtr(){
int i=,x=;
while(ch[i]){
int k=ch[i]-'a';
if(!tr[x][k])tr[x][k]=++tot;
x=tr[x][k];i++;
}
val[x]++;
} void getfail(){
queue<int>q;
int u,v,rt;
for(int i=;i<;i++)if(tr[][i])q.push(tr[][i]),f[tr[][i]]=ls[tr[][i]]=;
while(!q.empty()){
rt=q.front();q.pop();
for(int i=;i<;i++){
int u=tr[rt][i];
if(!u){tr[rt][u]=tr[f[rt]][u];continue;}
q.push(u);
v=f[rt];
while(v&&!tr[v][i])v=f[v];
f[u]=tr[v][i];
if(val[f[u]])ls[u]=f[u];
else ls[u]=ls[f[u]];
}
}
} void make(int x){
if(!x)return;
if(val[x])ans+=val[x],val[x]=;
make(ls[x]);
} void ac(){
int x=;
for(int i=;s[i];i++){
int k=s[i]-'a';
//while(x&&!tr[x][k])x=f[x];
/*上一句可以省略的原因是 getfail()函数中的这一句 :
if(!u){tr[rt][u]=tr[f[rt]][u];continue;}
已经通过迭代求出了最近的有k的串 */
x=tr[x][k];
if(val[x])make(x);
else if(ls[x])make(ls[x]);
}
} int main(){
int T;cin>>T;
while(T--){
memset(val,,sizeof(val));
memset(tr,,sizeof(tr));
ans=tot=;scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%s",ch),adtr();
getfail();scanf("%s",s);ac();
printf("%d\n",ans);
}
}
点击查看完整版。。
2.ac自动机+dp
就是字符串禁用一类的题
正常的字符串禁用只有一个串禁用，求长度为n的不含禁用串的字符串由多少个
但由于学了ac自动机，我们可以干出一个多串禁用版本，非常high，如果串的长度n太大，dp是还需要使用矩阵快速幂，high到爆！！可惜我不会~
这东西暂时不管，之后再来慢慢学。
3.splay树
伸展树，区间王，线段树能做的区间题它都能做（据说是这样），线段树不能做的它也可以做
原因：线段树是静态树，不能插入、删除和区间倒置、平移之类的，如果出现上述操作，必定会导致重新建一棵线段树，这时就可以用splay动态树。
splay如何动态维护区间？
和线段树不同，splay树上的节点都是只表示线段上的一个点，一般是区间中点，但这并不妨碍它维护区间信息。在需要进行动态操作时，我们把和操作有关的点给旋转至根节点，再在根节点上进行操作，这样就不会对原树造成太大影响。
值得一说的是，splay树是一棵二叉平衡树，也就是说，对于任何一个节点，它都满足一个式子：lson<fa<rson ，这样就可以通过某种手段表示一个区间。
把某个节点旋转至根有一些特定的操作，称splay。而在splay树中，几乎每个操作都和splay有关，splay操作中有个rotate操作，表示把某个点和它的父亲节点交换位置而不影响原树的性质（平衡），这就有些屌。
详细图解参考 http://www.cnblogs.com/Paul-Guderian/p/6637045.html
吐槽一下：水友做的总是比我详细得多[滑稽]，劳资根本就不会画图
另外呢，推荐一个pdf，有助于详细得理解伸展树
https://wenku.baidu.com/view/7f0ff024ccbff121dd3683ac.html
一道题 NOI2005 维修数列
这个题几乎包含了所有伸展树的操作，打完了它你会有一种莫名的成就感。。（至少我是这样）
具体参考黄学长 http://hzwer.com/2841.html
自己暂时打不出来，在黄学长的代码上加了注释
CODE：
#include<bits/stdc++.h>
#define N 1000005
#define inf 1000000000
using namespace std;
int v[N],sum[N],lx[N],mx[N],id[N],size[N],rx[N],fa[N],a[N],n,m,rt,cnt,tag[N],rev[N],c[N][];
queue<int>q;
int read(){
char c;int f=,x=;c=getchar();
while(c>''||c<''){if(c=='-')f=-;c=getchar();}
while(c<=''&&c>='')x=x*+c-'',c=getchar();
return f*x;
} void update(int x)//上传信息
{
int l=c[x][],r=c[x][];
sum[x]=sum[l]+sum[r]+v[x];
size[x]=size[l]+size[r]+;
mx[x]=max(mx[l],mx[r]);
mx[x]=max(mx[x],rx[l]+v[x]+lx[r]);
lx[x]=max(lx[l],sum[l]+v[x]+lx[r]);
rx[x]=max(rx[r],sum[r]+v[x]+rx[l]);
} void pushdown(int x)//下放lazy标记
{
int l=c[x][],r=c[x][];
if(tag[x])
{
rev[x]=tag[x]=;
if(l)tag[l]=,v[l]=v[x],sum[l]=v[x]*size[l];
if(r)tag[r]=,v[r]=v[x],sum[r]=v[x]*size[r];
if(v[x]>=)
{
if(l)lx[l]=rx[l]=mx[l]=sum[l];
if(r)lx[r]=rx[r]=mx[r]=sum[r];
}
else
{
if(l)lx[l]=rx[l]=,mx[l]=v[x];
if(r)lx[r]=rx[r]=,mx[r]=v[x];
}
}
if(rev[x])
{
rev[x]^=;rev[l]^=;rev[r]^=;
swap(lx[l],rx[l]);swap(lx[r],rx[r]);
swap(c[l][],c[l][]);swap(c[r][],c[r][]);
}
} void rotate(int x,int &k){//旋转操作
int y=fa[x],z=fa[y],l,r;
if(c[y][]==x)l=;else l=;r=l^;
if(y==k)k=x;
else c[z][c[z][]==y]=x;
fa[x]=z;fa[c[x][r]]=y;fa[y]=x;
c[y][l]=c[x][r];c[x][r]=y;
update(y),update(x);
} void splay(int x,int &k){//把某个节点转至根
while(x!=k){
int y=fa[x],z=fa[y];
if(y!=k){
if((c[z][]==y)^(c[y][]==x))rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
} int find(int x,int rk){//查找序列内第k个数的节点编号并把它调整至根
pushdown(x);
int l=c[x][],r=c[x][];
if(size[l]+==rk)return x;
if(size[l]>=rk)return find(l,rk);
return find(r,rk-size[l]-);
} int split(int k,int tot){//分离出某个子树(一段区间)，便于操作
int x=find(rt,k),y=find(rt,k+tot+);
splay(x,rt);splay(y,c[x][]);
return c[y][];
} void query(int k,int tot){//查询，题目特殊
int x=split(k,tot);
printf("%d\n",sum[x]);
} void modify(int k,int tot,int val){//把某一区间所有数都修改为val
int x=split(k,tot),y=fa[x];
v[x]=val;tag[x]=;sum[x]=size[x]*val;
if(val>=)lx[x]=rx[x]=mx[x]=sum[x];
else lx[x]=rx[x]=,mx[x]=val;
update(y);update(fa[y]);
} void rever(int k,int tot){//倒置某一区间
int x=split(k,tot),y=fa[x];
if(!tag[x]){
rev[x]^=;
swap(c[x][],c[x][]);
swap(lx[x],rx[x]);
update(y);update(fa[y]);
}
} void rec(int x){//删除子树空间，节省空间
if(!x)return;
int l=c[x][],r=c[x][];
rec(l);rec(r);q.push(x);
fa[x]=tag[x]=rev[x]=c[x][]=c[x][]=;
} void erase(int k,int tot){//删除某一区间
int x=split(k,tot),y=fa[x];
rec(x);c[y][]=;
update(y);update(fa[y]);
} void build(int l,int r,int f){//建立树
if(l>r)return;
int mid=(l+r)>>,now=id[mid],last=id[f];
if(l==r){
sum[now]=a[l];size[now]=;
tag[now]=rev[now]=;
if(a[l]>=)lx[now]=rx[now]=mx[now]=a[l];
else lx[now]=rx[now]=,mx[now]=a[l];
}
else build(l,mid-,mid),build(mid+,r,mid);
v[now]=a[mid];fa[now]=last;update(now);
c[last][mid>=f]=now;
} void insert(int k,int tot){//插入新的一段区间
for(int i=;i<=tot;i++)a[i]=read();
for(int i=;i<=tot;i++)
if(!q.empty())id[i]=q.front(),q.pop();//这里使用了以前被删除的区间节点标号
else id[i]=++cnt;//若被删除的区间节点不够，增加新的标号值
build(,tot,);int z=id[(+tot)>>];//对于新区间，建立一棵树，把这棵树加到总树中
int x=find(rt,k+),y=find(rt,k+);
splay(x,rt);splay(y,c[x][]);
fa[z]=y;c[y][]=z;
update(y);update(x);
} int main(){
n=read();m=read();
mx[]=a[]=a[n+]=-inf;
for(int i=;i<=n;i++)a[i+]=read();
for(int i=;i<=n+;i++)id[i]=i;
build(,n+,);
rt=(n+)>>;cnt=n+;
int k,tot,val;
char ch[];
while(m--){
scanf("%s",ch);
if(ch[]!='M'||ch[]!='X')k=read(),tot=read();
if(ch[]=='I')insert(k,tot);
if(ch[]=='D')erase(k,tot);
if(ch[]=='M')
{
if(ch[]=='X')printf("%d\n",mx[rt]);
else val=read(),modify(k,tot,val);
}
if(ch[]=='R')rever(k,tot);
if(ch[]=='G')query(k,tot);
} return ;
}
下午老师出去玩了，我们很多没懂的地方想问也没办法，最后几个人一起讨论了一晚上，真的是，shit。还有，有些上信息课的傻屌把劳资主机搞烂了，还好我机智的把所有资料转移到了百度云，不然估计是要暴走了。
晚上发生了一些搞笑的事，一哥们儿晚上吃完饭打游戏，没关后门，被hy逮住了。更扯淡的是，那时候我在看小说，听到他被老师训斥的声音才发觉有人来了。也就是说，他为我挡了一刀。。
好了，第二天就这样了。