。。。。线段树要开4倍的空间,按理来说你这还是过不了
by Chloris @ 2018-07-09 12:09:01
@[Quanta](/space/show?uid=82722)
by Chloris @ 2018-07-09 12:09:10
我说的是原数组
线段树的我开了4 倍了
by everdream @ 2018-07-09 12:16:47
也就是4*137500
by everdream @ 2018-07-09 12:17:33
那个。。。
我想知道线段树的数组为什么要开得4倍空间还大
by everdream @ 2018-07-09 12:41:54
按我的写法要开6倍
求daolao指教
~~~cpp
#include<iostream>
#include<cstdio>
#define maxn 100005
using namespace std;
typedef long long LL;
LL n,m,p,a[maxn],s[maxn*6],add[maxn*6],mul[maxn*6];
inline LL read()
{
LL ret=0;char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9') ret=(ret<<1)+(ret<<3)+(ch^48),ch=getchar();
return ret;
}
inline void pushup(int root){s[root]=(s[root<<1]+s[root<<1|1])%p;}
inline void build(int L,int R,int root)
{
mul[root]=1;
if (L==R){s[root]=a[L];return;}
int mid=(R-L>>1)+L;
build(L,mid,root<<1);
build(mid+1,R,root<<1|1);
pushup(root);
}
inline void pushdown_add(int root,LL a,LL b)
{
if (!add[root]) return;
add[root<<1]=(add[root<<1]+add[root])%p;
add[root<<1|1]=(add[root<<1|1]+add[root])%p;
s[root<<1]=(s[root<<1]+add[root]*a%p)%p;
s[root<<1|1]=(s[root<<1|1]+add[root]*b%p)%p;
add[root]=0;
}
inline void pushdown_mul(int root)
{
if (mul[root]==1) return;
mul[root<<1]=mul[root<<1]*mul[root]%p;
mul[root<<1|1]=mul[root<<1|1]*mul[root]%p;
add[root<<1]=add[root<<1]*mul[root]%p;
add[root<<1|1]=add[root<<1|1]*mul[root]%p;
s[root<<1]=s[root<<1]*mul[root]%p;
s[root<<1|1]=s[root<<1|1]*mul[root]%p;
mul[root]=1;
}
void update_add(int L,int R,LL x,int l,int r,int root)
{
int mid=(r-l>>1)+l;
if (L<=l&&r<=R)
{
pushdown_mul(root);
pushdown_add(root,mid-l+1,r-mid);
add[root]=(add[root]+x)%p;
s[root]=(s[root]+(r-l+1)*x%p)%p;
return;
}
pushdown_mul(root);
pushdown_add(root,mid-l+1,r-mid);
if (L<=mid) update_add(L,R,x,l,mid,root<<1);
if (mid<R) update_add(L,R,x,mid+1,r,root<<1|1);
pushup(root);
}
void update_mul(int L,int R,LL x,int l,int r,int root)
{
int mid=(r-l>>1)+l;
if (L<=l&&r<=R)
{
pushdown_mul(root);
pushdown_add(root,mid-l+1,r-mid);
mul[root]=mul[root]*x%p;
s[root]=s[root]*x%p;
return;
}
pushdown_mul(root);
pushdown_add(root,mid-l+1,r-mid);
if (L<=mid) update_mul(L,R,x,l,mid,root<<1);
if (mid<R) update_mul(L,R,x,mid+1,r,root<<1|1);
pushup(root);
}
LL query(int L,int R,int l,int r,int root)
{
if (L<=l&&r<=R) return s[root]%p;
int mid=(r-l>>1)+l;LL tot=0;
pushdown_mul(root);
pushdown_add(root,mid-l+1,r-mid);
if (L<=mid) tot=query(L,R,l,mid,root<<1);
if (mid<R) tot+=query(L,R,mid+1,r,root<<1|1);
return tot%p;
}
int main()
{
scanf("%lld%lld%lld",&n,&m,&p);
for (int i=1;i<=n;i++) a[i]=read()%p;
build(1,n,1);
while (m--)
{
LL flg=read(),L=read(),R=read();
switch(flg)
{
case 1:{LL x=read();update_mul(L,R,x,1,n,1);break;}
case 2:{LL x=read();update_add(L,R,x,1,n,1);break;}
case 3:{printf("%lld\n",query(L,R,1,n,1));break;}
}
}
return 0;
}
~~~
by everdream @ 2018-07-09 12:49:24
@[Quanta](/space/show?uid=82722) 这个问题很明显啊
满二叉树是$2n+1$
但恶心出题人是不会给你满二叉树的
所以多算一层，≈$4n$
by 初日辉煌 @ 2018-07-15 22:26:01