标签：return jia int 线段 tree mid sum
查找区间最大最小值
查看代码
#include<bits/stdc++.h>//维护最大最小值
#define int long long
using namespace std;
int n,q;
int tree1[4000000],tree2[4000000],a[1000000];
void build(int p,int l,int r)
{
if(l==r)
{
tree1[p]=a[l];
tree2[p]=a[l];
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
tree1[p]=max(tree1[p*2],tree1[p*2+1]);
tree2[p]=min(tree2[p*2],tree2[p*2+1]);
}
int calc1(int p,int l,int r,int x,int y)
{
if(x<=l&&y>=r)
{
return tree1[p];
}
int mid=(l+r)/2;
int ans=-LLONG_MAX;
if(x<=mid)ans=max(ans,calc1(p*2,l,mid,x,y));
if(y>mid)ans=max(ans,calc1(p*2+1,mid+1,r,x,y));
return ans;
}
int calc2(int p,int l,int r,int x,int y)
{
if(x<=l&&y>=r)
{
return tree2[p];
}
int mid=(l+r)/2;
int res=LLONG_MAX;
if(x<=mid)res=min(res,calc2(p*2,l,mid,x,y));
if(y>mid)res=min(res,calc2(p*2+1,mid+1,r,x,y));
return res;
}
signed main()
{
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,1,n);
for(int i=1;i<=q;i++)
{
int y,z;
cin>>y>>z;
cout<<calc1(1,1,n,y,z)-calc2(1,1,n,y,z)<<endl;
}
return 0;
}
区间修改和
查看代码
#include<bits/stdc++.h>//区间修改和
#define int long long
using namespace std;
int n,q,ff;
int tree[4000100],a[4000100],lazy[4000100];
void build(int p,int l,int r)
{
if(l==r)
{
tree[p]=a[l];
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
tree[p]=tree[p*2]+tree[p*2+1];
}
void pushdown(int p,int l,int r)
{
if(lazy[p]==0) return;
int mid=(l+r)/2;
tree[2*p]+=(mid-l+1)*lazy[p];
lazy[2*p]+=lazy[p];
tree[2*p+1]+=(r-mid)*lazy[p];
lazy[2*p+1]+=lazy[p];
lazy[p]=0;
}
void change(int p,int l,int r,int x,int y,int z)
{
if(y<l||x>r)return;
if(x<=l&&r<=y)
{
tree[p]+=(r-l+1)*z;
lazy[p]+=z;
return;
}
pushdown(p,l,r);
int mid=(l+r)/2;
change(p*2,l,mid,x,y,z);
change(p*2+1,mid+1,r,x,y,z);
tree[p]=tree[p*2]+tree[p*2+1];
}
int calc(int p,int l,int r,int x,int y)
{
if(y<l||x>r)return 0;
if(x<=l&&y>=r)
{
return tree[p];
}
pushdown(p,l,r);
int mid=(l+r)/2;
//if(y<=mid)return calc(p*2,l,mid,x,y);
//if(x>mid)return calc(p*2+1,mid+1,r,x,y);
//return calc(p*2,l,mid,x,mid)+calc(p*2+1,mid+1,r,mid+1,y);
return calc(p*2,l,mid,x,y)+calc(p*2+1,mid+1,r,x,y);
}
signed main()
{
//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
scanf("%lld %lld",&n,&q);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
build(1,1,n);
for(int i=1;i<=q;i++)
{
char c;
scanf("%s",&c);
if(c=='1')
{
int x,y,z;
scanf("%lld %lld %lld",&x,&y,&z);
change(1,1,n,x,y,z);
}
else
{
int y,z;
scanf("%lld %lld",&y,&z);
printf("%lld\n",calc(1,1,n,y,z));
}
}
return 0;
}
查找区间元素和，区间元素平方和， 将区间[l,r]内的每一个元素都乘上x，将区间[l,r]内的每一个元素都加上x
查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,ff;
int a[400010],lazy[400010];
struct node{
int sum;
int jia;
int cheng;
int ping;
}tree[4000000];
void build(int p,int l,int r)
{
tree[p].jia=0;
tree[p].cheng=1;
if(l==r)
{
tree[p].sum=a[l];
tree[p].ping=a[l]*a[l];
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
tree[p].ping=tree[p*2].ping+tree[p*2+1].ping;
}
void pushdown(int p,int l,int r)
{
int mid=(l+r)/2;
tree[2*p].jia*=tree[p].cheng;
tree[2*p+1].jia*=tree[p].cheng;
tree[2*p].cheng*=tree[p].cheng;
tree[2*p+1].cheng*=tree[p].cheng;
tree[2*p].sum*=tree[p].cheng;
tree[2*p+1].sum*=tree[p].cheng;
tree[2*p].ping*=tree[p].cheng*tree[p].cheng;
tree[2*p+1].ping*=tree[p].cheng*tree[p].cheng;
tree[p].cheng=1;
if(tree[p].jia)
{
tree[2*p].jia+=tree[p].jia;
tree[2*p+1].jia+=tree[p].jia;
tree[2*p].ping+=2*tree[p].jia*tree[2*p].sum+(mid-l+1)*tree[p].jia*tree[p].jia;
tree[2*p+1].ping+=2*tree[p].jia*tree[2*p+1].sum+(r-(mid+1)+1)*tree[p].jia*tree[p].jia;
tree[2*p].sum+=(mid-l+1)*tree[p].jia;
tree[2*p+1].sum+=(r-(mid+1)+1)*tree[p].jia;
tree[p].jia=0;
}
}
void changejia(int p,int l,int r,int x,int y,int z)
{
if(y<l||x>r)return;
if(x<=l&&r<=y)
{
tree[p].jia+=z;
tree[p].ping+=2*z*tree[p].sum+(r-l+1)*z*z;
tree[p].sum+=(r-l+1)*z;
return;
}
if(tree[p].jia||tree[p].cheng!=1)pushdown(p,l,r);
int mid=(l+r)/2;
if(x<=mid)changejia(p*2,l,mid,x,y,z);
if(y>mid)changejia(p*2+1,mid+1,r,x,y,z);
tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
tree[p].ping=tree[p*2].ping+tree[p*2+1].ping;
}
void changeche(int p,int l,int r,int x,int y,int z)
{
if(y<l||x>r)return;
if(x<=l&&r<=y)
{
tree[p].cheng*=z;
tree[p].jia*=z;
tree[p].ping*=z*z;
tree[p].sum*=z;
return;
}
if(tree[p].jia||tree[p].cheng!=1)pushdown(p,l,r);
int mid=(l+r)/2;
if(x<=mid)changeche(p*2,l,mid,x,y,z);
if(y>mid)changeche(p*2+1,mid+1,r,x,y,z);
tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
tree[p].ping=tree[p*2].ping+tree[p*2+1].ping;
}
int calc1(int p,int l,int r,int x,int y)
{
if(y<l||x>r)return 0;
if(x<=l&&y>=r)
{
return tree[p].sum;
}
if(tree[p].jia||tree[p].cheng!=1)pushdown(p,l,r);
int mid=(l+r)/2;
int ans=0;
if(x<=mid)ans+=calc1(2*p,l,mid,x,y);
if(y>mid)ans+=calc1(2*p+1,mid+1,r,x,y);
return ans;
}
int calc2(int p,int l,int r,int x,int y)
{
if(y<l||x>r)return 0;
if(x<=l&&y>=r)
{
return tree[p].ping;
}
if(tree[p].jia||tree[p].cheng!=1)pushdown(p,l,r);
int mid=(l+r)/2;
int ans=0;
if(x<=mid)ans+=calc2(2*p,l,mid,x,y);
if(y>mid)ans+=calc2(2*p+1,mid+1,r,x,y);
return ans;
}
signed main()
{
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,1,n);
for(int i=1;i<=q;i++)
{
int c,x,y,z;
cin>>c>>x>>y;
if( c == 1)
cout<<calc1(1,1,n,x,y)<<endl;
if( c == 2)
cout<<calc2(1,1,n,x,y)<<endl;
if( c == 3)
{
cin>>z;
changeche(1,1,n,x,y,z);
}
if( c == 4)
{
cin>>z;
changejia(1,1,n,x,y,z);
}
}
return 0;
}
标签：return,
jia,
int,
线段,
tree,
mid,
sum
From： https://www.cnblogs.com/violet-hty/p/18400720