私は次のコードを持っています。これは、遅延伝播を使用したセグメント ツリー用で、なんとか書くことができました。このコードは、範囲内のすべての数値に x などの値を掛ける場合には機能しません。update_mult 関数で何か間違ったことをしていると思います。ツリーは、範囲の合計を維持します。
update_mult の問題がわかりませんでした。専門家の皆さん、実装のどこが間違っているのかを見つけるのを手伝ってくれませんか?
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <set>
#include <assert.h>
#include <cstring>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <time.h>
#include <climits>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;++i)
#define FORR(i,a,b) for(int i=a;i>=b;--i)
#define FORC(it,container) for(typeof(container.begin()) it=container.begin();it!=container.end();++it)
#define INT(x) scanf("%d",&x)
#define LLD(x) scanf("%lld",&x)
#define STR(x) scanf("%s",x)
#define CHAR(x) scanf("%c",&x)
#define PINT(x) printf("%d\n",x)
#define PLLD(x) printf("%lld\n",x)
#define CLR(x) memset(x,0,sizeof(x));
const int INF = INT_MAX;
const int MAX = 1000001;
typedef long long LL;
LL arr[MAX+5];
LL MOD = 1e9 + 7;
struct data
{
LL sumsq;
LL sum;
LL lazyset;
LL setval;
LL lazyMult;
LL lazyVal;
LL addval;
void assignleaf()
{
}
void assignleaf(int idx ,int val)
{
}
void combine(data &l, data &r)
{
sum = (l.sum + r.sum)%MOD;
}
};
data tree[10*MAX+5];
void pushdown(int node,int segs,int sege)
{
int mid = segs+sege; mid /= 2;
if(tree[node].lazyset==1)
{
tree[node].lazyset=0;
tree[2*node].lazyset=1;
tree[2*node+1].lazyset=1;
tree[2*node].setval = tree[node].setval;
tree[2*node+1].setval = tree[node].setval;
tree[2*node].sum = ((mid-segs+1)*tree[node].setval)%MOD;
tree[2*node+1].sum = ((sege-mid)*tree[node].setval)%MOD;
tree[2*node].addval=0;
tree[2*node+1].addval=0;
}
if(tree[node].lazyMult==1)
{
tree[node].lazyMult=0;
tree[2*node].lazyMult=1;
tree[2*node+1].lazyMult=1;
tree[2*node].sum = (tree[2*node].sum * tree[node].lazyVal)%MOD;
tree[2*node+1].sum = (tree[2*node+1].sum * tree[node].lazyVal)%MOD;
tree[2*node].addval=0;
tree[2*node+1].addval=0;
}
if(tree[node].addval)
{
tree[2*node].addval = (tree[2*node].addval +tree[node].addval)%MOD;
tree[2*node+1].addval = (tree[2*node+1].addval +tree[node].addval)%MOD;
tree[2*node].sum = (tree[2*node].sum + ((mid-segs+1)*tree[node].addval)%MOD)%MOD;
tree[2*node+1].sum =(tree[2*node+1].sum+ ((sege-mid)*tree[node].addval)%MOD)%MOD;
tree[node].addval = 0;
}
}
void build_tree(int node,int s,int e)
{
tree[node].addval=0;
tree[node].lazyset=0;
if(s>e) return;
if(s==e)
{
tree[node].sum = arr[s];
return;
}
int mid=(s+e)/2;
build_tree(2*node,s,mid);
build_tree(2*node+1,mid+1,e);
tree[node].combine(tree[2*node],tree[2*node+1]);
}
LL query(int node,int segs,int sege,int qs,int qe)
{
//cout<<" q -- node = "<<node<<" segs = "<<segs<<" sege = "<<sege<<" qs = "<<qs<<" qe = "<<qe<<endl;
if(segs>sege || segs>qe || sege < qs)
{
if(tree[node].lazyset||tree[node].addval)
pushdown(node,segs,sege);
return 0;
}
if(tree[node].lazyset || tree[node].addval)
pushdown(node,segs,sege);
if(segs>=qs && sege<=qe)
{
//cout<<"q1 node = "<<node<<" segs = "<<segs<<" sege = "<<sege<<" sumsq = "<<tree[node].sumsq<<endl;
return tree[node].sum % MOD;
}
int mid= segs+sege; mid /= 2;
return (query(2*node,segs,mid,qs,qe) + query(2*node+1,mid+1,sege,qs,qe))%MOD;
}
//comm=1
void update_add(int node,int segs,int sege,int qs,int qe,int x)
{
if(segs>sege||segs>qe||sege<qs) return;
if(segs>=qs && sege<=qe)
{
tree[node].addval = (tree[node].addval+x)%MOD;
tree[node].sum = (tree[node].sum + ((LL)(sege-segs+1)*x)%MOD)%MOD;
return;
}
int mid= segs+sege; mid /= 2;
if(tree[node].lazyset || tree[node].addval)
pushdown(node,segs,sege);
update_add(2*node,segs,mid,qs,qe,x);
update_add(2*node+1,mid+1,sege,qs,qe,x);
tree[node].combine(tree[2*node],tree[2*node+1]);
}
void update_mult(int node,int segs,int sege,int qs,int qe,LL x)
{
//cout<<" ua - node = "<<node<<" segs = "<<segs<<" sege = "<<sege<<" qs = "<<qs<<" qe = "<<qe<<" x = "<<x<<endl;
if(segs>sege||segs>qe||sege<qs) return;
if(segs>=qs && sege<=qe)
{
//tree[node].addval = (tree[node].addval * x)%MOD;
tree[node].sum = (tree[node].sum * x)%MOD;
tree[node].lazyMult = 1;
tree[node].lazyVal = x;
tree[node].addval = 0;
return;
}
int mid= segs+sege; mid /= 2;
if(tree[node].lazyMult || tree[node].addval)
pushdown(node,segs,sege);
update_mult(2*node,segs,mid,qs,qe,x);
update_mult(2*node+1,mid+1,sege,qs,qe,x);
tree[node].combine(tree[2*node],tree[2*node+1]);
}
//comm=0
void update_set(int node,int segs,int sege,int qs,int qe,LL x)
{
//cout<<" node = "<<node<<" segs = "<<segs<<" sege = "<<sege<<" qs = "<<qs<<" qe = "<<qe<<" x = "<<x<<endl;
if(segs>sege||segs>qe||sege<qs)
return;
if(segs>=qs && sege<=qe)
{
tree[node].lazyset= 1;
tree[node].setval=x;
tree[node].sum = ((LL)(sege-segs+1)*x)%MOD;
tree[node].addval = 0;
return;
}
if(tree[node].lazyset || tree[node].addval)
pushdown(node,segs,sege);
int mid= segs+sege;
mid /= 2;
update_set(2*node,segs,mid,qs,qe,x);
update_set(2*node+1,mid+1,sege,qs,qe,x);
tree[node].combine(tree[2*node],tree[2*node+1]);
}
int main()
{
int test = 1;
FOR(tt,1,test+1)
{
int n,q; INT(n); INT(q);
CLR(arr);
CLR(tree);
FOR(i,0,n)
LLD(arr[i]);
build_tree(1,0,n-1);
while(q--)
{
int comm; int l,r;
INT(comm); INT(l); INT(r);
if(comm==3)
{
//set x
LL x; LLD(x);
update_set(1,0,n-1,l-1,r-1,x);
}
else if(comm==1)
{
//add x
LL x; LLD(x);
update_add(1,0,n-1,l-1,r-1,x);
}
else if(comm==2)
{
//add x
LL x; LLD(x);
update_mult(1,0,n-1,l-1,r-1,x);
}
else if(comm==4)
{
LL ans = query(1,0,n-1,l-1,r-1);
PLLD(ans);
}
}
}
return 0;
}