洛谷 2023_[AHOI2009]维护序列_线段树

发布于 2019-05-20  5 次阅读


题目描述

老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成。 有长为N的数列,不妨设为a1,a2,…,aN 。有如下三种操作形式: (1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值; (3)询问数列中的一段数的和,由于答案可能很大,你只需输出这个数模P的值。


思路

加两个标记一个乘一个加,跑lazy+线段树模板就可以了
写的时候忘了将值向上传递
最后没有输出lld型。。。


#include 
#define maxn 1000001
#define LL long long
int n,mod;
struct tree
{
    LL x,addlazy,mullazy;
}t[maxn];
LL a[maxn];
int k=0;
inline int read()
{
    int x=0,p=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-')p=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*p;
}
int pushdown(int p,int l,int r)
{
    int m=(l+r)>>1;
    if (l>1;
    if (m>=y) add(p<<1,l,m,x,y,k);
    else if (m>1;
    if (m>=y) mul(p<<1,l,m,x,y,k);
    else if (m>1;
    if (m>=y) xx=find(p<<1,l,m,x,y);
    else if (m>1;
    if (l==r)
    {
        t[p].x=a[l];
        return 0;
    }
    build(p<<1,l,m);
    build(p<<1|1,m+1,r);
    t[p].x=(t[p<<1].x+t[p<<1|1].x)%mod;
}
int main()
{
    n=read(); mod=read();
    for (int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build(1,1,n);

    int m=read();
    for (int i=1;i<=m;i++)
    {
        int h=read();
        if (h==1)
        {
            int x=read(),y=read(),k=read();
            mul(1,1,n,x,y,k);
        }
        if (h==2)
        {
            int x=read(),y=read(),k=read();
            add(1,1,n,x,y,k);
        }
        if (h==3)
        {
            int x=read(),y=read();
            printf("%lld\n",find(1,1,n,x,y));
        }
    }
}
]]>