下面是OI Wiki对树状数组和线段树原理的详解:
树状数组
线段树
动态 DP
upd:
线段树非递归的单点写法:(需要维护每个元素所在的叶结点的位置)
int mp[N];//a[i]放在哪个叶结点 void build(int u,int l,int r){ tree[u].l=l,tree[u].r=r; if(l==r){ tree[u].v=a[l]; mp[l]=u;/*plus*/ return; } int mid=(l+r)>>1; build(u<<1,l,mid);build(u<<1|1,mid+1,r); pushup(u); } void add(int u,ll v){ u=mp[u]; tree[u].v+=v; while(u>>=1) pushup(u); }
A [NOIP2012]借教室
做法:二分+差分
由于随着订单数量的增加,每天可用教室的数量一定单调下降。
因此我们可以二分出第一天出现负值的订单编号。
剩下的问题是如何快速求出经过若干订单后,每天所剩的教室数量。
每个订单的操作是 [L,R]全部减去d。
因此我们可以用差分来加速处理过程。
代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48606005
int n,m,s[N],t[N]; ll r[N],d[N],diff[N]; bool check(int x){ mst(diff,0); for(int i=1;i<=x;i++){ diff[s[i]]+=d[i]; diff[t[i]+1]-=d[i]; } ll need=0; rep(i,1,n){ need+=+diff[i]; if(need>r[i]) return 0; } return 1; } void solve(){ cin>>n>>m; rep(i,1,n) cin>>r[i]; rep(i,1,m) cin>>d[i]>>s[i]>>t[i]; int l=1,r=m,ans=0; while(l<=r){ int mid=(l+r)>>1; if(check(mid)) l=mid+1; else r=mid-1,ans=mid; } if(ans) cout<<"-1\n"<<ans<<"\n"; else cout<<"0\n"; }
B [SDOI2009]HH的项链
题意求区间内这一段中有多少不同的数字
这是一道很经典的离线莫队的模板题
莫队算法
莫队
代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48657705
ll a[N],id[N]; ll res[W],ans[M]; ll cnt; struct query { int l,r,id; }q[M]; bool cmp(query a, query b) { return (id[a.l] ^ id[b.l]) ? id[a.l] < id[b.l] : ((id[a.l] & 1) ? a.r < b.r : a.r > b.r); } void solve(){ int n;cin>>n; int len=sqrt(n),siz=(n+len-1)/len; for(int i=1;i<=n;i++){ cin>>a[i]; id[i]=(i-1)/len+1; } int m;cin>>m; for(int i=1;i<=m;i++) { cin>>q[i].l>>q[i].r; q[i].id=i; } sort(q+1,q+1+m,cmp); int l=1,r=0; for(int i=1;i<=m;i++) { int ql=q[i].l,qr=q[i].r; while(l < ql) cnt -= !--res[a[l++]]; while(l > ql) cnt += !res[a[--l]]++; while(r < qr) cnt += !res[a[++r]]++; while(r > qr) cnt -= !--res[a[r--]]; ans[q[i].id]=cnt; } for(int i=1;i<=m;i++) cout<<ans[i]<<"\n"; }
树状数组
先将求区间元素种类数问题转化成求区间和问题
那么怎么转化呢?
我们可以先将所有的询问离线下来,对于每一个r来统计区间[1,r]的元素种类数,利用前缀和的思想来求区间[l,r]的元素种类数(即[1,r]的元素种类数减去[1,l-1]的元素种类数)
代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48669053
int n,m; int a[N],c[N]; int ans[M]; int pre[W];//上一次w出现的位置 struct node{ int l,id; };//固定r //在x位置加上v void add(int x,int v){ while(x<=n){ c[x]+=v; x+=lowbit(x); } } //求前缀和 int getsum(int x){ int res=0; while(x>0){ res+=c[x]; x-=lowbit(x); } return res; } vector<node> q[N]; void solve(){ cin>>n; rep(i,1,n) cin>>a[i]; cin>>m; rep(i,1,m){ int l,r;cin>>l>>r; q[r].pb({l,i}); } rep(r,1,n){ if(pre[a[r]]) add(pre[a[r]],-1); add(r,1); pre[a[r]]=r; for(auto [l,id]:q[r]){ ans[id]=getsum(r)-getsum(l-1); } } rep(i,1,m) cout<<ans[i]<<"\n"; }
C [HEOI2012]采花
这题和上题类似,只要记录上两次次w出现的位置并进行单点修改即可
代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48669075
int n,m,w; int a[N],c[N]; int ans[N]; int pre[N][2];//pre[w][0]:上一次w出现的位置 pre[w][1]:上两次w出现的位置 struct node{ int l,id; };//固定r void add(int x,int v){ //在x位置加上v while(x<=n){ c[x]+=v; x+=lowbit(x); } } //求前缀和 int getsum(int x){ int res=0; while(x>0){ res+=c[x]; x-=lowbit(x); } return res; } vector<node> q[N]; void solve(){ cin>>n>>w>>m; rep(i,1,n) cin>>a[i]; rep(i,1,m){ int l,r;cin>>l>>r; q[r].pb({l,i}); } rep(r,1,n){ if(pre[a[r]][1]) add(pre[a[r]][1],-1),add(pre[a[r]][0],1); else if(pre[a[r]][0]) add(pre[a[r]][0],1); pre[a[r]][1]=pre[a[r]][0]; pre[a[r]][0]=r; for(auto [l,id]:q[r]){ ans[id]=getsum(r)-getsum(l-1); } } rep(i,1,m) cout<<ans[i]<<"\n"; }
D 数据结构
模板题 需要维护两个值以及两个懒标记
区间和:
区间平方和:
代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48657607
int n,m; ll a[N]; struct node{ int l,r; ll add,mul; ll v1,v2; }tree[N<<2]; void pushup(int u){ tree[u].v1=tree[u<<1].v1+tree[u<<1|1].v1; tree[u].v2=tree[u<<1].v2+tree[u<<1|1].v2; } void pushdown(int u){ if(tree[u].add||tree[u].mul!=1){ //cal_lazy tree[u<<1].v2 = tree[u].mul*tree[u].mul*tree[u<<1].v2 + 2*tree[u].mul*tree[u].add*tree[u<<1].v1 + tree[u].add*tree[u].add*(tree[u<<1].r-tree[u<<1].l+1); tree[u<<1|1].v2 = tree[u].mul*tree[u].mul*tree[u<<1|1].v2 + 2*tree[u].mul*tree[u].add*tree[u<<1|1].v1 + tree[u].add*tree[u].add*(tree[u<<1|1].r-tree[u<<1|1].l+1); tree[u<<1].v1 = tree[u].mul*tree[u<<1].v1 + tree[u].add*(tree[u<<1].r-tree[u<<1].l+1); tree[u<<1|1].v1 = tree[u].mul*tree[u<<1|1].v1 + tree[u].add*(tree[u<<1|1].r-tree[u<<1|1].l+1); //union_lazy tree[u<<1].mul = tree[u<<1].mul*tree[u].mul; tree[u<<1|1].mul = tree[u<<1|1].mul*tree[u].mul; tree[u<<1].add = tree[u<<1].add*tree[u].mul + tree[u].add; tree[u<<1|1].add = tree[u<<1|1].add*tree[u].mul + tree[u].add; //init_lazy tree[u].mul=1;tree[u].add=0; } } void build(int u,int l,int r){ tree[u].l=l;tree[u].r=r; tree[u].mul=1;tree[u].add=0; //init_lazy if(l==r){ tree[u].v2=a[l]*a[l]; tree[u].v1=a[l]; return; } int mid=(l+r)>>1; build(u<<1,l,mid);build(u<<1|1,mid+1,r); pushup(u); } void modify_add(int u,int l,int r,ll v){ if(l<=tree[u].l&&tree[u].r<=r){ tree[u].v2 = tree[u].v2 + 2*v*tree[u].v1 + v*v*(tree[u].r-tree[u].l+1); tree[u].v1 = tree[u].v1 + v*(tree[u].r-tree[u].l+1); tree[u].add=tree[u].add+v; return; } pushdown(u); int mid=(tree[u].l+tree[u].r)>>1; if(r<=mid) modify_add(u<<1,l,r,v); else if(l>mid) modify_add(u<<1|1,l,r,v); else modify_add(u<<1,l,r,v),modify_add(u<<1|1,l,r,v); pushup(u); } void modify_mul(int u,int l,int r,ll v){ if(l<=tree[u].l&&tree[u].r<=r){ tree[u].v2 = tree[u].v2*v*v; tree[u].v1 = tree[u].v1*v; tree[u].mul=tree[u].mul*v; tree[u].add=tree[u].add*v; return; } pushdown(u); int mid=(tree[u].l+tree[u].r)>>1; if(r<=mid) modify_mul(u<<1,l,r,v); else if(l>mid) modify_mul(u<<1|1,l,r,v); else modify_mul(u<<1,l,r,v),modify_mul(u<<1|1,l,r,v); pushup(u); } ll query_sum1(int u,int l,int r){ if(l<=tree[u].l&&tree[u].r<=r) return tree[u].v1; pushdown(u); int mid=(tree[u].l+tree[u].r)>>1; if(r<=mid) return query_sum1(u<<1,l,r); else if(l>mid) return query_sum1(u<<1|1,l,r); else return query_sum1(u<<1,l,r)+query_sum1(u<<1|1,l,r); } ll query_sum2(int u,int l,int r){ if(l<=tree[u].l&&tree[u].r<=r) return tree[u].v2; pushdown(u); int mid=(tree[u].l+tree[u].r)>>1; if(r<=mid) return query_sum2(u<<1,l,r); else if(l>mid) return query_sum2(u<<1|1,l,r); else return query_sum2(u<<1,l,r)+query_sum2(u<<1|1,l,r); } void solve(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; build(1,1,n); while(m--){ int op;cin>>op; if(op==1){ int l,r;cin>>l>>r; cout<<query_sum1(1,l,r)<<"\n"; } else if(op==2){ int l,r;cin>>l>>r; cout<<query_sum2(1,l,r)<<"\n"; } else if(op==3){ int l,r;ll x;cin>>l>>r>>x; modify_mul(1,l,r,x); } else{ int l,r;ll x;cin>>l>>r>>x; modify_add(1,l,r,x); } } }
E 线段树
这题维护区间[l,r]数字的乘积和
然后可以根据上一题求出的区间和和区间平方和套上去即可
代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48662189
ll mod; int n,m; ll a[N]; ll fpow(ll a,ll b){ ll ans=1%mod; while(b){ if(b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } struct node{ int l,r; ll add,mul; ll v1,v2; }tree[N<<2]; void pushup(int u){ tree[u].v1=(tree[u<<1].v1+tree[u<<1|1].v1)%mod; tree[u].v2=(tree[u<<1].v2+tree[u<<1|1].v2)%mod; } void pushdown(int u){ if(tree[u].add||tree[u].mul!=1){ //cal_lazy tree[u<<1].v2 = (tree[u].mul*tree[u].mul%mod*tree[u<<1].v2%mod + 2*tree[u].mul%mod*tree[u].add%mod*tree[u<<1].v1%mod + tree[u].add*tree[u].add%mod*(tree[u<<1].r-tree[u<<1].l+1)%mod)%mod; tree[u<<1|1].v2 = (tree[u].mul*tree[u].mul%mod*tree[u<<1|1].v2%mod + 2*tree[u].mul%mod*tree[u].add%mod*tree[u<<1|1].v1%mod + tree[u].add*tree[u].add%mod*(tree[u<<1|1].r-tree[u<<1|1].l+1)%mod)%mod; tree[u<<1].v1 = (tree[u].mul*tree[u<<1].v1%mod + tree[u].add*(tree[u<<1].r-tree[u<<1].l+1)%mod)%mod; tree[u<<1|1].v1 = (tree[u].mul*tree[u<<1|1].v1%mod + tree[u].add*(tree[u<<1|1].r-tree[u<<1|1].l+1)%mod)%mod; //union_lazy tree[u<<1].mul = tree[u<<1].mul*tree[u].mul%mod; tree[u<<1|1].mul = tree[u<<1|1].mul*tree[u].mul%mod; tree[u<<1].add = (tree[u<<1].add*tree[u].mul%mod + tree[u].add)%mod; tree[u<<1|1].add = (tree[u<<1|1].add*tree[u].mul%mod + tree[u].add)%mod; //init_lazy tree[u].mul=1;tree[u].add=0; } } void build(int u,int l,int r){ tree[u].l=l;tree[u].r=r; tree[u].mul=1;tree[u].add=0; //init_lazy if(l==r){ tree[u].v2=a[l]*a[l]%mod; tree[u].v1=a[l]; return; } int mid=(l+r)>>1; build(u<<1,l,mid);build(u<<1|1,mid+1,r); pushup(u); } void modify_add(int u,int l,int r,ll v){ if(l<=tree[u].l&&tree[u].r<=r){ tree[u].v2 = (tree[u].v2 + 2*v%mod*tree[u].v1%mod + v*v%mod*(tree[u].r-tree[u].l+1)%mod)%mod; tree[u].v1 = (tree[u].v1 + v*(tree[u].r-tree[u].l+1)%mod)%mod; tree[u].add=(tree[u].add+v)%mod; return; } pushdown(u); int mid=(tree[u].l+tree[u].r)>>1; if(r<=mid) modify_add(u<<1,l,r,v); else if(l>mid) modify_add(u<<1|1,l,r,v); else modify_add(u<<1,l,r,v),modify_add(u<<1|1,l,r,v); pushup(u); } void modify_mul(int u,int l,int r,ll v){ if(l<=tree[u].l&&tree[u].r<=r){ tree[u].v2 = tree[u].v2*v%mod*v%mod; tree[u].v1 = tree[u].v1*v%mod; tree[u].mul=tree[u].mul*v%mod; tree[u].add=tree[u].add*v%mod; return; } pushdown(u); int mid=(tree[u].l+tree[u].r)>>1; if(r<=mid) modify_mul(u<<1,l,r,v); else if(l>mid) modify_mul(u<<1|1,l,r,v); else modify_mul(u<<1,l,r,v),modify_mul(u<<1|1,l,r,v); pushup(u); } ll query_sum1(int u,int l,int r){ if(l<=tree[u].l&&tree[u].r<=r) return tree[u].v1; pushdown(u); int mid=(tree[u].l+tree[u].r)>>1; if(r<=mid) return query_sum1(u<<1,l,r); else if(l>mid) return query_sum1(u<<1|1,l,r); else return (query_sum1(u<<1,l,r)+query_sum1(u<<1|1,l,r))%mod; } ll query_sum2(int u,int l,int r){ if(l<=tree[u].l&&tree[u].r<=r) return tree[u].v2; pushdown(u); int mid=(tree[u].l+tree[u].r)>>1; if(r<=mid) return query_sum2(u<<1,l,r); else if(l>mid) return query_sum2(u<<1|1,l,r); else return (query_sum2(u<<1,l,r)+query_sum2(u<<1|1,l,r))%mod; } void solve(){ cin>>n>>m>>mod; ll inv2=fpow(2,mod-2); for(int i=1;i<=n;i++) cin>>a[i],a[i]%=mod; build(1,1,n); while(m--){ int op;cin>>op; if(op==1){ int l,r;ll x;cin>>l>>r>>x; modify_add(1,l,r,x); } else if(op==2){ int l,r;ll x;cin>>l>>r>>x; modify_mul(1,l,r,x); } else{ int l,r;cin>>l>>r; ll ans1=query_sum1(1,l,r); ll ans2=query_sum2(1,l,r); cout<<(ans1*ans1%mod-ans2+mod)*inv2%mod<<"\n"; } } }
F little w and Discretization
代码链接:
G 智乃酱的平方数列
代码链接:
H 仓鼠的鸡蛋
线段树树上二分
维护区间最大值,并用二分的思想存放在哪个结点中
优先放左子树,不行放右子树
每次存放修改结点的最大容量
代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48704051
int n,m,k; ll a[N],cnt[N]; struct node{ int l,r; ll v; }tree[N<<2]; void pushup(int u){ tree[u].v=max(tree[u<<1].v,tree[u<<1|1].v); } void build(int u,int l,int r){ tree[u].l=l,tree[u].r=r; if(l==r){ tree[u].v=m; cnt[l]=0; return; } int mid=(l+r)>>1; build(u<<1,l,mid);build(u<<1|1,mid+1,r); pushup(u); } ll modify(int u,ll v){ while(tree[u].l<tree[u].r){ if(tree[u<<1].v>=v) u<<=1; else (u<<=1)|=1; } tree[u].v-=v; int ans=tree[u].l; if(++cnt[tree[u].l]==k) tree[u].v=0; while(u>>=1) pushup(u); return ans; } void solve(){ cin>>n>>m>>k; build(1,1,n); rep(i,1,n){ ll x;cin>>x; if(x>m) cout<<"-1\n"; else cout<<modify(1,x)<<"\n"; } }
I 智乃酱的cube
代码链接:
J 智乃酱的双塔问题·极(带修改的DP,DDP)
代码链接:
K 智乃酱的双塔问题·改
代码链接: