原理类似,用线段树来维护区间求和,只是一个是一次差分的值,一个是二次差分的值
P1438 无聊的数列
每次加上等差数列,单点查询
#include <bits/stdc++.h>
using namespace std;
#define ul (u<<1)
#define ur (u<<1|1)
#define len(u) (tr[u].r-tr[u].l+1)
#define mid (tr[u].l+tr[u].r>>1)
#define int long long
const int M=1e6+5;
struct Tree {
int l,r;
int s,la;
}tr[M<<2];
int a[M];
void pu(int u) {
tr[u].s=tr[ul].s+tr[ur].s;
}
void pd(int u) {
if(tr[u].la==0)return ;
tr[ul].la+=tr[u].la;
tr[ur].la+=tr[u].la;
tr[ul].s+=len(ul)*tr[u].la;
tr[ur].s+=len(ur)*tr[u].la;
tr[u].la=0;
}
void build(int u,int l,int r) {
tr[u]={l,r,0,0};
if(l==r){tr[u].s=a[l];return ;}
build(ul,l,mid);build(ur,mid+1,r);
pu(u);
}
void up(int u,int l,int r,int c) {
if(tr[u].l>=l&&tr[u].r<=r) {
tr[u].s+=len(u)*c;
tr[u].la+=c;
return ;
}
pd(u);
if(l<=mid)up(ul,l,r,c);
if(r>mid)up(ur,l,r,c);
pu(u);
}
int query(int u,int l,int r) {
if(tr[u].l>=l&&tr[u].r<=r)return tr[u].s;
if(tr[u].l>r||tr[u].r<l)return 0;
pd(u);
return query(ul,l,r)+query(ur,l,r);
}
signed main() {
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=n;i;i--)a[i]-=a[i-1];
build(1,1,n);
for(int i=0;i<m;i++) {
int op,l,r;
cin>>op;
if(op==1) {
int k,d;cin>>l>>r>>k>>d;
up(1,l,l,k);
if(l!=r)up(1,l+1,r,d);
if(r<n)up(1,r+1,r+1,-(k+d*(r-l)));
}
else {
int t;cin>>t;
cout<<query(1,1,t)<<endl;
}
}
return 0;
}
牛牛的等差数列
每次加上等差数列,区间查询
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M=2e5+5;
const int mod=3*5*7*11*13*17*19*23;
#define ul u<<1
#define ur u<<1|1
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int a[M];
struct Tree {
int l,r,len;
int sum,la1,la2;//首项,公差记录一下就可以了
}tr[M<<2];
void pu(int u) {
tr[u].sum=(tr[ul].sum+tr[ur].sum)%mod;
}
void build(int u,int l,int r) {
tr[u]={l,r,r-l+1,a[l],0,0};
if(l==r)return ;
int mid=l+r>>1;
build(ul,l,mid);
build(ur,mid+1,r);
pu(u);
}
void upd(int &x,int y) {
x=(x+y)%mod;
}
void pd(int u) {//更新
if(tr[u].la1||tr[u].la2) {
int d1=tr[u].la1,d2=(tr[u].la1+tr[ul].len*tr[u].la2%mod)%mod;
upd(tr[ul].la1,d1);upd(tr[ul].la2,tr[u].la2);
upd(tr[ur].la1,d2);upd(tr[ur].la2,tr[u].la2);
upd(tr[ul].sum,d1*tr[ul].len%mod+tr[ul].len*(tr[ul].len-1)/2%mod*tr[u].la2%mod);
upd(tr[ur].sum,d2*tr[ur].len%mod+tr[ur].len*(tr[ur].len-1)/2%mod*tr[u].la2%mod);
tr[u].la1=tr[u].la2=0;
}
}
int query(int u,int l,int r) {
if(tr[u].l>=l&&tr[u].r<=r)return tr[u].sum;
if(tr[u].l>r||tr[u].r<l)return 0;
pd(u);
return (query(ul,l,r)+query(ur,l,r))%mod;
}
void up(int u,int l,int r,int x,int d) {
int xx=x+(tr[u].l-l)*d;
if(tr[u].l>=l&&tr[u].r<=r) {
upd(tr[u].sum,xx*tr[u].len%mod+tr[u].len*(tr[u].len-1)/2%mod*d%mod);
upd(tr[u].la1,xx);
upd(tr[u].la2,d);
return ;
}
if(tr[u].l>r||tr[u].r<l)return ;
pd(u);
up(ul,l,r,x,d);
up(ur,l,r,x,d);
pu(u);
}
signed main() {
int n=read();
for(int i=1;i<=n;i++)a[i]=read()%mod;
build(1,1,n);
int q=read();
while(q--) {
int op=read();
if(op==1) {
int l=read(),r=read(),x=read()%mod,d=read()%mod;
up(1,l,r,x,d);
}
else {
int l=read(),r=read(),m=read();
cout<<query(1,l,r)%m<<endl;
}
}
return 0;
}
标签:二次,int,upd,tr,差分,ur,ul,维护,mod
From: https://www.cnblogs.com/basicecho/p/16981515.html