线段树单点更新，区间最大值,zkw线段树
先留下板子，后填坑；
#include <cstdio>
#include <cstring>
#include <cctype>
#include <string>
#include <set>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define mod 10000007
#define debug() puts("what the ***!!!")
#define N 200200
#define M 1000000
#define ll long long
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1 //位运算，|可以理解为+
int MAX[4*N];
void pushup(int rt)//更新该节点维护的值,求和
{
MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
}
void build(int l,int r,int rt)//建立线段树
{
if(l==r)
{
scanf("%d",&MAX[rt]);
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
void update(int p,int sc,int l,int r,int rt)//单点更新
{
if(l==r)
{
MAX[rt]=sc;
return;
}
int m=(l+r)>>1;
if(p<=m)
update(p,sc,lson);
else
update(p,sc,rson);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt)//要查询的区间和当前的左右节点和根节点
{
if(L<=l&&r<=R)//[l,r]∈[L,R]
{
return MAX[rt];
}
int m=(l+r)>>1;//找中间点
int ret=0;
if(L<=m) ret=max(ret,query(L,R,lson));
if(R>m) ret=max(ret,query(L,R,rson));
return ret;
}
int main()
{
int n,m,a,b;
char s[5];
while(~scanf("%d%d",&n,&m))
{
mem(MAX,0);
build(1,n,1);
while(m--)
{
scanf("%s%d%d",s,&a,&b);
if(s[0]=='Q')
printf("%d\n",query(a,b,1,n,1));
if(s[0]=='U')
update(a,b,1,n,1);
}
}
return 0;
}
zkw
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<iostream>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define mod 10000007
#define debug() puts("what the ***!!!")
#define ll long long
using namespace std;
const int N=1000000+20;
int M,n,m,tree[N<<2];
void pushup(int i)//向上更新
{
tree[i]=max(tree[i<<1],tree[i<<1|1]);
}
void update(int x,int v)//单点修改，把x的值变成v
{
for(tree[x+=M]=v,x>>=1; x; x>>=1)
pushup(x);
}
int query(int l,int r)//求[l~r]的最大值
{
int ans=0;
//l^r^1判断是否是兄弟节点，>0时是兄弟节点
//是兄弟是退出循环
for(l=l+M-1,r=r+M+1; l^r^1; l>>=1,r>>=1)
{
//l&1^1,r&1分别判断偶数和奇数
if(l&1^1) ans=max(ans,tree[l^1]);//l+1
if(r&1) ans=max(ans,tree[r^1]);//r-1
}
return ans;
}
void build()
{
for(M=1; M<n; M<<=1);
for(int i=M+1; i<=M+n; i++)
scanf("%d",&tree[i]);
for(int i=M; i>=1; i--)
pushup(i);
}
int main()
{
char op[10];
int a,b;
while(~scanf("%d%d",&n,&m))
{
build();
while(m--)
{
scanf("%s%d%d",op,&a,&b);
if(op[0]=='Q')
printf("%d\n",query(a,b));
else
update(a,b);
}
}
return 0;
}
1：区间更新与区间求和
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 400010
#define LL long long
LL sum[N],lazy[N];
///向上更新求和
void pushUp(int root){
sum[root]=sum[root<<1] + sum[(root<<1)+1];
}
///向下更新求和
void pushDown(int root,int len){
lazy[root<<1]+=lazy[root];
lazy[(root<<1)+1]+=lazy[root];
sum[root<<1]+=(len-(len>>1))*lazy[root];
sum[(root<<1)+1]+=(len>>1)*lazy[root];
lazy[root]=0;
}
///建树
void build(int l,int r,int root){
lazy[root]=0;
if(l==r){
scanf("%I64d",&sum[root]);
return;
}
int m = (l+r)>>1;
build(l,m,root<<1);
build(m+1,r,(root<<1)+1);
pushUp(root);
}
///在（l,r）区间内，根节点为root，将（L,R）区间的每个数 +c
void update(int L,int R,long long c,int l,int r,int root){
if(L<=l&&R>=r){
lazy[root]+=c;
sum[root]+=c*(r-l+1);
return;
}
if(lazy[root]) pushDown(root,r-l+1);
int m = (l+r)>>1;
if(L<=m) update(L,R,c,l,m,root<<1);
if(R>m) update(L,R,c,m+1,r,(root<<1)+1);
pushUp(root);
}
///在（l,r）区间内，根节点为root，求（L,R）区间的数的和
LL query(int L,int R,int l,int r,int root){
if(L<=l&&R>=r) return sum[root];
if(lazy[root]){
pushDown(root,r-l+1);
}
int m=(l+r)>>1;
LL ans=0;
if(L<=m) ans+=query(L,R,l,m,root<<1);
if(R>m) ans+=query(L,R,m+1,r,(root<<1)+1);
return ans;
}
int main(){
int n,q,a,b;
long long c;
char ch;
scanf("%d%d",&n,&q);
build(1,n,1);
while(q--){
getchar();
scanf("%c",&ch);
if(ch=='Q'){
scanf("%d%d",&a,&b);
printf("%I64d\n",query(a,b,1,n,1));
}else{
scanf("%d%d%I64d",&a,&b,&c);
update(a,b,c,1,n,1);
}
}
return 0;
}
2：区间更新与区间求最值
注：最大值与最小值函数经测试都具有可行性，可自行测试
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define N 4000001
#define INF 0x3f3f3f3f
int Min[N];
int Max[N];
int lazy[N];
bool vis[N];
///向上更新最值
void PushUp(int root){
Min[root]=min(Min[root<<1],Min[(root<<1)+1]);
Max[root]=max(Max[root<<1],Max[(root<<1)+1]);
}
///向下更新最值
void PushDown(int root,int c){
Min[root<<1]=Min[(root<<1)+1]=lazy[root];
Max[root<<1]=Max[(root<<1)+1]=lazy[root];
vis[root<<1]=vis[(root<<1)+1]=true;
lazy[root<<1]=lazy[(root<<1)+1]=lazy[root];
vis[root]=false;
}
///建树，根节点为root，区间为（l,r）
void build(int l,int r,int root){
if(l==r){
scanf("%d",&Min[root]);
Max[root]=Min[root];
return;
}
int m = (l+r)>>1;
build(l,m,root<<1);
build(m+1,r,(root<<1)+1);
PushUp(root);
}
///在（l,r）区间内，根节点为root，求（L,R）区间的最小值
int getMin(int L,int R,int l,int r,int root){
// if(vis[root]) return Min[root];
if(L<=l&&R>=r) return Min[root];
if(vis[root]) PushDown(root,lazy[root]);
int m = (l+r)>>1,ret=INF;
if(L<=m) ret = min(ret,getMin(L,R,l,m,root<<1));
if(R>m) ret = min(ret,getMin(L,R,m+1,r,(root<<1)+1));
return ret;
}
///在（l,r）区间内，根节点为root，求（L,R）区间的最大值
int getMax(int L,int R,int l,int r,int root){
//if(vis[root]) return Max[root];
if(L<=l&&R>=r) return Max[root];
if(vis[root]) PushDown(root,lazy[root]);
int m = (l+r)>>1,ret=0;
if(L<=m) ret = max(ret,getMax(L,R,l,m,root<<1));
if(R>m) ret = max(ret,getMax(L,R,m+1,r,(root<<1)+1));
return ret;
}
///在（l,r）区间内，根节点为root，将（L,R）区间的数更新为 c
void update(int L,int R,int c,int l,int r,int root){
if(L<=l&&R>=r){
Min[root]=Max[root]=c;
lazy[root]=c;
vis[root]=true;
return ;
}
if(vis[root]) PushDown(root,c);
int m = (l+r)>>1;
if(L<=m) update(L,R,c,l,m,root<<1);
if(R>m) update(L,R,c,m+1,r,(root<<1)+1);
PushUp(root);
}
int main(){
int n,m,a,b,c,t;
while(scanf("%d",&n)!=EOF){
memset(vis,false,sizeof(vis));
build(1,n,1);
scanf("%d\n",&m);
while(m--){
scanf("%d",&t);
if(t==0){
scanf("%d%d%d",&a,&b,&c);
update(a,b,c,1,n,1);
}else{
scanf("%d%d",&a,&b);
printf("%d\n",getMin(a,b,1,n,1));
}
}
}
return 0;
}
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define N 4000001
#define INF 0x3f3f3f3f
int Min[N];
int Max[N];
int lazy[N];
bool vis[N];
///向上更新最值
void PushUp(int root){
Min[root]=min(Min[root<<1],Min[(root<<1)+1]);
Max[root]=max(Max[root<<1],Max[(root<<1)+1]);
}
///向下更新最值
void PushDown(int root,int c){
Min[root<<1]=Min[(root<<1)+1]=lazy[root];
Max[root<<1]=Max[(root<<1)+1]=lazy[root];
vis[root<<1]=vis[(root<<1)+1]=true;
lazy[root<<1]=lazy[(root<<1)+1]=lazy[root];
vis[root]=false;
}
///建树，根节点为root，区间为（l,r）
void build(int l,int r,int root){
if(l==r){
scanf("%d",&Min[root]);
Max[root]=Min[root];
return;
}
int m = (l+r)>>1;
build(l,m,root<<1);
build(m+1,r,(root<<1)+1);
PushUp(root);
}
///在（l,r）区间内，根节点为root，求（L,R）区间的最小值
int getMin(int L,int R,int l,int r,int root){
// if(vis[root]) return Min[root];
if(L<=l&&R>=r) return Min[root];
if(vis[root]) PushDown(root,lazy[root]);
int m = (l+r)>>1,ret=INF;
if(L<=m) ret = min(ret,getMin(L,R,l,m,root<<1));
if(R>m) ret = min(ret,getMin(L,R,m+1,r,(root<<1)+1));
return ret;
}
///在（l,r）区间内，根节点为root，求（L,R）区间的最大值
int getMax(int L,int R,int l,int r,int root){
//if(vis[root]) return Max[root];
if(L<=l&&R>=r) return Max[root];
if(vis[root]) PushDown(root,lazy[root]);
int m = (l+r)>>1,ret=0;
if(L<=m) ret = max(ret,getMax(L,R,l,m,root<<1));
if(R>m) ret = max(ret,getMax(L,R,m+1,r,(root<<1)+1));
return ret;
}
///在（l,r）区间内，根节点为root，将（L,R）区间的数更新为 c
void update(int L,int R,int c,int l,int r,int root){
if(L<=l&&R>=r){
Min[root]=Max[root]=c;
lazy[root]=c;
vis[root]=true;
return ;
}
if(vis[root]) PushDown(root,c);
int m = (l+r)>>1;
if(L<=m) update(L,R,c,l,m,root<<1);
if(R>m) update(L,R,c,m+1,r,(root<<1)+1);
PushUp(root);
}
int main(){
int n,m,a,b,t;
char c;
while(scanf("%d%d",&n,&m)!=EOF){
memset(vis,false,sizeof(vis));
build(1,n,1);
while(m--){
getchar();
scanf("%c%d%d",&c,&a,&b);
if(c=='U'){
update(a,a,b,1,n,1);
}else{
printf("%d\n",getMax(a,b,1,n,1));
}
}
}
return 0;
}
投递零跑科技等公司10个岗位 >
查看9道真题和解析
腾讯公司福利 465人发布