4.5 平衡树
4.5.1 253. 普通平衡树
代码：
#include<bits/stdc++.h> using namespace std; const int N=100010,INF=1e9; int n; struct Node { int l,r; int key,val; int cnt,sz; }tr[N]; int root,idx; void pushup(int p) { tr[p].sz=tr[tr[p].l].sz+tr[tr[p].r].sz+tr[p].cnt; } int get_node(int key) //创建新的节点 { tr[++idx].key=key; tr[idx].val=rand(); tr[idx].cnt=tr[idx].sz=1; return idx; } void zig(int &p) // 右旋 { int q=tr[p].l; tr[p].l=tr[q].r,tr[q].r=p,p=q; pushup(tr[p].r),pushup(p); } void zag(int &p) // 左旋 { int q=tr[p].r; tr[p].r=tr[q].l,tr[q].l=p,p=q; pushup(tr[p].l),pushup(p); } void build() { get_node(-INF),get_node(INF); root=1,tr[1].r=2; pushup(root); if(tr[1].val<tr[2].val) zag(root); } void my_insert(int &p,int key) { if(!p) p=get_node(key); else if(tr[p].key==key) tr[p].cnt++; else if(tr[p].key>key) { my_insert(tr[p].l,key); if(tr[tr[p].l].val>tr[p].val) zig(p); } else { my_insert(tr[p].r,key); if(tr[tr[p].r].val>tr[p].val) zag(p); } pushup(p); } void my_remove(int &p,int key) { if(!p) return; if(tr[p].key==key) { if(tr[p].cnt>1) tr[p].cnt--; else if(tr[p].l||tr[p].r) { if(!tr[p].r||tr[tr[p].l].val>tr[tr[p].r].val) { zig(p); my_remove(tr[p].r,key); } else { zag(p); my_remove(tr[p].l,key); } } else p=0; } else if(tr[p].key>key) my_remove(tr[p].l,key); else my_remove(tr[p].r,key); pushup(p); } int get_rank_by_key(int p,int key) // 通过数值找排名 { if(!p) return 0; // 本题中不会发生此情况 if(tr[p].key==key) return tr[tr[p].l].sz+1; if(tr[p].key>key) return get_rank_by_key(tr[p].l,key); return tr[tr[p].l].sz+tr[p].cnt+get_rank_by_key(tr[p].r,key); } int get_key_by_rank(int p,int rk) // 通过排名找数值rk:rank { if(!p) return INF; // 本题中不会发生此情况 if(tr[tr[p].l].sz>=rk) return get_key_by_rank(tr[p].l,rk); if(tr[tr[p].l].sz+tr[p].cnt>=rk) return tr[p].key; return get_key_by_rank(tr[p].r,rk-tr[tr[p].l].sz-tr[p].cnt); } int get_prev(int p,int key) // 找到严格小于key的最大数 { if(!p) return -INF; if(tr[p].key>=key) return get_prev(tr[p].l,key); return max(tr[p].key,get_prev(tr[p].r,key)); } int get_next(int p,int key) // 找到严格大于key的最小数 { if(!p) return INF; if(tr[p].key<=key) return get_next(tr[p].r,key); return min(tr[p].key,get_next(tr[p].l,key)); } int main() { build(); cin>>n; while(n--) { int op,x; cin>>op>>x; if(op==1) my_insert(root,x); else if(op==2) my_remove(root,x); else if(op==3) cout<<get_rank_by_key(root,x)-1<<endl; else if(op==4) cout<<get_key_by_rank(root,x+1)<<endl; else if(op==5) cout<<get_prev(root,x)<<endl; else cout<<get_next(root,x)<<endl; } return 0; }
4.5.2 265. 营业额统计
代码：
/* Treep #include<bits/stdc++.h> using namespace std; const int N=1000010,INF=1e9; int n; struct Node { int l,r; int key,val; int cnt,sz; }tr[N]; int root,idx; void pushup(int p) { tr[p].sz=tr[tr[p].l].sz+tr[tr[p].r].sz+tr[p].cnt; } int get_node(int key) //创建新的节点 { tr[++idx].key=key; tr[idx].val=rand(); tr[idx].cnt=tr[idx].sz=1; return idx; } void zig(int &p) // 右旋 { int q=tr[p].l; tr[p].l=tr[q].r,tr[q].r=p,p=q; pushup(tr[p].r),pushup(p); } void zag(int &p) // 左旋 { int q=tr[p].r; tr[p].r=tr[q].l,tr[q].l=p,p=q; pushup(tr[p].l),pushup(p); } void build() { get_node(-INF),get_node(INF); root=1,tr[1].r=2; pushup(root); if(tr[1].val<tr[2].val) zag(root); } void my_insert(int &p,int key) { if(!p) p=get_node(key); else if(tr[p].key==key) tr[p].cnt++; else if(tr[p].key>key) { my_insert(tr[p].l,key); if(tr[tr[p].l].val>tr[p].val) zig(p); } else { my_insert(tr[p].r,key); if(tr[tr[p].r].val>tr[p].val) zag(p); } pushup(p); } int get_prev(int p,int key) // 找到严格小于等于key的最大数 { if(!p) return -INF; if(tr[p].key>key) return get_prev(tr[p].l,key); return max(tr[p].key,get_prev(tr[p].r,key)); } int get_next(int p,int key) // 找到严格大于等于key的最小数 { if(!p) return INF; if(tr[p].key<key) return get_next(tr[p].r,key); return min(tr[p].key,get_next(tr[p].l,key)); } int main() { ios::sync_with_stdio(0); build(); cin>>n; int res=0; for(int i=1;i<=n;i++) { int key; cin>>key; if(i==1) res+=key; else { int aj1=get_prev(root,key),aj2=get_next(root,key); if(aj1==-INF) aj1=INF; int aj=min(abs(aj1-key),abs(aj2-key)); res+=aj; } my_insert(root,key); } cout<<res<<endl; return 0; } */ //STL set lower_bound >= #include<bits/stdc++.h> using namespace std; const int INF=0x3f3f3f3f; int n; set<int> st; int main() { cin>>n; int res=0; set<int>::iterator it; st.insert(-INF); st.insert(INF); for(int i=0;i<n;i++) { int x; cin>>x; if(i==0) res+=x; else { int aj1,aj2; it=st.lower_bound(x); aj1=*it; aj2=*(--it); res+=min(aj1-x,x-aj2); } st.insert(x); } cout<<res<<endl; return 0; }
4.6 AC自动机
4.6.1 1282. 搜索关键词
代码：
#include<bits/stdc++.h> using namespace std; const int N=10010,S=55,M=1000010; int n; int tr[N*S][26],cnt[N*S],idx; char str[M]; int q[N*S],ne[N*S]; void my_insert() //trie中插入节点 { int p=0; for(int i=0;str[i];i++) { int t=str[i]-'a'; if(!tr[p][t]) tr[p][t]=++idx; p=tr[p][t]; } cnt[p]++; } void build() { queue<int> q; for(int i=0;i<26;i++) { if(tr[0][i]) q.push(tr[0][i]); } while(q.size()) { int t=q.front(); q.pop(); for(int i=0;i<26;i++) { int p=tr[t][i]; if(!p) tr[t][i]=tr[ne[t]][i]; else { ne[p]=tr[ne[t]][i]; q.push(p); } } } } int main() { int T; cin>>T; while(T--) { memset(tr,0,sizeof tr); memset(cnt,0,sizeof cnt); memset(ne,0,sizeof ne); idx=0; cin>>n; for(int i=0;i<n;i++) { cin>>str; my_insert(); } build(); cin>>str; int res=0; for(int i=0,j=0;str[i];i++) { int t=str[i]-'a'; j=tr[j][t]; int p=j; while(p) { res+=cnt[p]; cnt[p]=0; p=ne[p]; } } cout<<res<<endl; } return 0; }
4.6.2 1285. 单词
代码：
#include<bits/stdc++.h> using namespace std; const int N=1000010; int n; int tr[N][26],f[N],idx; int ne[N]; char str[N]; int id[210]; vector<int> seq; void my_insert(int x) { int p=0; for(int i=0;str[i];i++) { int t=str[i]-'a'; if(!tr[p][t]) tr[p][t]=++idx; p=tr[p][t]; f[p]++; } id[x]=p; } void build() { queue<int> q; for(int i=0;i<26;i++) { if(tr[0][i]) { q.push(tr[0][i]); seq.push_back(tr[0][i]); } } while(q.size()) { int t=q.front(); q.pop(); for(int i=0;i<26;i++) { int &p=tr[t][i]; if(!p) p=tr[ne[t]][i]; else { ne[p]=tr[ne[t]][i]; q.push(p); seq.push_back(p); } } } } int main() { cin>>n; for(int i=0;i<n;i++) { cin>>str; my_insert(i); } build(); for(int i=seq.size()-1;i>=0;i--) f[ne[seq[i]]]+=f[seq[i]]; for(int i=0;i<n;i++) cout<<f[id[i]]<<endl; return 0; }
