今天是第二天集训。（其实已经是第三天了，只是昨天并没有机会来写总结，现在补上）
上午大家心情都很愉快，因为老师讲了splay树和ac自动机。
但到了下午，我们的教练竟然跑出去耍了（excuse me？），害的我们在一些不懂的地方冥思苦想浪费时间，效率极其低下，所以说只做了点模板题，以后这方面的知识还需要多多练习0.0
1.ac自动机
这东西是kmp的升级版本，由一个模式串升级到了多个模式串，效率依然高。
只要掌握了kmp，ac自动机一般不会有问题。哦，当然你也必须会trie树，这是自动机的基础
首先，和kmp一样，构造fail数组，也就是next数组。注意：这个fail数组不止能够跳到自己的最大相同前缀上，还能跳到别的串。
有了fail数组，就可以匹配了，过程也和kmp类似，只不过加一些处理令得模式串之间可以互相到达
所以，以上我说的全是废话[滑稽]。
话不多说，上代码（标准模板）
CODE： HDU2222
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 10005 4 int tr[N*50][26],ls[N*50],n,tot,f[N*50],val[N*50],ans; 5 char s[1000005],ch[55]; 6 7 void adtr(){ 8 int i=0,x=0; 9 while(ch[i]){ 10 int k=ch[i]-'a'; 11 if(!tr[x][k])tr[x][k]=++tot; 12 x=tr[x][k];i++; 13 } 14 val[x]++; 15 } 16 17 void getfail(){ 18 queue<int>q; 19 int u,v,rt; 20 for(int i=0;i<26;i++)if(tr[0][i])q.push(tr[0][i]),f[tr[0][i]]=ls[tr[0][i]]=0; 21 while(!q.empty()){ 22 rt=q.front();q.pop(); 23 for(int i=0;i<26;i++){ 24 int u=tr[rt][i]; 25 if(!u){tr[rt][u]=tr[f[rt]][u];continue;} 26 q.push(u); 27 v=f[rt]; 28 while(v&&!tr[v][i])v=f[v]; 29 f[u]=tr[v][i]; 30 if(val[f[u]])ls[u]=f[u]; 31 else ls[u]=ls[f[u]]; 32 } 33 } 34 } 35 36 void make(int x){ 37 if(!x)return; 38 if(val[x])ans+=val[x],val[x]=0; 39 make(ls[x]); 40 } 41 42 void ac(){ 43 int x=0; 44 for(int i=0;s[i];i++){ 45 int k=s[i]-'a'; 46 //while(x&&!tr[x][k])x=f[x]; 47 /*上一句可以省略的原因是 getfail()函数中的这一句 : 48 if(!u){tr[rt][u]=tr[f[rt]][u];continue;} 49 已经通过迭代求出了最近的有k的串 */ 50 x=tr[x][k]; 51 if(val[x])make(x); 52 else if(ls[x])make(ls[x]); 53 } 54 } 55 56 int main(){ 57 int T;cin>>T; 58 while(T--){ 59 memset(val,0,sizeof(val)); 60 memset(tr,0,sizeof(tr)); 61 ans=tot=0;scanf("%d",&n); 62 for(int i=1;i<=n;i++)scanf("%s",ch),adtr(); 63 getfail();scanf("%s",s);ac(); 64 printf("%d ",ans); 65 } 66 }
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：
1 #include<bits/stdc++.h> 2 #define N 1000005 3 #define inf 1000000000 4 using namespace std; 5 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][2]; 6 queue<int>q; 7 int read(){ 8 char c;int f=1,x=0;c=getchar(); 9 while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} 10 while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar(); 11 return f*x; 12 } 13 14 void update(int x)//上传信息 15 { 16 int l=c[x][0],r=c[x][1]; 17 sum[x]=sum[l]+sum[r]+v[x]; 18 size[x]=size[l]+size[r]+1; 19 mx[x]=max(mx[l],mx[r]); 20 mx[x]=max(mx[x],rx[l]+v[x]+lx[r]); 21 lx[x]=max(lx[l],sum[l]+v[x]+lx[r]); 22 rx[x]=max(rx[r],sum[r]+v[x]+rx[l]); 23 } 24 25 void pushdown(int x)//下放lazy标记 26 { 27 int l=c[x][0],r=c[x][1]; 28 if(tag[x]) 29 { 30 rev[x]=tag[x]=0; 31 if(l)tag[l]=1,v[l]=v[x],sum[l]=v[x]*size[l]; 32 if(r)tag[r]=1,v[r]=v[x],sum[r]=v[x]*size[r]; 33 if(v[x]>=0) 34 { 35 if(l)lx[l]=rx[l]=mx[l]=sum[l]; 36 if(r)lx[r]=rx[r]=mx[r]=sum[r]; 37 } 38 else 39 { 40 if(l)lx[l]=rx[l]=0,mx[l]=v[x]; 41 if(r)lx[r]=rx[r]=0,mx[r]=v[x]; 42 } 43 } 44 if(rev[x]) 45 { 46 rev[x]^=1;rev[l]^=1;rev[r]^=1; 47 swap(lx[l],rx[l]);swap(lx[r],rx[r]); 48 swap(c[l][0],c[l][1]);swap(c[r][0],c[r][1]); 49 } 50 } 51 52 void rotate(int x,int &k){//旋转操作 53 int y=fa[x],z=fa[y],l,r; 54 if(c[y][0]==x)l=0;else l=1;r=l^1; 55 if(y==k)k=x; 56 else c[z][c[z][1]==y]=x; 57 fa[x]=z;fa[c[x][r]]=y;fa[y]=x; 58 c[y][l]=c[x][r];c[x][r]=y; 59 update(y),update(x); 60 } 61 62 void splay(int x,int &k){//把某个节点转至根 63 while(x!=k){ 64 int y=fa[x],z=fa[y]; 65 if(y!=k){ 66 if((c[z][0]==y)^(c[y][0]==x))rotate(x,k); 67 else rotate(y,k); 68 } 69 rotate(x,k); 70 } 71 } 72 73 int find(int x,int rk){//查找序列内第k个数的节点编号并把它调整至根 74 pushdown(x); 75 int l=c[x][0],r=c[x][1]; 76 if(size[l]+1==rk)return x; 77 if(size[l]>=rk)return find(l,rk); 78 return find(r,rk-size[l]-1); 79 } 80 81 int split(int k,int tot){//分离出某个子树(一段区间)，便于操作 82 int x=find(rt,k),y=find(rt,k+tot+1); 83 splay(x,rt);splay(y,c[x][1]); 84 return c[y][0]; 85 } 86 87 void query(int k,int tot){//查询，题目特殊 88 int x=split(k,tot); 89 printf("%d ",sum[x]); 90 } 91 92 void modify(int k,int tot,int val){//把某一区间所有数都修改为val 93 int x=split(k,tot),y=fa[x]; 94 v[x]=val;tag[x]=1;sum[x]=size[x]*val; 95 if(val>=0)lx[x]=rx[x]=mx[x]=sum[x]; 96 else lx[x]=rx[x]=0,mx[x]=val; 97 update(y);update(fa[y]); 98 } 99 100 void rever(int k,int tot){//倒置某一区间 101 int x=split(k,tot),y=fa[x]; 102 if(!tag[x]){ 103 rev[x]^=1; 104 swap(c[x][0],c[x][1]); 105 swap(lx[x],rx[x]); 106 update(y);update(fa[y]); 107 } 108 } 109 110 void rec(int x){//删除子树空间，节省空间 111 if(!x)return; 112 int l=c[x][0],r=c[x][1]; 113 rec(l);rec(r);q.push(x); 114 fa[x]=tag[x]=rev[x]=c[x][0]=c[x][1]=0; 115 } 116 117 void erase(int k,int tot){//删除某一区间 118 int x=split(k,tot),y=fa[x]; 119 rec(x);c[y][0]=0; 120 update(y);update(fa[y]); 121 } 122 123 void build(int l,int r,int f){//建立树 124 if(l>r)return; 125 int mid=(l+r)>>1,now=id[mid],last=id[f]; 126 if(l==r){ 127 sum[now]=a[l];size[now]=1; 128 tag[now]=rev[now]=0; 129 if(a[l]>=0)lx[now]=rx[now]=mx[now]=a[l]; 130 else lx[now]=rx[now]=0,mx[now]=a[l]; 131 } 132 else build(l,mid-1,mid),build(mid+1,r,mid); 133 v[now]=a[mid];fa[now]=last;update(now); 134 c[last][mid>=f]=now; 135 } 136 137 void insert(int k,int tot){//插入新的一段区间 138 for(int i=1;i<=tot;i++)a[i]=read(); 139 for(int i=1;i<=tot;i++) 140 if(!q.empty())id[i]=q.front(),q.pop();//这里使用了以前被删除的区间节点标号 141 else id[i]=++cnt;//若被删除的区间节点不够，增加新的标号值 142 build(1,tot,0);int z=id[(1+tot)>>1];//对于新区间，建立一棵树，把这棵树加到总树中 143 int x=find(rt,k+1),y=find(rt,k+2); 144 splay(x,rt);splay(y,c[x][1]); 145 fa[z]=y;c[y][0]=z; 146 update(y);update(x); 147 } 148 149 int main(){ 150 n=read();m=read(); 151 mx[0]=a[1]=a[n+2]=-inf; 152 for(int i=1;i<=n;i++)a[i+1]=read(); 153 for(int i=1;i<=n+2;i++)id[i]=i; 154 build(1,n+2,0); 155 rt=(n+3)>>1;cnt=n+2; 156 int k,tot,val; 157 char ch[10]; 158 while(m--){ 159 scanf("%s",ch); 160 if(ch[0]!='M'||ch[2]!='X')k=read(),tot=read(); 161 if(ch[0]=='I')insert(k,tot); 162 if(ch[0]=='D')erase(k,tot); 163 if(ch[0]=='M') 164 { 165 if(ch[2]=='X')printf("%d ",mx[rt]); 166 else val=read(),modify(k,tot,val); 167 } 168 if(ch[0]=='R')rever(k,tot); 169 if(ch[0]=='G')query(k,tot); 170 } 171 172 return 0; 173 }
下午老师出去玩了，我们很多没懂的地方想问也没办法，最后几个人一起讨论了一晚上，真的是，shit。还有，有些上信息课的傻屌把劳资主机搞烂了，还好我机智的把所有资料转移到了百度云，不然估计是要暴走了。
晚上发生了一些搞笑的事，一哥们儿晚上吃完饭打游戏，没关后门，被hy逮住了。更扯淡的是，那时候我在看小说，听到他被老师训斥的声音才发觉有人来了。也就是说，他为我挡了一刀。。
好了，第二天就这样了。