@[dennshokouni](/user/477757)
```
#include<bits/stdc++.h>
#define ls o<<1
#define rs o<<1|1
#define int long long
using namespace std;
const int maxn=2e5+5;
const int mod=19260817;
int n,m;
int d[maxn],a[maxn];
struct data{
int l,r;
int lcost,rcost,sum;
}t[maxn<<2];
data pushup(data lc,data rc){
data tmp;
tmp.lcost=(lc.lcost+rc.lcost+((rc.sum*(d[rc.l]-d[lc.l]))%mod))%mod;
tmp.rcost=(rc.rcost+lc.rcost+((lc.sum*(d[rc.r]-d[lc.r]))%mod))%mod;
tmp.sum=((lc.sum+rc.sum)%mod+mod)%mod;
tmp.l=lc.l,tmp.r=rc.r;
return tmp;
}
void build(int o,int l,int r){
t[o].l=l,t[o].r=r;
if(l==r){
t[o].sum=a[l],t[o].lcost=t[o].rcost=0;
return ;
}
int mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
t[o]=pushup(t[ls],t[rs]);
}
data query(int o,int l,int r,int x,int y){
x=max(x,l);
y=min(y,r);
if(x>y)
{
data res={x,y,0,0,0};
return res;
}
if(x==l&&r==y)
return t[o];
int mid=l+r>>1;
if(y<=mid)
return query(ls,l,mid,x,y);
if(x>mid)
return query(rs,mid+1,r,x,y);
return pushup(query(ls,l,mid,x,y),query(rs,mid+1,r,x,y));
}
signed main(){
cin>>n>>m;
for(int i=2;i<=n;i++){
cin>>d[i];
d[i]=(d[i]+d[i-1])%mod;
}
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]%=mod;
}
build(1,1,n);
while(m--){
int x,l,r;
cin>>x>>l>>r;
if(l>r)swap(l,r);
if(x<l){
data ans=query(1,1,n,l,r);
printf("%lld\n",((ans.lcost+ans.sum*((d[l]-d[x])%mod))%mod+mod)%mod);
}
else if(x>r){
data ans=query(1,1,n,l,r);
printf("%lld\n",((ans.rcost+ans.sum*((d[x]-d[r])%mod))%mod+mod)%mod);
}
else {
data ans1=query(1,1,n,l,x);
data ans2=query(1,1,n,x,r);
printf("%lld\n",((ans1.rcost+ans2.lcost)%mod+mod)%mod);
}
}
}
```
by LHQing @ 2023-02-10 16:43:05
$d_i$ 读入前缀和没取模,$l\leq x\leq r$ 的时候应该包含点 $x$(因为要移动到这里)。这些是不仔细造成的错误。
by LHQing @ 2023-02-10 16:45:12
你这个程序的主要的问题。还是在于 data 的意义。
l是目前询问区间左边界,r是目前询问区间右边界。
定义的是什么,写的时候就应该写什么。
by LHQing @ 2023-02-10 16:46:27
你的query函数中,初始化的res的边界根本就不是询问区间的边界,而是节点区间的边界。十分混乱。
by LHQing @ 2023-02-10 16:47:07
另外,pushup函数中,你不应该使用中点值mid作为两个区间分界。这不一定对,比如 [1,4] [5,5] 的分界是 4-5 ,而不是正中间。
你既然 lc 和 rc 都带有左右边界,直接用来更新就好了。
by LHQing @ 2023-02-10 16:48:18
@[LHQing](/user/167507) 謝謝,月亮好閃,拜謝月亮
by V1mnkE @ 2023-02-10 16:56:25