[Luogu 2023] AHOI2009 维护序列

<题目链接>

#include <cstdio>

int n,m;

long long p;

class SegmentTree

{

    private:

        struct Node

        {

			int left,right;

            long long v,mul,add;

            Node *c[2];

            Node(int l,int r):left(l),right(r),mul(1LL),add(0LL)

            {

				if(l==r)

				{

					scanf("%lld",&v);

					return;

				}

				int mid=l+r>>1;

				c[0]=new Node(l,mid);

				c[1]=new Node(mid+1,r);

				PushUp();

            }

            ~Node(void)

            {

                if(c[0]!=nullptr)

                    delete c[0];

                if(c[1]!=nullptr)

                    delete c[1];

            }

            long long Size(void)

            {

				return (long long)(right-left+1);

            }

            long long Value(bool p)

            {

                return c[p]!=nullptr ? c[p]->v : 0;

            }

            void Modify(long long _mul,long long _add)

            {

                v=(v*_mul+Size()*_add)%p;

                mul=mul*_mul%p;

                add=(add*_mul+_add)%p;

            }

            void MulModify(long long k)

            {

                v=v*k%p;

                mul=mul*k%p;

                add=add*k%p;

            }

            void AddModify(long long k)

            {

                v=(v+Size()*k)%p;

                add=(add+k)%p;

            }

            void PushUp(void)

            {

                v=(Value(0)+Value(1))%p;

            }

            void PushDown(void)

            {

                if(c[0]!=nullptr)

                    c[0]->Modify(mul,add);

                if(c[1]!=nullptr)

                    c[1]->Modify(mul,add);

                mul=1,add=0;

            }

			void Mul(int l,int r,long long k)

			{

				if(l==left && r==right)

				{

					MulModify(k);

					return;

				}

				PushDown();

				int mid=left+right>>1;

				if(r<=mid)

					c[0]->Mul(l,r,k);

				else if(l>mid)

					c[1]->Mul(l,r,k);

				else

				{

					c[0]->Mul(l,mid,k);

					c[1]->Mul(mid+1,r,k);

				}

				PushUp();

			}

			void Add(int l,int r,long long k)

			{

				if(l==left && r==right)

				{

					AddModify(k);

					return;

				}

				PushDown();

				int mid=left+right>>1;

				if(r<=mid)

					c[0]->Add(l,r,k);

				else if(l>mid)

					c[1]->Add(l,r,k);

				else

				{

					c[0]->Add(l,mid,k);

					c[1]->Add(mid+1,r,k);

				}

				PushUp();

			}

			long long Sum(int l,int r)

			{

				if(l==left && r==right)

					return v;

				PushDown();

				int mid=left+right>>1;

				if(r<=mid)

					return c[0]->Sum(l,r);

				else if(l>mid)

					return c[1]->Sum(l,r);

				else

					return (c[0]->Sum(l,mid)+c[1]->Sum(mid+1,r))%p;

			}

        }*root;

    public:

		SegmentTree(int n):root(new Node(1,n)){}

        ~SegmentTree(void)

        {

			delete root;

        }

        void Mul(int l,int r)

        {

            long long k;

            scanf("%lld",&k);

			root->Mul(l,r,k);

        }

        void Add(int l,int r)

        {

            long long k;

            scanf("%lld",&k);

			root->Add(l,r,k);

        }

        void Sum(int l,int r)

        {

            printf("%lld\n",root->Sum(l,r));

        }

};

int main(int argc,char** argv)

{

	scanf("%d %lld",&n,&p);

    SegmentTree *T=new SegmentTree(n);

	scanf("%d",&m);

    for(int i=1,opt,x,y;i<=m;++i)

    {

        scanf("%d %d %d",&opt,&x,&y);

        switch(opt)

        {

            case 1:

                T->Mul(x,y);

                break;

            case 2:

                T->Add(x,y);

                break;

            case 3:

                T->Sum(x,y);

                break;

        }

    }

    delete T;

    return 0;

}

[Luogu 2023] AHOI2009 维护序列的相关教程结束。