F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:五月份月赛定于5.27日12:30--17:30,欢迎大家来玩! 2:关于OJ的注册可看https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671
大视野在线测评-欢迎您
[ New Thread ]
Problem 1798 >> 这代码样例都过不了还能过评测?!
2711694897 @ 2017-10-05 21:59:13
[ Quote ] [ Edit ] [ Delete ] 1#
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define N 100010
using namespace std;
typedef long long ll;
ll mul[N<<2],sum[N<<2],add[N<<2];
ll n,mod;
int q;
void pushup(int rt)
{
sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%mod;
}
void pushdown(int rt,ll m)
{
if(mul[rt]!=1||add[rt]!=0)
{
mul[rt<<1]=(mul[rt<<1]*mul[rt])%mod;
mul[rt<<1|1]=(mul[rt<<1|1]*mul[rt])%mod;
add[rt<<1]=(mul[rt]*add[rt<<1]+add[rt])%mod;
add[rt<<1|1]=(mul[rt]*add[rt<<1|1]+add[rt])%mod;
sum[rt<<1]=(sum[rt<<1]*mul[rt]+(m-(m>>1))*add[rt])%mod;
sum[rt<<1|1]=(sum[rt<<1|1]*mul[rt]+(m>>1)*add[rt])%mod;
mul[rt]=1,add[rt]=0;
}
}
void build(int l,int r,int rt)
{
mul[rt]=1,sum[rt]=0;
if(l==r)
{
scanf("%I64d",&sum[rt]);
return;
}
int mid=(l+r)>>1;
build(lson),build(rson);
pushup(rt);
}
void update_mul(int L,int R,int l,int r,int rt,ll c)
{
if(L<=l&&r<=R)
{
mul[rt]=(mul[rt]*c)%mod;
add[rt]=(add[rt]*c)%mod;
sum[rt]=(sum[rt]*c)%mod;
return;
}
pushdown(rt,r-l+1);
int mid=(l+r)>>1;
if(L<=mid)update_mul(L,R,lson,c);
if(R>mid) update_mul(L,R,rson,c);
pushup(rt);
}
void update_add(int L,int R,int l,int r,int rt,ll c)
{
if(L<=l&&r<=R)
{
add[rt]=(add[rt]+c)%mod;
sum[rt]=(sum[rt]+(r-l+1)*c)%mod;
return;
}
pushdown(rt,r-l+1);
int mid=(l+r)>>1;
if(L<=mid)update_add(L,R,lson,c);
if(R>mid)update_add(L,R,rson,c);
pushup(rt);
}
ll query(int L,int R,int l,int r,int rt)
{
ll ret=0;
if(L<=l&&r<=R)
{
return sum[rt];
}
pushdown(rt,r-l+1);
int mid=(l+r)>>1;
if(L<=mid)ret=(ret+query(L,R,lson))%mod;
if(R>mid)ret=(ret+query(L,R,rson))%mod;
return ret;
}
int main()
{
scanf("%lld%lld",&n,&mod);
build(1,n,1);
scanf("%d",&q);
while(q--)
{
int opt;scanf("%d",&opt);
int x,y;scanf("%d%d",&x,&y);
ll z;
switch(opt)
{
case 1:scanf("%lld",&z);update_mul(x,y,1,n,1,z);break;
case 2:scanf("%lld",&z);update_add(x,y,1,n,1,z);break;
case 3:printf("%lld\n",query(x,y,1,n,1));break;
}
}
}
nevvworld @ 2017-10-12 22:00:57
[ Quote ] [ Edit ] [ Delete ] 2#
只能说数据太水了
[Top] [Previous Page] [Next Page]

HOME Back