题目链接：牛牛的等差数列 对每个区间维护首项和公差即可。显然是具有可加性的。
最开始分块TLE了。
（比赛的时候L写成1了。。。。）
【牛牛的等差数列】AC代码：
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include
#define int long long
#define mid (l+r>>1)
using namespace std;
const int N=2e5+10;
const int mod=3LL*5*7*11*13*17*19*23;
const int inv=mod-mod/2;
int n,a[N],q;
char *fs,*ft,buf[1<<20];
#define gc() (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<20,stdin),fs==ft))?0:*fs++;
inline int read(){
int x=0,f=1;
char ch=gc();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=gc();
}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';
ch=gc();
}
return x*f;
}
int calc(int a,int d,int len){
return (a*len%mod+(len-1)*len*inv%mod*d%mod)%mod;
}
struct seg{
int sum[N<<2],k[N<<2],d[N<<2];
void build(int p,int l,int r){
if(l==r){sum[p]=a[l];
return ;
}
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
sum[p]=(sum[p<<1]+sum[p<<1|1])%mod;
}
void push_down(int p,int l,int r){
if(!k[p]&&!d[p]) return ;
k[p<<1]=(k[p<<1]+k[p])%mod,d[p<<1]=(d[p<<1]+d[p])%mod;
k[p<<1|1]=(k[p<<1|1]+k[p]+(mid-l+1)*d[p]%mod)%mod,d[p<<1|1]=(d[p<<1|1]+d[p])%mod;
sum[p<<1]=(sum[p<<1]+calc(k[p],d[p],mid-l+1))%mod;
sum[p<<1|1]=(sum[p<<1|1]+calc((k[p]+(mid-l+1)*d[p]%mod)%mod,d[p],r-mid))%mod;
k[p]=0,d[p]=0;
}
void change(int p,int l,int r,int ql,int qr,int qk,int qd){
if(l==ql&&r==qr){
k[p]=(k[p]+qk)%mod,d[p]=(d[p]+qd)%mod;
sum[p]=(sum[p]+calc(qk,qd,r-l+1))%mod;
return ;
}
push_down(p,l,r);
if(qr<=mid) change(p<<1,l,mid,ql,qr,qk,qd);
else if(ql>mid) change(p<<1|1,mid+1,r,ql,qr,qk,qd);
else{
change(p<<1,l,mid,ql,mid,qk,qd);
change(p<<1|1,mid+1,r,mid+1,qr,((mid-ql+1)*qd%mod+qk)%mod,qd);
}
sum[p]=(sum[p<<1]+sum[p<<1|1])%mod;
}
int ask(int p,int l,int r,int ql,int qr){
if(l==ql&&r==qr) return sum[p];
push_down(p,l,r);
if(qr<=mid) return ask(p<<1,l,mid,ql,qr);
else if(ql>mid) return ask(p<<1|1,mid+1,r,ql,qr);
else return (ask(p<<1,l,mid,ql,mid)+ask(p<<1|1,mid+1,r,mid+1,qr))%mod;
}
}t;
signed main(){
n=read();
for(int i=1;
i<=n;
i++) a[i]=read();
t.build(1,1,n);
q=read();
for(int i=1,op,l,r,val,d;
i<=q;
i++){
op=read(),l=read(),r=read(),val=read();
if(op==1){
d=read();
t.change(1,1,n,l,r,val,d);
}else{
printf("%lld\n",t.ask(1,1,n,l,r)%val);
}
}
return 0;
}
推荐阅读
- 线段树|[类欧几里得算法 线段树] BZOJ 1938 [CROATIAN2010] ALADIN
- 牛客 C. 子段乘积（线段树）
- 牛客挑战赛39 C 牛牛的等差数列（线段树）（*）
- 牛客 数据结构（区间修改+求区间元素平方和）
- 校门外的树 线段树版
- 树链剖分|牛客练习赛51 F-ABCBA（树链剖分，线段树，状态转移）
- 数论|bzoj 1938 - 类欧几里得+线段树
- 线段树|FZU - 2277(树链剖分或dfs序+线段树)
- 并查集|[CF938G] Shortest Path Queries
- 牛客网 练习赛25 B最长区间