poj 3468セグメントツリーセグメント更新
2023 ワード
タイトル:
n個の数を与えて、mの中で操作します!!エリアの和はすでにエリアの更新を求めました!
解法:
線分樹!!
n個の数を与えて、mの中で操作します!!エリアの和はすでにエリアの更新を求めました!
解法:
線分樹!!
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100010;
#define ll long long
ll sum[maxn<<2],col[maxn<<2],s[maxn];
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
void pushUP(int rt)
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int rt,int l,int r)
{
col[rt]=0;
if(l==r)
{
sum[rt]=s[l];
return;
}
int mid=(l+r)>>1;
build(lson);
build(rson);
pushUP(rt);
}
void pushDOWN(int rt,int m)
{
if(col[rt])
{
col[rt<<1]+=col[rt];
col[rt<<1|1]+=col[rt];
sum[rt<<1]+=col[rt]*(m-(m>>1));
sum[rt<<1|1]+=col[rt]*(m>>1);
col[rt]=0;
// pushUP(rt);
}
}
void updata(int rt,int l,int r,int L,int R,int c)
{
if(L<=l&&r<=R)
{
col[rt]+=c;
sum[rt]+=(r-l+1)*(ll)c;
return;
}
pushDOWN(rt,r-l+1);//
int mid=(l+r)>>1;
if(mid>=L) updata(lson,L,R,c);
if(mid<R) updata(rson,L,R,c);
pushUP(rt);
}
ll query(int rt,int l,int r,int L,int R)
{
if(L<=l&&r<=R)
{
return sum[rt];
}
pushDOWN(rt,r-l+1);// pushDown WA //
int mid=(l+r)>>1;
__int64 res=0;
if(mid>=L) res+=query(lson,L,R);
if(mid<R) res+=query(rson,L,R);
return res;
}
int main()
{
int i,j,a,b,c;
int n,m;
char op[2];
scanf("%d%d",&n,&m);
for(i=1; i<=n; i++)scanf("%lld",&s[i]);// ll WA
build(1,1,n);
while(m--)
{
scanf("%s",op);
if (op[0] == 'Q') {
scanf("%d%d",&a,&b);
printf("%lld
",query(1,1,n,a,b));
} else {
scanf("%d%d%d",&a,&b,&c);
updata(1,1,n,a,b,c);
}
}
return 0;
}