RT,long long也开了但不知道为啥还是WA了......
(错了 #2 #9 #10 点)
#include<cstdio>
#define ll long long
using namespace std;
int n,m,z;
ll ans;
long long tree[4*100020];
int p;
ll lazy[4*100020];
ll mlazy[4*100020];
long long read()
{
long long num=0;
int f=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while('0'<=c&&c<='9')num=num*10+c-'0',c=getchar();
return num*f;
}
ll build(int l,int r,int a)
{
mlazy[a] = 1;
//printf("1 ");
if(l==r)
{
tree[a]=read();
return tree[a];
}
int mid=(l+r)>>1;
tree[a] += build(l,mid,a<<1);
tree[a] += build(mid+1,r,(a<<1)|1);
return tree[a];
}
//void print(int l,int r,int a)
//{
// //mlazy[a] = 1;
// //printf("1 ");
// if(l==r)
// {
// printf("%d:%d ",l,tree[a]);
// return;
// }
// int mid=(l+r)>>1;
// print(l,mid,a<<1);
// print(mid+1,r,(a<<1)|1);
// //return tree[a];
//}
inline void push_up(int a)
{
tree[a] = tree[a<<1] + tree[(a<<1)|1];
}
inline void push_down(int a,int l,int r)
{
if(lazy[a]||mlazy[a])
{
mlazy[a<<1] = (mlazy[a<<1] * mlazy[a])%p;
mlazy[(a<<1)|1] = (mlazy[(a<<1)|1] * mlazy[a])%p;
lazy[a<<1] = (lazy[a<<1] * mlazy[a] + lazy[a])%p;
lazy[(a<<1)|1] = (lazy[(a<<1)|1] * mlazy[a] + lazy[a])%p;
tree[a<<1] = (tree[a<<1] * mlazy[a])%p;
tree[a<<1|1] = (tree[a<<1|1] * mlazy[a])%p;
tree[a<<1] = (tree[a<<1] + (((l+r)>>1)-l+1) * lazy[a])%p;
tree[a<<1|1] = (tree[a<<1|1] + (r-((l+r)>>1)) * lazy[a])%p;
mlazy[a]=1;
lazy[a]=0;
}
}
void change(int l,int r,int k,int ln,int rn,int a)
{
// print(1,n,1);
// printf("\n");
// if(ln>r||rn<l)return;
if(ln>=l && rn<=r)
{
lazy[a] = (lazy[a] + k)%p;
tree[a] = (tree[a] + ((rn-ln+1) * k)%p)%p;
return;
}
if(ln==rn)return;
push_down(a,ln,rn);
int mid=(ln+rn)>>1;
if(l<=mid) change(l,r,k,ln,mid,a<<1);
if(r>mid) change(l,r,k,mid+1,rn,a<<1|1);
push_up(a);
}
void mchange(int l,int r,int k,int ln,int rn,int a)
{
// for(int i=1;i<=n*4;i++)printf("%lld ",tree[i]);
// printf("\n");
// print(1,n,1);
// printf("\n");
// if(ln>r||rn<l)return;
if(ln>=l && rn<=r)
{
mlazy[a] = (mlazy[a] * k)%p;
lazy[a] = (lazy[a] * k)%p;
tree[a] = (tree[a] * k)%p;
return;
}
if(ln==rn)return;
push_down(a,ln,rn);
int mid=(ln+rn)>>1;
if(l<=mid) mchange(l,r,k,ln,mid,a<<1);
if(r>mid) mchange(l,r,k,mid+1,rn,a<<1|1);
push_up(a);
}
void sum(int l,int r,int ln,int rn,int a)
{
//printf("1 ");
//printf("%d %d %d %d\n",ans,a,ln,rn);
if(ln>=l && rn<=r)
{
ans += tree[a];
ans%=p;
// printf("%d %d %d %d\n",ans,a,ln,rn);
return;
}
if(ln==rn)return;
push_down(a,ln,rn);
int mid=(ln+rn)>>1;
if(l<=mid) sum(l,r,ln,mid,a<<1);
if(r>mid) sum(l,r,mid+1,rn,a<<1|1);
push_up(a);
}
int main()
{
n=read(),m=read(),p=read();
build(1,n,1);
// for(int i=1;i<=n*4;i++)printf("%lld ",tree[i]);
// printf("\n");
for(int i=1;i<=m;i++)
{
z=read();
// printf("1 ");
if(z==1)
{
int z1=read(),z2=read(),k=read();
mchange(z1,z2,k,1,n,1);
}
if(z==2)
{
int z1=read(),z2=read(),k=read();
change(z1,z2,k,1,n,1);
}
if(z==3)
{
int z1=read(),z2=read();
sum(z1,z2,1,n,1);
printf("%lld\n",ans%p);
ans=0;
}
}
}
求大佬指教QwQ