https://ac.nowcoder.com/acm/contest/19684/E
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
long long mod;
long long A[MAXN];
struct tnode
{
long long sum[2], lazy[2];
int l, r;
};
tnode operator + (const tnode &A, const tnode &B)
{
tnode C;
C.l = A.l;
C.r = B.r;
C.lazy[0] = 1;
C.lazy[1] = 0;
C.sum[0] = A.sum[0] + B.sum[0];
if (C.sum[0] >= mod)C.sum[0] -= mod;
C.sum[1] = A.sum[1] + B.sum[1];
if (C.sum[1] >= mod)C.sum[1] -= mod;
C.sum[1] += A.sum[0] * B.sum[0] % mod;
if (C.sum[1] >= mod)C.sum[1] -= mod;
return C;
}
struct Segment_Tree
{
tnode t[4 * MAXN];
void init_lazy(int root)
{
t[root].lazy[0] = 1;
t[root].lazy[1] = 0;
}
void union_lazy(int fa, int ch)
{
long long temp[2];
temp[0] = t[fa].lazy[0] * t[ch].lazy[0] % mod;
temp[1] = ((t[fa].lazy[0] * t[ch].lazy[1] % mod) + t[fa].lazy[1]) % mod;
t[ch].lazy[0] = temp[0];
t[ch].lazy[1] = temp[1];
}
void cal_lazy(int root)
{
long long len = (t[root].r - t[root].l + 1) % mod;
t[root].sum[1] = (len * (len - 1) / 2 % mod * t[root].lazy[1] % mod * t[root].lazy[1] % mod +
t[root].lazy[0] * t[root].lazy[0] % mod * t[root].sum[1] % mod +
t[root].lazy[0] * t[root].lazy[1] % mod * (len - 1) % mod * t[root].sum[0] % mod) % mod;
t[root].sum[0] = (len * t[root].lazy[1] % mod +
t[root].lazy[0] * t[root].sum[0] % mod) % mod;
return;
}
void push_down(int root)
{
if (t[root].lazy[0] != 1 || t[root].lazy[1] != 0)
{
cal_lazy(root);
if (t[root].l != t[root].r)
{
int ch = root << 1;
union_lazy(root, ch);
union_lazy(root, ch + 1);
}
init_lazy(root);
}
}
void update (int root)
{
int ch = root << 1;
push_down(ch);
push_down(ch + 1);
t[root] = t[ch] + t[ch + 1];
}
void build(int root, int l, int r)
{
t[root].l = l;
t[root].r = r;
init_lazy(root);
if (l != r)
{
int mid = (l + r) >> 1;
int ch = root << 1;
build(ch, l, mid);
build(ch + 1, mid + 1, r);
update(root);
}
else
{
t[root].sum[0] = A[l] % mod;
t[root].sum[1] = 0;
}
}
void change(int root, int l, int r, long long delta, int op)
{
push_down(root);
if (l == t[root].l && r == t[root].r)
{
t[root].lazy[op] = delta % mod;
return;
}
int mid = (t[root].l + t[root].r) >> 1;
int ch = root << 1;
if (r <= mid)change(ch, l, r, delta, op);
else if (l > mid)change(ch + 1, l, r, delta, op);
else {change(ch, l, mid, delta, op); change(ch + 1, mid + 1, r, delta, op);}
update(root);
}
tnode sum(int root, int l, int r)
{
push_down(root);
if (t[root].l == l && t[root].r == r)
{
return t[root];
}
int mid = (t[root].l + t[root].r) >> 1;
int ch = root << 1;
if (r <= mid)return sum(ch, l, r);
else if (l > mid)return sum(ch + 1, l, r);
else return sum(ch, l, mid) + sum(ch + 1, mid + 1, r);
}
};
Segment_Tree ST;
int n, m, op, l, r, T;
long long x;
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d %d %lld", &n, &m , &mod);
for (int i = 1; i <= n; ++i)
{
scanf("%lld", &A[i]);
}
ST.build(1, 1, n);
for (int _ = 1; _ <= m; ++_)
{
scanf("%d %d %d", &op, &l, &r);
if (op <= 2)
{
scanf("%lld", &x);
ST.change(1, l, r, x, 2 - op);
}
else
{
printf("%lld\n", ST.sum(1, l, r).sum[1]);
}
}
}
return 0;
}
https://www.luogu.com.cn/problem/P3372
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,a[N];
struct tree{
int l,r ;
long long sum;
long long tag;
};
tree t[4*N];
inline void update(int i)
{
t[i].sum=t[i*2].sum+t[i*2+1].sum;
}
inline void pass(int i, long long x)
{
t[i].tag+=x;
t[i].sum+=x*(t[i].r-t[i].l+1);
}
inline void pushdown(int i)
{
pass(i*2,t[i].tag);
pass(i*2+1,t[i].tag);
t[i].tag=0;
}
inline void build_tree(int i,int l,int r)
{
t[i].l=l;t[i].r=r;
if(l==r)
{
t[i].sum=a[l];t[i].tag=0;
return;
}
int mid=(l+r)>>1;
build_tree(i*2,l,mid);
build_tree(i*2+1,mid+1,r);
update(i);
}
inline long long query(int i,int l,int r)
{
if(l<=t[i].l&&t[i].r<=r) return t[i].sum;
int mid=(t[i].l+t[i].r)/2;
long long ans=0;
pushdown(i);
if(l<=mid) ans+=query(i*2,l,r);
if(r>mid) ans+=query(i*2+1,l,r);
return ans;
}
inline void change(int i,int l,int r,int x)
{
if(l<=t[i].l&&t[i].r<=r)
{
t[i].sum+=x*(t[i].r-t[i].l+1);
t[i].tag+=x;
return;
}
pushdown(i);
int mid=(t[i].l+t[i].r)/2;
if(l<=mid) change(i*2,l,r,x);
if(r>mid) change(i*2+1,l,r,x);
update(i);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
build_tree(1,1,n);
while(m--)
{
int s=0; cin>>s;
if(s==1)
{
int x,y,k;cin>>x>>y>>k;
change(1,x,y,k);
}
else
{ int x,y;
cin>>x>>y;
cout<<query(1,x,y)<<"\n";
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int n,m,a[N];
struct node
{
int l,r;
int sum,tag;
};
node st[4*N];
void build(int i,int l,int r)
{
st[i].l=l;
st[i].r=r;
if(l==r)
{
st[i].sum=a[l];
st[i].tag=0;
return;
}
int mid=(l+r)/2;
build(i*2,l,mid);
build(i*2+1,mid+1,r);
st[i].sum=st[i*2].sum+st[i*2+1].sum;
}
void xiu(int i)
{
st[i].sum+=st[i/2].tag*(st[i].r-st[i].l+1);
st[i].tag+=st[i/2].tag;
}
void pushdown(int i)
{
xiu(i*2);
xiu(i*2+1);
st[i].tag=0;
}
void change(int i,int l,int r,int k)
{
if(l<=st[i].l&&st[i].r<=r)
{
st[i].sum+=k*(st[i].r-st[i].l+1);
st[i].tag+=k;
return;
}
pushdown(i);
int mid=(st[i].l+st[i].r)/2;
if(l<=mid) change(i*2,l,r,k);
if(r>mid) change(i*2+1,l,r,k);
st[i].sum=st[i*2].sum+st[i*2+1].sum;
}
int query(int i,int l,int r)
{
if(l<=st[i].l&&st[i].r<=r)
{
return st[i].sum;
}
pushdown(i);
int ans=0;
int mid=(st[i].l+st[i].r)/2;
if(l<=mid) ans+=query(i*2,l,r);
if(r>mid) ans+=query(i*2+1,l,r);
return ans;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
while(m--)
{
int s;cin>>s;
if(s==1)
{
int l,r,k;
cin>>l>>r>>k;
change(1,l,r,k);
}
else
{ int l,r;
cin>>l>>r;
cout<<query(1,l,r)<<"\n";
}
}
return 0;
}
