【BZOJ1798】【AHOI2009】维护序列(线段树)
序列 维护 线段
2023-09-11 14:14:41 时间
题解
这不就是luogu的线段树2的板子吗。。。。
没有任何的区别。。。
上代码吧。。。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
using namespace std;
#define ll long long
#define lson (now<<1)
#define rson (now<<1|1)
#define MAX 200000
int a[MAX];
int P,N,M;
inline ll read()
{
ll x=0,t=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
struct Node
{
ll val,lc,lj;
}t[MAX*5];
void Build(int now,int l,int r)
{
t[now].lc=1;t[now].lj=0;
if(l==r){t[now].val=a[l]%P;return;}
int mid=(l+r)>>1;
Build(lson,l,mid);
Build(rson,mid+1,r);
t[now].val=(t[lson].val+t[rson].val)%P;
}
void Pushdown(int now,int l,int r)
{
int mid=(l+r)>>1;
int lsize=mid-l+1,rsize=r-mid;
t[lson].val=(t[lson].val*t[now].lc+t[now].lj*lsize)%P;
t[rson].val=(t[rson].val*t[now].lc+t[now].lj*rsize)%P;
t[lson].lc=t[lson].lc*t[now].lc%P;
t[rson].lc=t[rson].lc*t[now].lc%P;
t[lson].lj=(t[lson].lj*t[now].lc+t[now].lj)%P;
t[rson].lj=(t[rson].lj*t[now].lc+t[now].lj)%P;
t[now].lc=1;t[now].lj=0;
}
void Plus(int now,int l,int r,int al,int ar,ll pp)
{
if(al==l&&ar==r)
{
t[now].lj=(t[now].lj+pp)%P;
t[now].val=(t[now].val+(r-l+1)*pp)%P;
return;
}
Pushdown(now,l,r);
int mid=(l+r)>>1;
if(ar<=mid)Plus(lson,l,mid,al,ar,pp);
else if(al>mid)Plus(rson,mid+1,r,al,ar,pp);
else {Plus(lson,l,mid,al,mid,pp);Plus(rson,mid+1,r,mid+1,ar,pp);}
t[now].val=(t[lson].val+t[rson].val)%P;
}
void Multi(int now,int l,int r,int al,int ar,ll pp)
{
if(al==l&&ar==r)
{
t[now].val=(t[now].val*pp)%P;
t[now].lj=(t[now].lj*pp)%P;
t[now].lc=(t[now].lc*pp)%P;
return;
}
Pushdown(now,l,r);
int mid=(l+r)>>1;
if(ar<=mid)Multi(lson,l,mid,al,ar,pp);
else if(al>mid)Multi(rson,mid+1,r,al,ar,pp);
else {Multi(lson,l,mid,al,mid,pp);Multi(rson,mid+1,r,mid+1,ar,pp);}
t[now].val=(t[lson].val+t[rson].val)%P;
}
ll Query(int now,int l,int r,int al,int ar)
{
if(al==l&&ar==r)return t[now].val%P;
Pushdown(now,l,r);
int mid=(l+r)>>1;
ll re=0;
if(ar<=mid)re=Query(lson,l,mid,al,ar)%P;
else if(al>mid)re=Query(rson,mid+1,r,al,ar)%P;
else re=(Query(lson,l,mid,al,mid)+Query(rson,mid+1,r,mid+1,ar))%P;
t[now].val=(t[lson].val+t[rson].val)%P;
return re%P;
}
int main()
{
N=read();P=read();
for(int i=1;i<=N;++i)a[i]=read();
Build(1,1,N);
M=read();
while(M--)
{
int opt=read();int x=read();int y=read();
if(opt==1)
{
ll k=read();
Multi(1,1,N,x,y,k);
}
if(opt==2)
{
ll k=read();
Plus(1,1,N,x,y,k);
}
if(opt==3)
{
printf("%lld\n",Query(1,1,N,x,y)%P);
}
}
return 0;
}
相关文章
- C语言程序设计100例之(58):连续子序列计数
- hdu4604 不错的子序列问题
- 【BZOJ4540】【HNOI2016】序列(莫队)
- Google Earth Engine (GEE) ——时间序列分析案例分析
- Google Earth Engine(GEE)——长时间序列逐月VCI数据提取分析和面积计算(墨西哥为例)
- SS2022-Z变换-性质-两个序列乘积的Z变换是什么?
- 用Logitic 映射产生混沌序列
- 最长公共子序列lcs实现
- 数据结构 DNA序列 (KMP+暴力,或者STL+暴力)
- POJ 1458 Common Subsequence (DP+LCS,最长公共子序列)
- Python 物联网之用于基于 TinyFlux的物联网和分析应用程序的微型时间序列数据库
- [LeetCode] 673. Number of Longest Increasing Subsequence 最长递增序列的个数
- 【bzoj1251】序列终结者 Splay