1.洛谷p1351?https://www.luogu.org/problem/show?pid=1531

//單點修改區(qū)間詢問 #include<iostream> #include<cstdio> #include<cstring>#define maxn 200001using namespace std; int n,m,x,y,z,ans1,ans2; char c; struct node {int l,r,sum,max; }tree[maxn<<2];inline int init() {int x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; }void build(int now,int l,int r) {tree[now].l=l;tree[now].r=r;if(l==r){tree[now].sum=tree[now].max=init();return;}int mid=(l+r)>>1;build(now<<1,l,mid);build(now<<1|1,mid+1,r);tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;tree[now].max=max(tree[now<<1].max,tree[now<<1|1].max); }int query(int now,int l,int r) {if(tree[now].l==l&&tree[now].r==r) return tree[now].max;int mid=(tree[now].l+tree[now].r)>>1;if(l>mid) return query(now<<1|1,l,r);else if(r<=mid) return query(now<<1,l,r);else return max(query(now<<1,l,mid),query(now<<1|1,mid+1,r)); }int serch(int now,int pos) {if(tree[now].l==pos&&tree[now].r==pos) return tree[now].sum;int mid=(tree[now].l+tree[now].r)>>1;if(pos<=mid) return serch(now<<1,pos);else if(pos>mid) serch(now<<1|1,pos); }void change(int now,int pos,int k) {int l=tree[now].l;int r=tree[now].r;if(l==pos&&r==pos){tree[now].sum=tree[now].max=k;return;}int mid=(tree[now].l+tree[now].r)>>1;if(pos>mid) change(now<<1|1,pos,k);if(pos<=mid) change(now<<1,pos,k);tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;tree[now].max=max(tree[now<<1].max,tree[now<<1|1].max); }int main() {n=init();m=init();build(1,1,n);for(int i=1;i<=m;i++){cin>>c;x=init();y=init();if(c=='Q'){printf("%d\n",query(1,x,y));}else if(serch(1,x)<y) change(1,x,y);}return 0; }

?

轉載于:https://www.cnblogs.com/L-Memory/p/6817937.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的线段树水题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。