算法笔记
模板：
#include<bits/stdc++.h> using namespace std; #define ll long long #define ls rt<<1,l,m #define rs rt<<1|1,m+1,r #define pb push_back const int INF=0x3f3f3f3f; const int N=1e6+5; int tree[4*N]; int lazy[4*N]; //将子节点值更新到父亲节点 /*对于区间求和而言*/ void push_up(int rt) { tree[rt]=tree[rt<<1]+tree[rt<<1|1]; } //节点懒惰标记下推 /*对于区间求和而言*/ void push_down(int rt,int len) { tree[rt<<1]+=lazy[rt]*(len-(len>>1)); lazy[rt<<1]+=lazy[rt]; tree[rt<<1|1]+=lazy[rt]*(len>>1); lazy[rt<<1|1]+=lazy[rt]; lazy[rt]=0; } //建树 void build(int rt,int l,int r) { if(l==r) { scanf("%d",&tree[rt]);//最好用scanf,防止超时 return ; } int m=(l+r)>>1; build(ls); build(rs); push_up(rt); } //单节点更新 void update(int p,int delta,int rt,int l,int r) { if(l==r) { tree[rt]+=delta; return ; } int m=(l+r)>>1; if(p<=m)update(p,delta,ls); else update(p,delta,rs); push_up(rt); } //区间更新 void Update(int L,int R,int delta,int rt,int l,int r) { if(L<=l&&r<=R) { tree[rt]+=(r-l+1)*delta; lazy[rt]+=delta; return ; } if(lazy[rt])push_down(rt,r-l+1); int m=(l+r)>>1; if(L<=m)Update(L,R,delta,ls); if(R>m)Update(L,R,delta,rs); push_up(rt); } //区间查询 /*对于区间求和而言*/ int query(int L,int R,int rt,int l,int r) { if(L<=l&&r<=R)return tree[rt]; if(lazy[rt])push_down(rt,r-l+1); int m=(l+r)>>1,res=0; if(L<=m)res+=query(L,R,ls); if(R>m)res+=query(L,R,rs); return res; }
POJ - 3468A Simple Problem with Integers
代码：
#include<iostream> #include<cstdio> using namespace std; #define ll long long #define ls rt<<1,l,m #define rs rt<<1|1,m+1,r #define pb push_back const int INF=0x3f3f3f3f; const int N=1e5+5; ll tree[4*N]; ll lazy[4*N]; void push_up(int rt) { tree[rt]=tree[rt<<1]+tree[rt<<1|1]; } void push_down(int rt,int len) { tree[rt<<1]+=lazy[rt]*(len-(len>>1)); lazy[rt<<1]+=lazy[rt]; tree[rt<<1|1]+=lazy[rt]*(len>>1); lazy[rt<<1|1]+=lazy[rt]; lazy[rt]=0; } void build(int rt,int l,int r) { if(l==r) { scanf("%lld",&tree[rt]); return ; } int m=(l+r)>>1; build(ls); build(rs); push_up(rt); } void Update(int L,int R,int delta,int rt,int l,int r) { if(L<=l&&r<=R) { tree[rt]+=delta*(r-l+1); lazy[rt]+=delta; return; } if(lazy[rt])push_down(rt,r-l+1); int m=(l+r)>>1; if(L<=m)Update(L,R,delta,ls); if(R>m)Update(L,R,delta,rs); push_up(rt); } ll query(int L,int R,int rt,int l,int r) { if(L<=l&&r<=R)return tree[rt]; if(lazy[rt])push_down(rt,r-l+1); int m=(l+r)>>1; ll res=0; if(L<=m)res+=query(L,R,ls); if(R>m)res+=query(L,R,rs); return res; } int main() { /*ios::sync_with_stdio(false); cin.tie(0);*/ int n,q; scanf("%d%d",&n,&q); build(1,1,n); while(q--) { getchar(); char s; int a,b,c; scanf("%c",&s); if(s=='Q') { scanf("%d%d",&a,&b); printf("%lld ",query(a,b,1,1,n)); } else { scanf("%d%d%d",&a,&b,&c); Update(a,b,c,1,1,n); } } return 0; }
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define ls rt<<1,l,m #define rs rt<<1|1,m+1,r #define mem(a,b) memset(a,b,sizeof(a)) const int N=1e5+5; int lazy[4*N]; int tree[4*N]; void push_up(int rt) { tree[rt]=tree[rt<<1]+tree[rt<<1|1]; } void push_down(int rt,int len) { lazy[rt<<1]=lazy[rt]; lazy[rt<<1|1]=lazy[rt]; tree[rt<<1]=lazy[rt]*(len-(len>>1)); tree[rt<<1|1]=lazy[rt]*(len>>1); lazy[rt]=0; } void build(int rt,int l,int r) { lazy[rt]=0; if(l==r) { tree[rt]=1; return ; } int m=(l+r)>>1; build(ls); build(rs); push_up(rt); } /*void update(int p,int delta,int rt,int l,int r) { if(l==r) { tree[rt]=delta; return ; } int m=(l+r)>>1; if(p<=m)update(p,delta,ls); else update(p,delta,rs); push_up(rt); }*/ void Update(int L,int R,int delta,int rt,int l,int r) { if(L<=l&&r<=R) { tree[rt]=delta*(r-l+1); lazy[rt]=delta; return ; } if(lazy[rt])push_down(rt,r-l+1); int m=(l+r)>>1; if(L<=m)Update(L,R,delta,ls); if(R>m)Update(L,R,delta,rs); push_up(rt); } int query(int L,int R,int rt,int l,int r) { if(L<=l&&r<=R)return tree[rt]; if(lazy[rt])push_down(rt,r-l+1); int m=(l+r)>>1,ans=0; if(L<=m)ans+=query(L,R,ls); if(R>m)ans+=query(L,R,rs); return ans; } int main() { /*ios::sync_with_stdio(false); cin.tie(0);*/ int T,n,q,l,r,a; scanf("%d",&T); int cs=0; while(T--) { scanf("%d",&n); build(1,1,n); scanf("%d",&q); while(q--) { scanf("%d%d%d",&l,&r,&a); Update(l,r,a,1,1,n); } printf("Case %d: The total value of the hook is %d. ",++cs,query(1,n,1,1,n)); //for(int i=1;i<=2*n;i++)cout<<tree[i]<<endl; } return 0; }
#include<bits/stdc++.h> using namespace std; #define long long #define pb push_back #define ls rt<<1,l,m #define rs rt<<1|1,m+1,r #define mem(a,b) memset(a,b,sizeof(a)) const int N=8e3+5; int vis[N]; int ans[N]; int lazy[N<<2]; void push_down(int rt) { lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt]; lazy[rt]=-1; } void update(int L,int R,int c,int rt,int l,int r) { if(L<=l&&r<=R) { lazy[rt]=c; return ; } if(lazy[rt]==c)return ; if(lazy[rt]!=-1)push_down(rt); int m=(l+r)>>1; if(L<=m)update(L,R,c,ls); if(R>m)update(L,R,c,rs); } void query(int L,int R,int rt,int l,int r) { if(lazy[rt]!=-1) { for(int i=l;i<=r;i++) vis[i]=lazy[rt]; return ; } if(l!=r&&lazy[rt]==-1) { int m=(l+r)>>1; if(L<=m)query(L,R,ls); if(R>m)query(L,R,rs); } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n,l,r,c; while(cin>>n) { mem(lazy,-1); mem(vis,-1); mem(ans,0); for(int i=0;i<n;i++)cin>>l>>r>>c,update(l+1,r,c,1,1,8000); //cout<<1<<endl; query(1,8000,1,1,8000); int i=1; while(i<N) { if(vis[i]==-1){ i++; continue; } int c=vis[i]; while(i<N&&vis[i]==c)i++; ans[c]++; } for(int i=0;i<N;i++)if(ans[i])cout<<i<<' '<<ans[i]<<endl; cout<<endl; } return 0; }
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<queue> #include<map> #include<set> using namespace std; #define ll long long #define pb push_back #define ls rt<<1,l,m #define rs rt<<1|1,m+1,r #define mem(a,b) memset(a,b,sizeof(a)) const int N=5e4+5; const int INF=0x3f3f3f3f; struct node { int mx,mn; }tree[N<<2]; void push_up(int rt) { tree[rt].mx=max(tree[rt<<1].mx,tree[rt<<1|1].mx); tree[rt].mn=min(tree[rt<<1].mn,tree[rt<<1|1].mn); } void build(int rt,int l,int r) { if(l==r) { scanf("%d",&tree[rt].mx); tree[rt].mn=tree[rt].mx; return ; } int m=(l+r)>>1; build(ls); build(rs); push_up(rt); } int querymx(int L,int R,int rt,int l,int r) { if(L<=l&&r<=R)return tree[rt].mx; int m=(l+r)>>1,ans=0; if(L<=m)ans=max(ans,querymx(L,R,ls)); if(R>m)ans=max(ans,querymx(L,R,rs)); return ans; } int querymn(int L,int R,int rt,int l,int r) { if(L<=l&&r<=R)return tree[rt].mn; int m=(l+r)>>1,ans=INF; if(L<=m)ans=min(ans,querymn(L,R,ls)); if(R>m)ans=min(ans,querymn(L,R,rs)); return ans; } int main() { /*ios::sync_with_stdio(false); cin.tie(0);*/ int n,q,l,r; scanf("%d%d",&n,&q); build(1,1,n); while(q--) { scanf("%d%d",&l,&r); printf("%d ",querymx(l,r,1,1,n)-querymn(l,r,1,1,n)); } return 0; }
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define ls rt<<1,l,m #define rs rt<<1|1,m+1,r #define mem(a,b) memset(a,b,sizeof(a)) const int N=1e5+5; ll tree[N<<2]; void push_up(int rt) { tree[rt]=tree[rt<<1]+tree[rt<<1|1]; } void build(int rt,int l,int r) { if(l==r) { scanf("%lld",&tree[rt]); return ; } int m=(l+r)>>1; build(ls); build(rs); push_up(rt); } void update(int L,int R,int rt,int l,int r) { if(l==r) { tree[rt]=(int)sqrt(tree[rt]); return ; } int m=(l+r)>>1; if(L<=m)update(L,R,ls); if(R>m)update(L,R,rs); push_up(rt); } ll query(int L,int R,int rt,int l,int r) { if(L<=l&&r<=R)return tree[rt]; int m=(l+r)>>1; ll ans=0; if(L<=m)ans+=query(L,R,ls); if(R>m)ans+=query(L,R,rs); return ans; } int main() { int n,m,t,l,r,cs=0; while(~scanf("%d",&n)) { build(1,1,n); scanf("%d",&m); printf("Case #%d: ",++cs); while(m--) { scanf("%d%d%d",&t,&l,&r); if(l>r)swap(l,r); if(t==0) { if(query(l,r,1,1,n)!=r-l+1)update(l,r,1,1,n); } else { printf("%lld ",query(l,r,1,1,n)); } } puts(""); } return 0; }
线段树区间合并
#include<bits/stdc++.h> using namespace std; #define pb push_back #define ls rt<<1,l,m #define rs rt<<1|1,m+1,r #define mem(a,b) memset(a,b,sizeof(a)) const int N=5e4+5; struct tree{ int ll,rr,len;//ll表示以当前区间左端点为左端点最长连续区间的长度,rr表示以当前区间右端点为右端点最长连续区间的长度，len表示当前区间的长度 }tree[N<<2]; void push_up(int rt){ if(tree[rt<<1].ll==tree[rt<<1].len)tree[rt].ll=tree[rt<<1].ll+tree[rt<<1|1].ll; else tree[rt].ll=tree[rt<<1].ll; if(tree[rt<<1|1].rr==tree[rt<<1|1].len)tree[rt].rr=tree[rt<<1|1].rr+tree[rt<<1].rr; else tree[rt].rr=tree[rt<<1|1].rr; } void build(int rt,int l,int r){ tree[rt].ll=tree[rt].rr=tree[rt].len=r-l+1; if(l==r)return ; int m=(l+r)>>1; build(ls); build(rs); } void update(int p,int v,int rt,int l,int r){ if(l==r){ tree[rt].ll=tree[rt].rr=v; return ; } int m=(l+r)>>1; if(p<=m)update(p,v,ls); else update(p,v,rs); push_up(rt); } int query(int p,int rt,int l,int r){ if(rt==1){ if(l+tree[rt].ll-1>=p)return tree[rt].ll; if(r-tree[rt].rr+1<=p)return tree[rt].rr; } else{ if(l+tree[rt].ll-1>=p)return tree[rt].ll+tree[rt-1].rr; if(r-tree[rt].rr+1<=p)return tree[rt].rr+tree[rt+1].ll; } if(l==r)return 0; int m=(l+r)>>1; if(p<=m)return query(p,ls); else return query(p,rs); } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m,x; char c; while(cin>>n>>m){ stack<int>s; build(1,1,n); while(m--){ cin>>c; if(c=='D'){ cin>>x; s.push(x); update(x,0,1,1,n); } else if(c=='Q'){ cin>>x; cout<<query(x,1,1,n)<<endl; } else{ x=s.top(); s.pop(); update(x,1,1,1,n); } } } return 0; }
dfs序+线段树
先将每个节点按dfs序的in[u]映射到线段上，然后将线段映射成线段树
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define ls rt<<1,l,m #define rs rt<<1|1,m+1,r #define mem(a,b) memset(a,b,sizeof(a)) const int N=5e4+5; int head[N]; int in[N]; int ind[N]; int out[N]; int tree[N<<2]; int lazy[N<<2]; struct edge{ int to,next; }edge[N]; int cnt=0; void add_edge(int u,int v){ edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt++; } void dfs(int u,int &x){ in[u]=x; for(int i=head[u];~i;i=edge[i].next)dfs(edge[i].to,++x); out[u]=x; } void push_down(int rt){ if(lazy[rt]){ tree[rt<<1]=lazy[rt]; tree[rt<<1|1]=lazy[rt]; lazy[rt<<1]=lazy[rt]; lazy[rt<<1|1]=lazy[rt]; lazy[rt]=0; } } void update(int L,int R,int v,int rt,int l,int r){ if(L<=l&&r<=R){ tree[rt]=v; lazy[rt]=v; return ; } push_down(rt); int m=(l+r)>>1; if(L<=m)update(L,R,v,ls); if(R>m)update(L,R,v,rs); } int query(int p,int rt,int l,int r){ if(l==r)return tree[rt]; push_down(rt); int m=(l+r)>>1; if(p<=m)return query(p,ls); else return query(p,rs); } int main(){ ios::sync_with_stdio(false); cin.tie(0); int T,cs=0; cin>>T; while(T--){ mem(head,-1); mem(ind,0); cnt=0; int n,rt,u,v,l,r,m; char c; cin>>n; for(int i=1;i<n;i++){ cin>>u>>v; add_edge(v,u); ind[u]++; } for(int i=1;i<=n;i++)if(ind[i]==0)rt=i; int x=1; dfs(rt,x); mem(tree,-1); mem(lazy,0); cout<<"Case #"<<++cs<<":"<<endl; cin>>m; while(m--){ cin>>c; if(c=='C'){ cin>>l; cout<<query(in[l],1,1,n)<<endl; } else { cin>>l>>r; update(in[l],out[l],r,1,1,n); } } } return 0; }
线段树易错点：
1.push_down后记得push_up
2.区间修改或者查询应该有两个if判断if(L <= m); if(R > m);很容易写成if(L <= m); else ;这是不对的
3.lazy标记的修改很容易错