把小煜
UID: 600, 注册于 2024-11-2 19:23:08, 最后登录于 2026-11-6 17:06:03, 最后活动于 2026-11-14 10:10:08.
解决了 242 道题目，RP: 231.9 (No. 7)
-
个人简介
我练习打字两年半，至今仍是一指禅。
我练习打字两年半，至今仍是一指禅。
我练习打字两年半，至今仍是一指禅。
我练习打字两年半，至今仍是一指禅。
我练习打字两年半，至今仍是一指禅。
我练习打字两年半，至今仍是一指禅。
一些模板#include<bits/stdc++.h> #define int long long #define inf 0x3f3f3f3f3f3f3f3f using namespace std; const int N=100010; int n,m; int idx; struct node { int fath,dep,dfn,siz; int top,son; vector<int>G; }point[N]; void dfs1(int u,int fa) { point[u].fath=fa; point[u].dep=point[fa].dep+1; point[u].siz=1; for(int v : point[u].G) { if(v==fa) continue; dfs1(v,u); point[u].siz+=point[v].siz; if(point[v].siz>point[point[u].son].siz) point[u].son=v; } } void dfs2(int u,int fatop) { point[u].top=fatop; point[u].dfn=++idx; if(point[u].son) dfs2(point[u].son,fatop); for(int v:point[u].G) if(v!=point[u].son && v!=point[u].fath) dfs2(v,v); } int a[N],val[N]; struct nodex { int l,r,data,sum,lazy; }t[N<<2]; void build(int p,int l,int r) { t[p].l=l,t[p].r=r; t[p].lazy=0; if(l==r) { t[p].data=val[l]; t[p].sum=val[l]; return; } int mid=l+r>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); t[p].data=max(t[p<<1].data,t[p<<1|1].data); t[p].sum=t[p<<1].sum+t[p<<1|1].sum; } void pushdown(int p) { if(t[p].lazy) { t[p<<1].sum=t[p<<1].sum+t[p].lazy*(t[p<<1].r-t[p<<1].l+1); t[p<<1].data=t[p<<1].data+t[p].lazy; t[p<<1].lazy=t[p<<1].lazy+t[p].lazy; t[p<<1|1].sum=t[p<<1|1].sum+t[p].lazy*(t[p<<1|1].r-t[p<<1|1].l+1); t[p<<1|1].data=t[p<<1|1].data+t[p].lazy; t[p<<1|1].lazy=t[p<<1|1].lazy+t[p].lazy; t[p].lazy=0; } } void add1(int p,int x,int k)//单点修改 { if(t[p].l==t[p].r) { t[p].data+=k; t[p].sum+=k; return; } pushdown(p); int mid=t[p].l+t[p].r>>1; if(x<=mid) add1(p<<1,x,k); if(x>mid) add1(p<<1|1,x,k); t[p].data=max(t[p<<1].data,t[p<<1|1].data); t[p].sum=t[p<<1].sum+t[p<<1|1].sum; } void add2(int p,int l,int r,int k)//区间修改 { if(l<=t[p].l && t[p].r<=r) { t[p].sum=t[p].sum+k*(t[p].r-t[p].l+1); t[p].data=t[p].data+k; t[p].lazy=t[p].lazy+k; return; } pushdown(p); int mid=t[p].l+t[p].r>>1; if(l<=mid) add2(p<<1,l,r,k); if(r>mid) add2(p<<1|1,l,r,k); t[p].data=max(t[p<<1].data,t[p<<1|1].data); t[p].sum=t[p<<1].sum+t[p<<1|1].sum; } int querymax(int p,int l,int r)//区间查询最大值 { if(l<=t[p].l&&t[p].r<=r) return t[p].data; pushdown(p); int mid=t[p].l+t[p].r>>1; int ret=-inf; if(l<=mid) ret=max(ret,querymax(p<<1,l,r)); if(r>mid) ret=max(ret,querymax(p<<1|1,l,r)); return ret; } int querysum(int p,int l,int r)//区间求和查询 { if(l<=t[p].l && t[p].r<=r) return t[p].sum; pushdown(p); int mid=t[p].l+t[p].r>>1; int ret=0; if(l<=mid) ret+=querysum(p<<1,l,r); if(r>mid) ret+=querysum(p<<1|1,l,r); return ret; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<n;i++) { int u,v; cin>>u>>v; point[u].G.push_back(v); point[v].G.push_back(u); } dfs1(1,0); dfs2(1,1); for(int i=1;i<=n;i++) val[point[i].dfn]=a[i]; build(1,1,n); while(m--) { int op; cin>>op; if(op==1)//单点修改 { int u,t; cin>>u>>t; add1(1,point[u].dfn,t); a[u]+=t; } if(op==2)//子树修改 { int u,t; cin>>u>>t; add2(1,point[u].dfn,point[u].dfn+point[u].siz-1,t); } if(op==3)//路径修改 { int u,v,t; cin>>u>>v>>t; while(point[u].top!=point[v].top) { if(point[point[u].top].dep>point[point[v].top].dep) swap(u,v); add2(1,point[point[v].top].dfn,point[v].dfn,t); v=point[point[v].top].fath; } if(point[u].dep>point[v].dep) swap(u,v); add2(1,point[u].dfn,point[v].dfn,t); } if(op==4)//路径最大值查询 { int u,v; cin>>u>>v; int ans=-inf; while(point[u].top!=point[v].top) { if(point[point[u].top].dep>point[point[v].top].dep) swap(u,v); ans=max(ans,querymax(1,point[point[v].top].dfn,point[v].dfn)); v=point[point[v].top].fath; } if(point[u].dep>point[v].dep) swap(u,v); ans=max(ans,querymax(1,point[u].dfn,point[v].dfn)); cout<<ans<<"\n"; } if(op==5)//路径和查询 { int u,v; cin>>u>>v; int ans=0; while(point[u].top!=point[v].top) { if(point[point[u].top].dep>point[point[v].top].dep) swap(u,v); ans+=querysum(1,point[point[v].top].dfn,point[v].dfn); v=point[point[v].top].fath; } if(point[u].dep>point[v].dep) swap(u,v); ans+=querysum(1,point[u].dfn,point[v].dfn); cout<<ans<<"\n"; } if(op==6)//子树最大值查询 { int u; cin>>u; int ans=querymax(1,point[u].dfn,point[u].dfn+point[u].siz-1); cout<<ans<<"\n"; } if(op==7)//子树和查询 { int u; cin>>u; int ans=querysum(1,point[u].dfn,point[u].dfn+point[u].siz-1); cout<<ans<<"\n"; } } return 0; }#include <bits/stdc++.h> #define int long long #define inf 0x3f3f3f3f3f3f3f3f using namespace std; const int N=1e5+5; int a[N],n,m; struct node { int l,r,data,sum,lazy; }t[N<<2]; //建树 void build(int p,int l,int r) { t[p].l=l,t[p].r=r; t[p].lazy=0; if(l==r) { t[p].data=a[l]; t[p].sum=a[l]; return; } int mid=l+r>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); t[p].data=max(t[p<<1].data,t[p<<1|1].data); t[p].sum=t[p<<1].sum+t[p<<1|1].sum; } // 传懒标记 void pushdown(int p) { if(t[p].lazy) { //更新左子树 t[p<<1].sum+=t[p].lazy*(t[p<<1].r-t[p<<1].l+1); t[p<<1].data+=t[p].lazy; t[p<<1].lazy+=t[p].lazy; //更新右子树 t[p<<1|1].sum+=t[p].lazy*(t[p<<1|1].r-t[p<<1|1].l+1); t[p<<1|1].data+=t[p].lazy; t[p<<1|1].lazy+=t[p].lazy; t[p].lazy=0; } } // 单点修改 void add1(int p,int x,int k) { if(t[p].l==t[p].r) { t[p].data+=k; t[p].sum+=k; return; } pushdown(p); int mid=t[p].l+t[p].r>>1; if(x<=mid) add1(p<<1,x,k); else add1(p<<1|1,x,k); t[p].data=max(t[p<<1].data,t[p<<1|1].data); t[p].sum=t[p<<1].sum+t[p<<1|1].sum; } //区间查询最大值 int query1(int p,int l,int r) { if(l<=t[p].l&&t[p].r<=r) return t[p].data; pushdown(p); int mid=t[p].l+t[p].r>>1; int ret=-inf; if(l<=mid) ret=max(ret,query1(p<<1,l,r)); if(r>mid) ret=max(ret,query1(p<<1|1,l,r)); return ret; } //区间修改 void add2(int p,int l,int r,int k) { if(l<=t[p].l&&t[p].r<=r) { t[p].sum+=k*(t[p].r-t[p].l+1); t[p].data+=k; t[p].lazy+=k; return; } pushdown(p); int mid=t[p].l+t[p].r>>1; if(l<=mid) add2(p<<1,l,r,k); if(r>mid) add2(p<<1|1,l,r,k); t[p].data=max(t[p<<1].data,t[p<<1|1].data); t[p].sum=t[p<<1].sum+t[p<<1|1].sum; } //区间求和查询 int query2(int p,int l,int r) { if(l<=t[p].l&&t[p].r<=r) return t[p].sum; pushdown(p); int mid=t[p].l+t[p].r>>1; int ret=0; if(l<=mid) ret+=query2(p<<1,l,r); if(r>mid) ret+=query2(p<<1|1,l,r); return ret; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; build(1,1,n); for(int i=1;i<=m;i++) { int op; cin>>op; if(op==1)//单点修改 { int x,k; cin>>x>>k; add1(1,x,k); } else if(op==2)//区间查询最大值 { int l,r; cin>>l>>r; cout<<query1(1,l,r)<<"\n"; } else if(op==3)//区间修改 { int l,r,k; cin>>l>>r>>k; add2(1,l,r,k); } else if(op==4)//区间求和查询 { int l,r; cin>>l>>r; cout<<query2(1,l,r)<<"\n"; } } return 0; } -
通过的题目
- A0061
- P1
- edu001
- G0037
- A0096
- A0001
- A0002
- A0003
- A0004
- A0005
- A0006
- A0007
- A0008
- A0009
- A0010
- A0011
- A0012
- A0013
- A0014
- A0015
- A0016
- A0017
- A0018
- A0019
- A0020
- A0021
- A0022
- A0023
- A0024
- A0025
- A0026
- A0053
- A0027
- A0028
- A0029
- A0030
- A0031
- A0032
- A0033
- A0034
- A0035
- A0036
- A0038
- A0039
- A0040
- A0041
- A0042
- A0043
- A0044
- A0045
- A0046
- A0047
- A0049
- A0050
- A0051
- A0052
- CSPJ2020T1
- CSPJ2020T2
- CSPJ2022T1
- A0054
- A0055
- A0056
- A0057
- A0058
- A0059
- A0060
- A0062
- A0063
- A0064
- A0065
- A0066
- A0067
- NOIPS2012A
- NOIP2011J2
- A0068
- A0069
- A0070
- A0071
- A0072
- NOIP2008
- A0074
- A0075
- A0076
- NOIPS2011T4
- A0077
- A0078
- A0079
- A0080
- A0081
- edu003
- A0082
- NOIPJ1999A
- NOIPJ2008A
- 188
- CSPJ2021A
- CSPS2019A
- CSPJ2023A
- NOIPJ2002D
- NOIP2005A
- 201
- P1056
- edu004
- edu006
- edu007
- edu008
- edu009
- edu010
- edu011
- edu012
- edu013
- edu015
- CSPJ2024T1
- A0085
- A0086
- NOIP2015A
- NOIPJ2014A
- NOIPJ2018A
- A0087
- G0036
- A0090
- A0091
- A0092
- A0093
- A0095
- A0097
- A0098
- A0099
- A0101
- A0104
- edu3001
- edu3021
- edu3004
- edu3005
- edu2001
- edu3006
- edu3008
- edu2002
- edu2003
- edu2004
- edu1001
- edu1005
- edu1006
- edu1007
- edu1008
- edu2007
- edu2008
- edu2009
- edu2010
- G0086
- edu2011
- edu2012
- edu2005
- G0085
- edu2006
- G0097
- edu2020
- edu2023
- G0087
- edu2025
- edu2026
- G0098
- G0099
- edu2028
- edu2029
- edu2030
- edu2050
- edu2051
- edu2031
- edu2060
- G0104
- edu2013
- edu2014
- edu2015
- edu2016
- edu0014
- AT0101
- AT0102
- AT0103
- AT0104
- AT0105
- AT0106
- AT0107
- AT0108
- AT0109
- AT0110
- AT0118
- edu2070
- edu2071
- edu2072
- edu2073
- edu2074
- edu2075
- edu2076
- YT0001
- edu3024
- edu3023
- edu3030
- edu3031
- edu3010
- edu3011
- edu3050
- M0001
- M0002
- M0003
- M0004
- edu3060
- edu3063
- edu4001
- edu3070
-
最近活动
题目标签
- 教程
- 45
- atcoder
- 11
- dp
- 11
- stl
- 7
- 其他
- 6
- 高精度
- 5
- CSP-J
- 4
- NOIP
- 3
- 语法
- 3
- A
- 3
- 搜索
- 3
- 枚举
- 3
- 2015
- 2
- 2020
- 2
- NOIP 普及组
- 2
- NOIP 提高组
- 2
- 动态规划
- 2
- 模板题
- 2
- 1
- 1
- 2002
- 1