求时间复杂度优化

#include <bits/stdc++.h>
using namespace std;
int n,q,op,x,y,k;
long long arr[100005],m;
struct node{
	int l,r,lnt;
	long long val,tag1,tag2;
	bool leaf;
} tree[400005];
int ls(int n) {
	return n<<1;
}
int rs(int n) {
	return n<<1|1;
}
void push_up(int n) {
	tree[n].val=tree[ls(n)].val*tree[ls(n)].tag1+tree[rs(n)].val*tree[rs(n)].tag1+tree[ls(n)].lnt*tree[ls(n)].tag2+tree[rs(n)].lnt*tree[rs(n)].tag2;
	//tree[n].val=tree[ls(n)].val+tree[rs(n)].val;
	tree[n].val%=m;
}
void push_down(int n,int type) {
	if (tree[n].tag1!=1) {
		tree[n].val*=tree[n].tag1;
		tree[n].val%=m;
		tree[ls(n)].tag1*=tree[n].tag1;
		tree[rs(n)].tag1*=tree[n].tag1;
		tree[ls(n)].tag1%=m;
		tree[rs(n)].tag1%=m;
		tree[n].tag1=1;
	}
	if (tree[n].tag2!=0) {
		tree[n].val+=(tree[n].lnt*tree[n].tag2);
		tree[n].val%=m;
		tree[ls(n)].tag2+=tree[n].tag2;
		tree[rs(n)].tag2+=tree[n].tag2;
		tree[ls(n)].tag2%=m;
		tree[rs(n)].tag2%=m;
		tree[n].tag2=0;
	}
}
void build_tree(int n,int l,int r) {
	//printf("%d %d %d\n",n,l,r);
	tree[n].l=l;
	tree[n].r=r;
	tree[n].lnt=r-l+1;
	tree[n].tag1=1;
	tree[n].tag2=0;
	if (l==r) {
		tree[n].val=arr[l];
		tree[n].leaf=1;
		return;
	}
	int mid=(l+r)>>1;
	build_tree(ls(n),l,mid);
	build_tree(rs(n),mid+1,r);
	push_up(n);
}
long long ret(int n,int l,int r) {
	//printf("%d %d %d\n",n,l,r);
	if (tree[n].tag1!=1) {
		tree[n].val*=tree[n].tag1;
		tree[n].val%=m;
		if (!tree[n].leaf) {
			if (tree[ls(n)].tag2!=0) ret(ls(n),1,100005); //
			if (tree[rs(n)].tag2!=0) ret(rs(n),1,100005); //
			//push_down(ls(n),1);
			//push_down(rs(n),1);
			//push_down(ls(n),2);
			//push_down(rs(n),2);
			tree[ls(n)].tag1*=tree[n].tag1;
			tree[rs(n)].tag1*=tree[n].tag1;
			tree[ls(n)].tag1%=m;
			tree[rs(n)].tag1%=m;
		}
		tree[n].tag1=1;
	}
	if (tree[n].tag2!=0) {
		tree[n].val+=(tree[n].lnt*tree[n].tag2);
		if (!tree[n].leaf) {
			if (tree[ls(n)].tag1!=1) ret(ls(n),1,100005); //
			if (tree[rs(n)].tag1!=1) ret(rs(n),1,100005); //
			//push_down(ls(n),1);
			//push_down(rs(n),1);
			tree[ls(n)].tag2+=tree[n].tag2;
			tree[rs(n)].tag2+=tree[n].tag2;
			tree[ls(n)].tag2%=m;
			tree[rs(n)].tag2%=m;
		}
		tree[n].val%=m;
		tree[n].tag2=0;
	}
	if (tree[n].l>=l && tree[n].r<=r) {
		return tree[n].val;
	}
	int mid=(tree[n].l+tree[n].r)>>1;
	long long res=0;
	if (mid>=l) res+=ret(ls(n),l,r);
	if (mid<r) res+=ret(rs(n),l,r);
	push_up(n);
	return res%m;
}
void add(int n,int l,int r,int k) {
	if (tree[n].tag1!=1) {
		tree[n].val*=tree[n].tag1;
		tree[n].val%=m;
		if (!tree[n].leaf) {
			ret(ls(n),1,100005); //
			ret(rs(n),1,100005); //
			tree[ls(n)].tag1*=tree[n].tag1;
			tree[rs(n)].tag1*=tree[n].tag1;
			tree[ls(n)].tag1%=m;
			tree[rs(n)].tag1%=m;
		}
		tree[n].tag1=1;
	}
	if (tree[n].l>=l && tree[n].r<=r) {
		if (tree[n].leaf) tree[n].val+=k;
		else tree[n].tag2+=k;
		tree[n].val%=m;
		tree[n].tag2%=m;
		return;
	}
	if (tree[n].tag2!=0) {
		tree[n].val+=(tree[n].lnt*tree[n].tag2);
		if (!tree[n].leaf) {
			ret(ls(n),1,100005); //
			ret(rs(n),1,100005); //
			tree[ls(n)].tag2+=tree[n].tag2;
			tree[rs(n)].tag2+=tree[n].tag2;
			tree[ls(n)].tag2%=m;
			tree[rs(n)].tag2%=m;
		}
		tree[n].val%=m;
		tree[n].tag2=0;
	}
	int mid=(tree[n].l+tree[n].r)>>1;
	if (mid>=l) add(ls(n),l,r,k);
	if (mid<r) add(rs(n),l,r,k);
	push_up(n);
}
void mul(int n,int l,int r,int k) {
	if (tree[n].tag2!=0) {
		tree[n].val+=(tree[n].lnt*tree[n].tag2);
		if (!tree[n].leaf) {
			ret(ls(n),1,100005); //
			ret(rs(n),1,100005); //
			tree[ls(n)].tag2+=tree[n].tag2;
			tree[rs(n)].tag2+=tree[n].tag2;
			tree[ls(n)].tag2%=m;
			tree[rs(n)].tag2%=m;
		}
		tree[n].val%=m;
		tree[n].tag2=0;
	}
	if (tree[n].l>=l && tree[n].r<=r) {
		if (tree[n].leaf) tree[n].val*=k;
		else tree[n].tag1*=k;
		tree[n].val%=m;
		tree[n].tag1%=m;
		return;
	}
	if (tree[n].tag1!=1) {
		tree[n].val*=tree[n].tag1;
		tree[n].val%=m;
		if (!tree[n].leaf) {
			ret(ls(n),1,100005); //
			ret(rs(n),1,100005); //
			tree[ls(n)].tag1*=tree[n].tag1;
			tree[rs(n)].tag1*=tree[n].tag1;
			tree[ls(n)].tag1%=m;
			tree[rs(n)].tag1%=m;
		}
		tree[n].tag1=1;
	}
	int mid=(tree[n].l+tree[n].r)>>1;
	if (mid>=l) mul(ls(n),l,r,k);
	if (mid<r) mul(rs(n),l,r,k);
	push_up(n);
}
int main() {
	scanf("%d%d%lld",&n,&q,&m);
	for (int i=1;i<=n;i++) {
		scanf("%lld",&arr[i]);
	}
	build_tree(1,1,n);
	for (int i=1;i<=q;i++) {
		scanf("%d",&op);
		if (op==1) {
			scanf("%d%d%d",&x,&y,&k);
			mul(1,x,y,k);
			/*
			for (int i=1;i<=n;i++) printf("%lld ",ret(1,i,i));
			printf("\n");
			for (int i=1;i<=n;i++) printf("%lld ",ret(1,i,i)%571373);
			printf("\n");
			*/
		}
		if (op==2) {
			scanf("%d%d%d",&x,&y,&k);
			add(1,x,y,k);
			/*
			for (int i=1;i<=n;i++) printf("%lld ",ret(1,i,i));
			printf("\n");
			for (int i=1;i<=n;i++) printf("%lld ",ret(1,i,i)%571373);
			printf("\n");
			*/
		}
		if (op==3) {
			scanf("%d%d",&x,&y);
			printf("%lld\n",ret(1,x,y));
		}
	}
}