线段树2多加了个操作，pushdown就是用父节点的信息来下发到子节点进行更新，也即懒标记，用来区间修改
线段树的所有操作
pushup：子节点信息更新父节点信息
pushdown：父节点信息更新子节点信息
built：用堆的方式建立线段树
modify：修改一个值/一个区间的信息
query：询问一个区间的信息
pushup放在更新之后，pushdown放在更新之前
1.一个简单的整数问题2
这题之前用树状数组也可以做，现在用线段树来做一下
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; int w[N]; int n,m; struct Node { int l,r; ll sum,add; }tr[4*N]; void pushup(int u)//用子节点信息更新父节点信息 { tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum; } void pushdown(int u)//用父节点信息更新子节点信息 { auto &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;//根节点重新赋值0 } } void built(int u,int l,int r)//建立线段树 { if(l==r) tr[u]={l,r,w[l],0};//这个点的和等于w[l],add为0 else { tr[u]={l,r,0,0}; int mid=l+r>>1; built(u<<1,l,mid),built(u<<1|1,mid+1,r);//继续建左右子树 pushup(u);//更新一下父节点信息 } } void modify(int u,int l,int r,int d)//修改操作 { if(l<=tr[u].l&&r>=tr[u].r)//假如这个u区间已经在l~r里了，则直接修改 { tr[u].sum+=(ll)(tr[u].r-tr[u].l+1)*d;//区间每个数都加上d tr[u].add+=d;//这个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&&r>=tr[u].r) return tr[u].sum;//假如这个区间在l~r中了，则直接返回 pushdown(u);//先把父节点的信息更新给子节点里 ll ans=0; int mid=tr[u].l+tr[u].r>>1; if(l<=mid) ans=query(u<<1,l,r);//假如在左区间 if(r>mid) ans+=query(u<<1|1,l,r);//假如在右区间，则加上 return ans;//返回结果 } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&w[i]); built(1,1,n);//建立线段树 char op[2]; while(m--) { int l,r,d; scanf("%s%d%d",op,&l,&r); if(*op=='Q') printf("%lld\n",query(1,l,r));//询问则直接输出 else { scanf("%d",&d); modify(1,l,r,d);//修改 } } return 0; }
2.亚特兰蒂斯
这题拓展性不大，自己斟酌着看 ，比赛难想
微分思想，把x进行正方形切分，然后y值进行线段树进行求长度，每个长方形的面积S=(xi-xi-1)*len，然后把所有的面积加起来则为总面积
假如一个矩形，我们让其左边为+1，右边为-1
然后用线段树进行两个操作
1.将某个区间【l,r】+k
2.整个区间长度大于0的区间总长为多少？也即len
线段树要存的节点信息
cnt：当前区间整个被覆盖的个数
len：不考虑祖宗节点cnt的前提下，cnt>0的区间总长度
#include<bits/stdc++.h> using namespace std; const int N=1e4+10; int n; struct Segment//用来存横坐标 { double x,y1,y2; int k; bool operator< (const Segment &t)const//横坐标按照从小到大排序 { return x<t.x; } }seg[N*2]; struct Node//存y，也即线段树 { int l,r; int cnt;//记录当前区间有多少个 double len;//当前区间y的长度 }tr[8*N]; vector<double> ys;//用来离散化，把y值离散化到1~2*n中 void pushup(int u)//用子节点信息更新父节点信息 { if(tr[u].cnt) tr[u].len=ys[tr[u].r+1]-ys[tr[u].l];//假如当前区间被覆盖了，则加上对应的y的长度 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 built(int u,int l,int r)//建立线段树 { tr[u]={l,r,0,0};//刚开始没操作的长度与覆盖数都为0 if(l!=r) { int mid=l+r>>1; built(u<<1,l,mid),built(u<<1|1,mid+1,r);//建立左右区间 //pushup(u)这里不用也行，因为刚开始没有数的时候就是0 } } void modify(int u,int l,int r,int k)//修改某个区间的值 { if(tr[u].l>=l&&tr[u].r<=r)//假如当前区间在l~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 find(double y)//离散化，把y离散到坐标里 { return lower_bound(ys.begin(),ys.end(),y)-ys.begin();//用二分找出y的位置 } int main() { int T=1; while(scanf("%d",&n),n) { ys.clear();//清空上一层的状态 double x1,x2,y1,y2; for(int i=1,j=0;i<=n;i++) { scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); seg[j++]={x1,y1,y2,1},seg[j++]={x2,y1,y2,-1};//左边则+1，右边则-1，加到存x中的结构体中去 ys.push_back(y1),ys.push_back(y2);//把y也存进离散化里头 } //将y去重 sort(ys.begin(),ys.end()); ys.erase(unique(ys.begin(),ys.end()),ys.end()); built(1,0,ys.size()-2);//建立一颗线段树 sort(seg,seg+2*n);//将x从小到大排序 double res=0; for(int i=0;i<2*n;i++) { if(i) res+=tr[1].len*(seg[i].x-seg[i-1].x);//当i>0才能计算 modify(1,find(seg[i].y1),find(seg[i].y2)-1,seg[i].k);//修改线段树y中的值 } printf("Test case #%d\n",T++); printf("Total explored area: %.2lf\n\n",res); } return 0; }
3.维护序列
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
第一题的进阶版
需要记录两个pushdown的值，也即add与mul
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; int w[N]; int n,m,p; struct Node//线段树 { int l,r; int sum,add,mul; }tr[4*N]; 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;//总和等于原来的和*mul+数的多少*add t.mul=(ll)t.mul*mul%p;//新的mul等于原来的mul*mul t.add=((ll)t.add*mul+add)%p;//新的add=原来的add*mul+add } 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 built(int u,int l,int r)//用来建立线段树 { if(l==r) tr[u]={l,r,w[l],0,1}; else { tr[u]={l,r,0,0,1}; int mid=l+r>>1; built(u<<1,l,mid),built(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);//假如这个区间在l~r之间直接更新 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;//假如这个区间在l~r之间则直接返回sum pushdown(u);//把父节点信息传递到子节点中去 int mid=tr[u].l+tr[u].r>>1; int res=0; if(l<=mid) res=query(u<<1,l,r);//假如左边有这个区间 if(r>mid) res=(res+query(u<<1|1,l,r))%p;//假如右边也有这个区间则加上 return res;//返回答案 } int main() { scanf("%d%d",&n,&p); for(int i=1;i<=n;i++) scanf("%d",&w[i]); built(1,1,n);//建立线段树 scanf("%d",&m); int op,l,r,d; while(m--) { scanf("%d%d%d",&op,&l,&r); if(op==1) { scanf("%d",&d); modify(1,l,r,0,d);//乘d相当于加0乘d } else if(op==2) { scanf("%d",&d); modify(1,l,r,d,1);//加d相当于加d乘1 } else printf("%d\n",query(1,l,r));//输出询问 } return 0; }
