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); } else cout<<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); } else cout<<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; }