给定一个长度为n的序列，共有q次操作，每次操作分为两种1和2
1、p x 将序号p处的值改为x
2、x 将序列中小于x的值变成x
思路：这道题大体上是一个线段树，用来维护区间最小值。操作1，每次将x与区间最小值进行比较，如果小的话就进行修改。比较麻烦的的是操作2，属于区间修改，一不小心就会T掉，区间修改最常用的就是lazy_tag：当我们要修改某个区间时，只需要修改该点的值tree[p]，而不去迭代修改其左右子树，并且用lazy[]去记录子节点的变化，等到下次查询到该子节点是，再去修改。（就相当于你生病了，开了点药方，但当前不抓药治疗，过几天再治疗，所以称为lazy！！！）
//区间修改 lazy tag #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; const int maxn = 2e5+5; ll a[maxn]; ll tree[maxn<<2]; ll lazy[maxn<<2]; void build(int p,int l,int r) // p:线段树的结点序号；l：维护的左区间；r：维护的右区间 { if (l==r) { tree[p]=a[l]; return ; } int mid =(l+r)>>1; build(p<<1,l,mid); //左子树 build(p<<1|1,mid+1,r); //右子树 tree[p] = min(tree[p<<1],tree[p<<1|1]); //维护区间的最小值 } void solve(int p,int l,int r,ll num) { if (tree[p]>=num) return ; tree[p] = num; lazy[p] = max(lazy[p],num); } void down(int p)//lazy_tag标记 { //左子树lazy大于父亲节点的lazy，那么就不用变 if (lazy[p]){ lazy[p<<1] = max(lazy[p],lazy[p<<1]); lazy[p<<1|1] = max(lazy[p],lazy[p<<1|1]); //tree[p]存储的是区间最小值,如果当前区间最小值大于lazy，就不用变;小于lazy,变成lazy即可 tree[p<<1] = max(tree[p<<1],lazy[p]); tree[p<<1|1] = max(tree[p<<1|1],lazy[p]); lazy[p] = 0; } } void change(int p,int l ,int r,int x,int num) //将下标为x的改为num { if (l==r){ tree[p] = num; return; } down(p);//将当前结点的更新信息传递给其左右子节点 int mid = (l+r)>>1; if (x<=mid) change(p<<1,l,mid,x,num); else change(p<<1|1,mid+1,r,x,num); tree[p] = min(tree[p<<1],tree[p<<1|1]); } ll print(int p,int l,int r,int x) { if (l==r) { return tree[p]; } down(p); //将当前结点的更新信息传递给其左右子节点 int mid = (l+r)>>1; if (x<=mid) print(p<<1,l,mid,x); else print(p<<1|1,mid+1,r,x); } int main() { int n,q; scanf("%d",&n); memset(a,0,sizeof(a)); memset(tree,0,sizeof(tree)); memset(lazy,0,sizeof(lazy)); for(int i=1;i<=n;i++) scanf("%I64d",&a[i]); build(1,1,n); scanf("%d",&q); while(q--) { int num; int p,x; scanf("%d",&num); if (num==1) { scanf("%d%d",&p,&x); change(1,1,n,p,x); } if (num==2) { scanf("%d",&x); solve(1,1,n,x); } } for(int i=1;i<=n;i++) printf("%I64d ",print(1,1,n,i)); return 0; }
Codeforces Round #576 (Div. 2)
原文：https://www.cnblogs.com/xiazhenbin/p/12451858.html