2020-2021:teams:no_morning_training:shaco:知识点:数据结构:线段树
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:shaco:知识点:数据结构:线段树 [2020/05/27 18:12] shaco |
2020-2021:teams:no_morning_training:shaco:知识点:数据结构:线段树 [2020/05/27 18:15] (当前版本) shaco |
||
|---|---|---|---|
| 行 9: | 行 9: | ||
| 初始版本左儿子下标是父亲下标的两倍，右儿子下标为父亲下标的两倍+1。 | 初始版本左儿子下标是父亲下标的两倍，右儿子下标为父亲下标的两倍+1。 | ||
| ===== 操作 ===== | ===== 操作 ===== | ||
| + | （代码源于网上） | ||
| ==== 建树 ==== | ==== 建树 ==== | ||
| 自上而下，同时更新父节点。 | 自上而下，同时更新父节点。 | ||
| 行 107: | 行 108: | ||
| </hidden> | </hidden> | ||
| ===== 例题 ===== | ===== 例题 ===== | ||
| + | [[https://ac.nowcoder.com/acm/problem/13891|The Trip On Abandoned Railway]] | ||
| + | <hidden mycode> | ||
| + | <code cpp> | ||
| + | #include<cstdio> | ||
| + | #include<cstring> | ||
| + | #define INF 1000000007 | ||
| + | using namespace std; | ||
| + | int t,n,m,d,p[100005],T[500005]; | ||
| + | long long tag[500005][3]; | ||
| + | void push_down(int k) | ||
| + | { | ||
| + | tag[k<<1][0]+=tag[k][0]; | ||
| + | tag[k<<1][1]+=tag[k][1]; | ||
| + | tag[k<<1][2]+=tag[k][2]; | ||
| + | tag[k<<1|1][0]+=tag[k][0]; | ||
| + | tag[k<<1|1][1]+=tag[k][1]; | ||
| + | tag[k<<1|1][2]+=tag[k][2]; | ||
| + | tag[k][0]=tag[k][1]=tag[k][2]=0; | ||
| + | } | ||
| + | void update(int L,int R,int l,int r,int k,int startup,int quota) | ||
| + | { | ||
| + | if(l>=L&&r<=R) | ||
| + | { | ||
| + | tag[k][0]++; | ||
| + | tag[k][1]+=startup; | ||
| + | tag[k][2]+=quota; | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | push_down(k); | ||
| + | int mid=(l+r)/2; | ||
| + | if(L<=mid) | ||
| + | update(L,R,l,mid,k<<1,startup,quota); | ||
| + | if(R>mid) | ||
| + | update(L,R,mid+1,r,k<<1|1,startup,quota); | ||
| + | } | ||
| + | } | ||
| + | int query(int k,int target,int l,int r) | ||
| + | { | ||
| + | if(l==r) | ||
| + | { | ||
| + | int ans=(T[k]+tag[k][2]%INF+((tag[k][0]*l-tag[k][1])*d)%INF)%INF; | ||
| + | T[k]=tag[k][0]=tag[k][1]=tag[k][2]=0; | ||
| + | return ans; | ||
| + | } | ||
| + | push_down(k); | ||
| + | int mid=(l+r)>>1; | ||
| + | if(target<=mid) | ||
| + | return query(k<<1,target,l,mid); | ||
| + | return query(k<<1|1,target,mid+1,r); | ||
| + | } | ||
| + | void build(int now,int l,int r) | ||
| + | { | ||
| + | if(l==r) | ||
| + | T[now]=p[l]; | ||
| + | else | ||
| + | { | ||
| + | int mid=(l+r)>>1; | ||
| + | build(now<<1,l,mid); | ||
| + | build(now<<1|1,mid+1,r); | ||
| + | } | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | scanf("%d",&t); | ||
| + | while(t--) | ||
| + | { | ||
| + | memset(T,0,sizeof(T)); | ||
| + | memset(tag,0,sizeof(tag)); | ||
| + | scanf("%d%d%d",&n,&m,&d); | ||
| + | for(int i=1;i<=n;i++) | ||
| + | scanf("%d",&p[i]); | ||
| + | build(1,1,n); | ||
| + | for(int i=1,op,x,y;i<=m;i++) | ||
| + | { | ||
| + | scanf("%d",&op); | ||
| + | if(op==1) | ||
| + | { | ||
| + | scanf("%d%d",&x,&y); | ||
| + | update(x,n,1,n,1,x,y); | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | scanf("%d",&x); | ||
| + | printf("%d\n",query(1,x,1,n)); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/no_morning_training/shaco/知识点/数据结构/线段树.1590574351.txt.gz · 最后更改: 2020/05/27 18:12 由 shaco
