有没有人帮我调线段树啊,一直没调出来,不知道哪里错了。。
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
const int N=1e5+5;
const ll mo=19260817;
ll n,m,D,sum,aa[N],pow[N],sn[N],fi[N];
ll tr0[N<<2],las0[N<<2],tr1[N<<2],las1[N<<2];
ll tr2[N<<2],las2[N<<2],tr3[N<<2],f1[N<<2],f2[N<<2];
ll num(ll qwq){return (qwq%mo+mo)%mo;}
ll dc(ll a,ll b){return num(b*(b+1)/2-a*(a+1)/2);}
ll qpow(ll a,ll k){
ll ans=1;
while(k){
if(k&1) ans=ans*a%mo;
a=a*a%mo;
k>>=1;
}
return ans;
}
void build(int node,int l,int r){
if(l==r){
scanf("%lld",&tr0[node]);
return;
}
int mid=l+r>>1;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
tr0[node]=tr0[node<<1]+tr0[node<<1|1];
tr0[node]%=mo;
}
void pushdown0(int node,int l,int r){
if(las0[node]){
int mid=l+r>>1;
las0[node<<1]+=las0[node];
las0[node<<1|1]+=las0[node];
tr0[node<<1]+=las0[node]*(mid-l+1);
tr0[node<<1|1]+=las0[node]*(r-mid);
tr0[node<<1]%=mo,tr0[node<<1|1]%=mo;
las0[node]=0;
}
}
void update0(int node,int l,int r,int x,int y,ll k){
if(x<=l&&y>=r){
tr0[node]+=k*(r-l+1);
las0[node]+=k;
tr0[node]%=mo,las0[node]%=mo;
return;
}
pushdown0(node,l,r);
int mid=l+r>>1;
if(x<=mid) update0(node<<1,l,mid,x,y,k);
if(y>=mid+1) update0(node<<1|1,mid+1,r,x,y,k);
tr0[node]=tr0[node<<1]+tr0[node<<1|1];
tr0[node]%=mo;
}
void pushdown1(int node,int l,int r){
if(las1[node]){
int mid=l+r>>1;
las1[node<<1]+=las1[node];
las1[node<<1|1]+=las1[node];
tr1[node<<1]+=las1[node]*dc(l-1,mid);
tr1[node<<1|1]+=las1[node]*dc(mid,r);
tr1[node<<1]%=mo,tr1[node<<1|1]%=mo;
las1[node]=0;
}
}
void update1(int node,int l,int r,int x,int y,ll k){
if(x<=l&&y>=r){
tr1[node]+=k*dc(l-1,r);
las1[node]+=k;
tr1[node]%=mo,las1[node]%=mo;
return;
}
pushdown1(node,l,r);
int mid=l+r>>1;
if(x<=mid) update1(node<<1,l,mid,x,y,k);
if(y>=mid+1) update1(node<<1|1,mid+1,r,x,y,k);
tr1[node]=tr1[node<<1]+tr1[node<<1|1];
tr1[node]%=mo;
}
void pushdown2(int node,int l,int r){
if(las2[node]){
int mid=l+r>>1;
ll rlas=las2[node]*pow[mid-l+1]%mo;
las2[node<<1]+=las2[node];
las2[node<<1|1]+=rlas;
tr2[node<<1]+=las2[node]*sn[mid-l+1];
tr2[node<<1|1]+=rlas*sn[r-mid];
tr2[node<<1]%=mo,tr2[node<<1|1]%=mo;
las2[node<<1]%=mo,las2[node<<1|1]%=mo;
las2[node]=0;
}
}
void update2(int node,int l,int r,int x,int y,ll k){
if(x<=l&&y>=r){
tr2[node]+=k*(sn[r-x+1]-sn[l-x]);
las2[node]+=k;
tr2[node]%=mo,las2[node]%=mo;
return;
}
pushdown2(node,l,r);
int mid=l+r>>1;
if(x<=mid) update2(node<<1,l,mid,x,y,k);
if(y>=mid+1) update2(node<<1|1,mid+1,r,x,y,k);
tr2[node]=tr2[node<<1]+tr2[node<<1|1];
tr2[node]%=mo;
}
void pushdown3(int node,int l,int r){
if(f1[node]||f2[node]){
int mid=l+r>>1,pos=mid-l+2,sop=r-mid+1;
ll inf1=fi[pos-1]*f2[node]+fi[pos-2]*f1[node];
ll inf2=fi[pos]*f2[node]+fi[pos-1]*f1[node];
f1[node<<1]+=f1[node];
f2[node<<1]+=f2[node];
tr3[node<<1]+=fi[pos-1]*f1[node]+(fi[pos]-1)*f2[node];
f1[node<<1]%=mo,f2[node<<1]%=mo,tr3[node<<1]%=mo;
f1[node<<1|1]+=inf1;
f2[node<<1|1]+=inf2;
tr3[node<<1|1]+=fi[sop-1]*inf1+(fi[sop]-1)*inf2;
f1[node<<1|1]%=mo,f2[node<<1|1]%=mo,tr3[node<<1|1]%=mo;
f1[node]=f2[node]=0;
}
}
void update3(int node,int l,int r,int x,int y){
if(x<=l&&y>=r){
f1[node]+=fi[l-x+1];
f2[node]+=fi[l-x+2];
tr3[node]+=fi[r-l+1]*fi[l-x+1]+(fi[r-l+2]-1)*fi[l-x+2];
f1[node]%=mo,f2[node]%=mo,tr3[node]%=mo;
return;
}
pushdown3(node,l,r);
int mid=l+r>>1;
if(x<=mid) update3(node<<1,l,mid,x,y);
if(y>=mid+1) update3(node<<1|1,mid+1,r,x,y);
tr3[node]=tr3[node<<1]+tr3[node<<1|1];
tr3[node]%=mo;
}
void find(int node,int l,int r,int x,int y){
if(x<=l&&y>=r){
sum+=tr0[node]+tr1[node]+tr2[node]+tr3[node];
return;
}
pushdown0(node,l,r);
pushdown1(node,l,r);
pushdown2(node,l,r);
pushdown3(node,l,r);
int mid=l+r>>1;
if(x<=mid) find(node<<1,l,mid,x,y);
if(y>=mid+1) find(node<<1|1,mid+1,r,x,y);
}
int main(){
scanf("%lld%lld%lld",&n,&m,&D);
build(1,1,n);
ll inv=qpow(D-1,mo-2);pow[0]=1;
for(int i=1;i<=n;i++){
pow[i]=pow[i-1]*D%mo;
sn[i]=num((pow[i]-1)*inv);
}
fi[0]=0,fi[1]=1;
for(int i=2;i<=n;i++)
fi[i]=(fi[i-1]+fi[i-2])%mo;
for(int i=1;i<=m;i++){
int op,l,r;
ll k,d;
scanf("%d%d%d",&op,&l,&r);
if(op==1){
scanf("%lld%lld",&k,&d);
update0(1,1,n,l,r,num(k-d*l));
update1(1,1,n,l,r,d);
}
else if(op==2){
scanf("%lld",&k);
update2(1,1,n,l,r,k);
}
else if(op==3){
update3(1,1,n,l,r);
}
else{
sum=0;
find(1,1,n,l,r);
printf("%lld\n",num(sum));
}
}
return 0;
}
无语了,这道题赛时3h30min都没调出来,所以这种多合一,思维量低,巨大码量题,出出来就是为了恶心人吗?