第四章 高级数据结构

4.1 并查集

4.1.1 1250. 格子游戏

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=40010;int n,m;
int p[N];
int findP(int x)
{if(p[x]!=x) return p[x]=findP(p[x]);return p[x];
}
int main()
{cin>>n>>m;for(int i=0;i<=N;i++) p[i]=i;bool success=false;for(int i=0;i<m;i++){int x,y;char c;cin>>x>>y>>c;int a=(x-1)*n+y-1;int b=a;if(c=='R'){b++;}elseb+=n;int pa=findP(a),pb=findP(b);if(pa==pb){cout<<i+1<<endl;success=true;break;}elsep[pa]=pb;}if(!success)cout<<"draw"<<endl;return 0;
}

4.1.2 1252. 搭配购买

代码：

#include<bits/stdc++.h> //y总的using namespace std;const int N = 10010;int n, m, vol;
int v[N], w[N];
int p[N];
int f[N];int find(int x)
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}int main()
{cin >> n >> m >> vol;for (int i = 1; i <= n; i ++ ) p[i] = i;for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];while (m -- ){int a, b;cin >> a >> b;int pa = find(a), pb = find(b);if (pa != pb){v[pb] += v[pa];w[pb] += w[pa];p[pa] = pb;}}// 01背包for (int i = 1; i <= n; i ++ )if (p[i] == i)for (int j = vol; j >= v[i]; j -- )f[j] = max(f[j], f[j - v[i]] + w[i]);cout << f[vol] << endl;return 0;
}
/* 自己写的
#include<bits/stdc++.h>
using namespace std;
const int N=10010;int n,m,w;
map<int,pair<int,int> > mp;
int money[N],value[N];
int cnt;
int M[N],V[N];
int dp[N];
int p[N];
int findP(int x)
{if(p[x]!=x) return p[x]=findP(p[x]);return p[x];
}int main()
{cin>>n>>m>>w;for(int i=1;i<=n;i++) p[i]=i;for(int i=1;i<=n;i++){cin>>money[i]>>value[i];}for(int i=0;i<m;i++){int a,b;cin>>a>>b;p[findP(a)]=findP(b);}for(int i=1;i<=n;i++){int pa=findP(i);mp[pa].first+=money[i];mp[pa].second+=value[i];}for(map<int,pair<int,int> >::iterator it=mp.begin();it!=mp.end();it++){cnt++;M[cnt]=it->second.first;V[cnt]=it->second.second;}for(int i=1;i<=cnt;i++){for(int j=w;j>=M[i];j--){dp[j]=max(dp[j],dp[j-M[i]]+V[i]);}}cout<<dp[w];return 0;
}
*/

4.1.3 237. 程序自动分析

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=200010;int cnt;
struct Node{int a,b,c;
}op[100010];
unordered_map<int,int> mp;
int p[N];
int findP(int x)
{if(p[x]!=x) return p[x]=findP(p[x]);return p[x];
}int main()
{int t;cin>>t;while(t--){int n;cin>>n;cnt=1;mp.clear();for(int i=1;i<=N;i++) p[i]=i;for(int i=1;i<=n;i++){int a,b,c;cin>>a>>b>>c;if(mp.count(a)==0)mp[a]=cnt++;if(mp.count(b)==0)mp[b]=cnt++;op[i].a=a,op[i].b=b,op[i].c=c;}for(int i=1;i<=n;i++){int a=op[i].a,b=op[i].b,c=op[i].c;if(c==1){p[findP(mp[a])]=findP(mp[b]);}}bool success=true;for(int i=1;i<=n;i++){int a=op[i].a,b=op[i].b,c=op[i].c;if(c==0){if(findP(mp[a])==findP(mp[b])){success=false;break;}}}if(success) cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;
}

4.1.4 239. 奇偶游戏

代码：

#include<bits/stdc++.h>     //带边权并查集
using namespace std;
const int N=20010;int n,m;
int p[N],d[N];
map<int,int> S;int get(int x)
{if(S.count(x)==0) S[x]=++n;return S[x];
}int findP(int x)
{if(p[x]!=x){int root=findP(p[x]);d[x]^=d[p[x]];p[x]=root;}return p[x];
}
int main()
{cin>>n>>m;n=0;for(int i=0;i<N;i++) p[i]=i;int res=m;for(int i=1;i<=m;i++){int a,b;string type;cin>>a>>b>>type;a=get(a-1),b=get(b);int t=0;if(type=="odd") t=1;int pa=findP(a),pb=findP(b);if(pa==pb){if(d[a]^d[b]!=t){res=i-1;break;}}else{p[pa]=pb;d[pa]=d[a]^d[b]^t;}}cout<<res<<endl;return 0;
}/* 扩展域
#include<bits/stdc++.h>
using namespace std;
const int N=40010,base=N/2;int n,m;
int p[N],d[N];
map<int,int> S;int get(int x)
{if(S.count(x)==0) S[x]=++n;return S[x];
}int findP(int x)
{if(p[x]!=x) return p[x]=findP(p[x]);return p[x];
}int main()
{cin>>n>>m;n=0;for(int i=0;i<N;i++) p[i]=i;int res=m;for(int i=1;i<=m;i++){int a,b;string type;cin>>a>>b>>type;a=get(a-1),b=get(b);if(type=="even"){if(findP(a+base)==findP(b)){res=i-1;break;}p[findP(a)]=findP(b);p[findP(a+base)]=findP(b+base);}else{if(findP(a)==findP(b)){res=i-1;break;}p[findP(a)]=findP(b+base);p[findP(a+base)]=findP(b);}}cout<<res<<endl;return 0;
}
*/

4.1.5 238. 银河英雄传说

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=30010;int n;
int p[N],sz[N],d[N];
int findP(int x)
{if(p[x]!=x){int root=findP(p[x]);d[x]+=d[p[x]];p[x]=root;}return p[x];
}
int main()
{cin>>n;for(int i=1;i<=N;i++){p[i]=i;sz[i]=1;}for(int i=0;i<n;i++){string type;int a,b;cin>>type>>a>>b;int pa=findP(a),pb=findP(b);if(type=="M"){d[pa]=sz[pb];sz[pb]+=sz[pa];p[pa]=pb;}else{if(pa!=pb)cout<<-1<<endl;elsecout<<max(0,abs(d[a]-d[b])-1)<<endl;}}return 0;
}

4.2 树状数组

4.2.1 241. 楼兰图腾

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;const int N=200010;int n;
int a[N],tr[N];
int big[N],little[N];
int lowbit(int x)
{return x&(-x);
}void add(int x,int c)
{for(int i=x;i<=n;i+=lowbit(i))  //从x开始tr[i]+=c;
}int sum(int x)
{int res=0;for(int i=x;i>0;i-=lowbit(i))res+=tr[i];return res;
}
int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){int y=a[i];big[i]=sum(n)-sum(y);little[i]=sum(y-1);add(y,1);}memset(tr,0,sizeof tr);LL res1=0,res2=0;for(int i=n;i>=1;i--){int y=a[i];res1+=big[i]*(LL)(sum(n)-sum(y));res2+=little[i]*(LL)sum(y-1);add(y,1);}cout<<res1<<" "<<res2<<endl;return 0;
}

4.2.2 242. 一个简单的整数问题

代码：

#include<bits/stdc++.h> //差分，树状数组综合应用
using namespace std;
const int N=100010;int n,m;
int a[N];
int b[N];   //差分数组
int tr[N];  //差分数组的树状数组void myinsert(int l,int r,int c)    //差分
{b[l]+=c,b[r+1]-=c;
}int lowbit(int x)
{return x&(-x);
}void add(int x,int c)
{for(int i=x;i<=n;i+=lowbit(i))  //从x开始tr[i]+=c;
}int sum(int x)
{int res=0;for(int i=x;i>0;i-=lowbit(i))res+=tr[i];return res;
}int main()
{cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)myinsert(i,i,a[i]);for(int i=1;i<=n;i++)add(i,b[i]);while(m--){string op;cin>>op;if(op=="Q"){int x;cin>>x;cout<<sum(x)<<endl;}else{int l,r,c;cin>>l>>r>>c;add(l,c),add(r+1,-c);}}return 0;
}

4.2.3 243. 一个简单的整数问题2

代码：

#include<bits/stdc++.h> //差分，树状数组综合应用
using namespace std;
typedef long long LL;
const int N=100010;int n,m;
int a[N];
LL tr_b[N];  //差分数组b[i]的树状数组
LL tr_bi[N]; //差分数组b[i]*i的树状数组int lowbit(int x)
{return x&(-x);
}void add(LL tr[],int x,LL c)
{for(int i=x;i<=n;i+=lowbit(i))  //从x开始tr[i]+=c;
}LL sum(LL tr[],int x)
{LL res=0;for(int i=x;i>0;i-=lowbit(i))res+=tr[i];return res;
}LL prefix_sum(int x)
{return sum(tr_b,x)*(x+1)-sum(tr_bi,x);
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){int b=a[i]-a[i-1];add(tr_b,i,b);add(tr_bi,i,(LL)b*i);}while(m--){string op;int l,r,d;cin>>op>>l>>r;if(op=="Q"){cout<<prefix_sum(r)-prefix_sum(l-1)<<endl;}else{cin>>d;add(tr_b,l,d),add(tr_b,r+1,-d);//均只要修改两处add(tr_bi,l,l*d),add(tr_bi,r+1,(r+1)*-d);}}return 0;
}

4.2.4 244. 谜一样的牛

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100010;int n;
int h[N];
int ans[N];
int tr[N];
int lowbit(int x)
{return x&-x;
}
void add(int x,int c)
{for(int i=x;i<=n;i+=lowbit(i))tr[i]+=c;
}
int sum(int x)
{int res=0;for(int i=x;i>0;i-=lowbit(i))res+=tr[i];return res;
}
int main()
{cin>>n;for(int i=2;i<=n;i++)cin>>h[i];for(int i=1;i<=n;i++)tr[i]=lowbit(i);for(int i=n;i>0;i--){int k=h[i]+1;int l=1,r=n;while(l<r){int mid=(l+r)/2;if(sum(mid)>=k) r=mid;else l=mid+1;}ans[i]=r;add(r,-1);}for(int i=1;i<=n;i++)cout<<ans[i]<<endl;return 0;
}

4.3 线段树

4.3.1 1275. 最大数

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=200010,INF=0x3f3f3f3f;int m,p;
int n;
struct Node
{int l,r;int v;  // 区间[l, r]中的最大值Node(){}Node(int _l,int _r,int _v){l=_l,r=_r,v=_v;}
}tr[4*N];void pushup(int u)  // 由子节点的信息，来计算父节点的信息 u表示父节点编号
{tr[u].v=max(tr[u<<1].v,tr[u<<1|1].v);
}void build(int u,int l,int r)   //u表示父节点编号,从u开始建立[l,r]的线段树
{tr[u]=Node(l,r,0);if(l==r) return;int mid=l+r>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);pushup(u);
}int query(int u,int l,int r)
{if(tr[u].l>=l&&tr[u].r<=r) return tr[u].v; // 树中节点，已经被完全包含在[l, r]中了int mid=tr[u].l+tr[u].r>>1;int v=-INF;if(l<=mid) v=query(u<<1,l,r);if(r>mid) v=max(v,query(u<<1|1,l,r));return v;
}void modify(int u,int x,int v) //单点修改，将u父节点编号，x是要修改的点，v是要修改为多少
{if(tr[u].l==x&&tr[u].r==x) tr[u].v=v;else{int mid=tr[u].l+tr[u].r>>1;if(x<=mid) modify(u<<1,x,v);else  modify(u<<1|1,x,v);pushup(u);}
}
int main()
{cin>>m>>p;int num=0;build(1,1,m);while(m--){string op;int x;cin>>op>>x;if(op=="Q"){num=query(1,n-x+1,n);cout<<num<<endl;}else{n++;modify(1,n,(num+x)%p);}}return 0;
}

4.3.2 245. 你能回答这些问题吗

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=500010,INF=0x3f3f3f3f;int n,m;
int w[N];
struct Node
{int l,r;int sum,tmax,lmax,rmax;Node(){}Node(int _l,int _r,int _sum,int _tmax,int _lmax,int _rmax){l=_l,r=_r,sum=_sum,tmax=_tmax,lmax=_lmax,rmax=_rmax;}
}tr[N*4];void pushup(Node &u,Node &l,Node &r)
{u.sum=l.sum+r.sum;u.lmax=max(l.lmax,l.sum+r.lmax);u.rmax=max(r.rmax,r.sum+l.rmax);u.tmax=max(max(l.tmax,r.tmax),l.rmax+r.lmax);
}
void pushup(int u)
{pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}void build(int u,int l,int r)
{if(l==r) tr[u]=Node(l,r,w[r],w[r],w[r],w[r]);else{tr[u]=Node(l,r,0,0,0,0);int mid=l+r>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);pushup(u);}
}void modify(int u,int x,int v)
{if(tr[u].l==x&&tr[u].r==x) tr[u]=Node(x,x,v,v,v,v);else{int mid=tr[u].l+tr[u].r>>1;if(x<=mid) modify(u<<1,x,v);else modify(u<<1|1,x,v);pushup(u);}
}Node query(int u,int l,int r)
{if(tr[u].l>=l&&tr[u].r<=r) return tr[u];int mid=tr[u].l+tr[u].r>>1;if(r<=mid) return query(u<<1,l,r);else if(l>mid) return query(u<<1|1,l,r);else{Node left=query(u<<1,l,r);Node right=query(u<<1|1,l,r);Node res;pushup(res,left,right);return res;}
}
int main()
{ios::sync_with_stdio(0);cin>>n>>m;for(int i=1;i<=n;i++)cin>>w[i];build(1,1,n);while(m--){int k,x,y;cin>>k>>x>>y;if(k==1){if(x>y) swap(x,y);cout<<query(1,x,y).tmax<<endl;}else modify(1,x,y);}return 0;
}

4.3.3 246. 区间最大公约数

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=500010;int n,m;
LL w[N];
struct Node
{int l,r;LL sum,d;Node(){}Node(int _l,int _r,LL _sum,LL _d){l=_l,r=_r,sum=_sum,d=_d;}
}tr[N*4];LL gcd(LL a,LL b)
{return b?gcd(b,a%b):a;
}void pushup(Node &u,Node &l,Node &r)
{u.sum=l.sum+r.sum;u.d=gcd(l.d,r.d);
}void pushup(int u)
{pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}void build(int u,int l,int r)
{if(l==r){LL b=w[r]-w[r-1];tr[u]=Node(l,r,b,b);}else{tr[u].l=l,tr[u].r=r;int mid=l+r>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);pushup(u);}
}void modify(int u,int x,LL v)
{if(tr[u].l==x&&tr[u].r==x){LL b=tr[u].sum+v;tr[u]=Node(x,x,b,b);}else{int mid=tr[u].l+tr[u].r>>1;if(x<=mid) modify(u<<1,x,v);else modify(u<<1|1,x,v);pushup(u);}
}Node query(int u,int l,int r)
{if(tr[u].l>=l&&tr[u].r<=r) return tr[u];//注意三种情况int mid=tr[u].l+tr[u].r>>1;if(r<=mid) return query(u<<1,l,r);else if(l>mid) return query(u<<1|1,l,r);else{Node left=query(u<<1,l,r);Node right=query(u<<1|1,l,r);Node res;pushup(res,left,right);return res;}
}int main()
{cin>>n>>m;for(int i=1;i<=n;i++) cin>>w[i];build(1,1,n);string op;int l,r;LL d;while(m--){cin>>op>>l>>r;if(op=="Q"){Node left=query(1,1,l);Node right=Node(0,0,0,0);if(l+1<=r) right=query(1,l+1,r);cout<<abs(gcd(left.sum,right.d))<<endl;}else{cin>>d;modify(1,l,d);if(r+1<=n) modify(1,r+1,-d);}}return 0;
}

4.3.4 243. 一个简单的整数问题2

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100010;int n,m;
int w[N];
struct Node
{int l,r;LL sum,add;Node(){}Node(int _l,int _r,LL _sum,LL _add){l=_l,r=_r,sum=_sum,add=_add;}
}tr[N*4];void pushup(int u)
{tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}void pushdown(int u)
{Node &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];if(root.add){left.add+=root.add,left.sum+=(LL)(left.r-left.l+1)*root.add;right.add+=root.add,right.sum+=(LL)(right.r-right.l+1)*root.add;root.add=0;}
}void build(int u,int l,int r)
{if(l==r) tr[u]=Node(l,r,w[r],0);else{tr[u]=Node(l,r,0,0);int mid=l+r>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);pushup(u);}
}void modify(int u,int l,int r,int d)
{if(tr[u].l>=l&&tr[u].r<=r){tr[u].sum+=(LL)(tr[u].r-tr[u].l+1)*d;tr[u].add+=d;}else // 一定要分裂{pushdown(u);int mid=tr[u].l+tr[u].r>>1;if(l<=mid) modify(u<<1,l,r,d);if(r>mid) modify(u<<1|1,l,r,d);pushup(u);}
}LL query(int u,int l,int r)
{if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;pushdown(u);int mid=tr[u].l+tr[u].r>>1;LL sum=0;if(l<=mid) sum+=query(u<<1,l,r);if(r>mid) sum+=query(u<<1|1,l,r);return sum;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++) cin>>w[i];build(1,1,n);string op;int l,r,d;while(m--){cin>>op>>l>>r;if(op=="C"){cin>>d;modify(1,l,r,d);}elsecout<<query(1,l,r)<<endl;}return 0;
}

4.3.5 247. 亚特兰蒂斯

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
typedef pair<double,double> PII;int n;
struct Segment
{double x,y1,y2;int k;Segment(){}Segment(double _x,double _y1,double _y2,int _k){x=_x,y1=_y1,y2=_y2,k=_k;}bool operator < (const Segment &t) const{return x<t.x;}
}seg[N*2];
struct Node
{int l,r;int cnt;double len;Node(){}Node(int _l,int _r,int _cnt,double _len){l=_l,r=_r,cnt=_cnt,len=_len;}
}tr[N*2*4];vector<double> ys;int find_y(double y)
{return lower_bound(ys.begin(),ys.end(),y)-ys.begin();
}void pushup(int u)
{if(tr[u].cnt) tr[u].len=ys[tr[u].r+1]-ys[tr[u].l];else if(tr[u].l!=tr[u].r){tr[u].len=tr[u<<1].len+tr[u<<1|1].len;}else tr[u].len=0;
}void build(int u,int l,int r)
{tr[u]=Node(l,r,0,0);if(l!=r){int mid=l+r>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);}
}void modify(int u,int l,int r,int k)
{if(tr[u].l>=l&&tr[u].r<=r){tr[u].cnt+=k;pushup(u);}else{int mid=tr[u].l+tr[u].r>>1;if(l<=mid) modify(u<<1,l,r,k);if(r>mid) modify(u<<1|1,l,r,k);pushup(u);}
}
int main()
{int T=1;while(true){cin>>n;if(n==0) break;ys.clear();for(int i=0,j=0;i<n;i++){double x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;seg[j++]=Segment(x1,y1,y2,1);seg[j++]=Segment(x2,y1,y2,-1);ys.push_back(y1),ys.push_back(y2);}sort(ys.begin(),ys.end());ys.erase(unique(ys.begin(),ys.end()),ys.end());build(1,0,ys.size()-2);sort(seg,seg+n*2);double res=0;for(int i=0;i<n*2;i++){if(i>0) res+=tr[1].len*(seg[i].x-seg[i-1].x);modify(1,find_y(seg[i].y1),find_y(seg[i].y2)-1,seg[i].k);}printf("Test case #%d\n",T++);printf("Total explored area: %.2f\n\n",res);}return 0;
}

4.3.6 1277. 维护序列

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100010;int n,p,m;
int w[N];
struct Node
{int l,r;int sum,add,mul;Node(){}Node(int _l,int _r,int _sum,int _add,int _mul){l=_l,r=_r,sum=_sum,add=_add,mul=_mul;}
}tr[N*4];void pushup(int u)
{tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%p;
}void eval(Node &t,int add,int mul)
{t.sum=((LL)t.sum*mul+(LL)(t.r-t.l+1)*add)%p;t.mul=(LL)t.mul*mul%p;t.add=((LL)t.add*mul+add)%p;
}void pushdown(int u)
{eval(tr[u<<1],tr[u].add,tr[u].mul);eval(tr[u<<1|1],tr[u].add,tr[u].mul);tr[u].add=0,tr[u].mul=1;
}void build(int u,int l,int r)
{if(l==r) tr[u]=Node(l,r,w[r],0,1);else{tr[u]=Node(l,r,0,0,1);int mid=l+r>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);pushup(u);}
}void modify(int u,int l,int r,int add,int mul)
{if(tr[u].l>=l&&tr[u].r<=r) eval(tr[u],add,mul);else{pushdown(u);int mid=tr[u].l+tr[u].r>>1;if(l<=mid) modify(u<<1,l,r,add,mul);if(r>mid) modify(u<<1|1,l,r,add,mul);pushup(u);}
}int query(int u,int l,int r)
{if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;pushdown(u);int mid=tr[u].l+tr[u].r>>1;int sum=0;if(l<=mid) sum=query(u<<1,l,r);if(r>mid) sum=(sum+query(u<<1|1,l,r))%p;return sum;
}
int main()
{cin>>n>>p;for(int i=1;i<=n;i++) cin>>w[i];build(1,1,n);cin>>m;while(m--){int t,l,r,d;cin>>t>>l>>r;if(t==1){cin>>d;modify(1,l,r,0,d);}else if(t==2){cin>>d;modify(1,l,r,d,1);}elsecout<<query(1,l,r)<<endl;}return 0;
}

4.4 可持久化数据结构

4.4.1 256. 最大异或和

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=600010,M=N*25;int n,m;
int s[N];
int tr[M][2],max_id[M];
int root[N],idx;void my_insert(int i,int k,int p,int q)
{if(k<0){max_id[q]=i;return;}int v=s[i]>>k&1;if(p) tr[q][v^1]=tr[p][v^1];tr[q][v]=++idx;my_insert(i,k-1,tr[p][v],tr[q][v]);max_id[q]=max(max_id[tr[q][0]],max_id[tr[q][1]]);
}int query(int root,int C,int L)
{int p=root;for(int i=23;i>=0;i--){int v=C>>i&1;if(max_id[tr[p][v^1]]>=L) p=tr[p][v^1];else p=tr[p][v];}return C^s[max_id[p]];
}
int main()
{ios::sync_with_stdio(0);cin>>n>>m;max_id[0]=-1;root[0]=++idx;my_insert(0,23,0,root[0]);for(int i=1;i<=n;i++){int x;cin>>x;s[i]=s[i-1]^x;root[i]=++idx;my_insert(i,23,root[i-1],root[i]);}string op;int l,r,x;while(m--){cin>>op;if(op=="A"){cin>>x;n++;s[n]=s[n-1]^x;root[n]=++idx;my_insert(n,23,root[n-1],root[n]);}else{cin>>l>>r>>x;cout<<query(root[r-1],s[n]^x,l-1)<<endl;}}return 0;
}

4.4.2 255. 第K小数

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=10010;int n,m;
int a[N];
vector<int> nums;struct Node
{int l,r;int cnt;
}tr[N*4+N*17];int root[N],idx;int find_x(int x)
{return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
}int build(int l,int r)
{int p=++idx;if(l==r) return p;int mid=l+r>>1;tr[p].l=build(l,mid),tr[p].r=build(mid+1,r);return p;
}int my_insert(int p,int l,int r,int x)
{int q=++idx;tr[q]=tr[p];if(l==r){tr[q].cnt++;return q;}int mid=l+r>>1;if(x<=mid) tr[q].l=my_insert(tr[p].l,l,mid,x);else tr[q].r=my_insert(tr[p].r,mid+1,r,x);tr[q].cnt=tr[tr[q].l].cnt+tr[tr[q].r].cnt;return q;
}int query(int q,int p,int l,int r,int k)
{if(l==r) return r;int cnt=tr[tr[q].l].cnt-tr[tr[p].l].cnt;int mid=l+r>>1;if(k<=cnt) return query(tr[q].l,tr[p].l,l,mid,k);else return query(tr[q].r,tr[p].r,mid+1,r,k-cnt);
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];nums.push_back(a[i]);}sort(nums.begin(),nums.end());nums.erase(unique(nums.begin(),nums.end()),nums.end());root[0]=build(0,nums.size()-1);for(int i=1;i<=n;i++)root[i]=my_insert(root[i-1],0,nums.size()-1,find_x(a[i]));while(m--){int l,r,k;cin>>l>>r>>k;cout<<nums[query(root[r],root[l-1],0,nums.size()-1,k)]<<endl;}return 0;
}

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);}}elsep=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;
}