codeVS 2回目の月試合C
2872 ワード
テーマ説明Description
書類の読み書きは一切しないでください.今回の試合はifndef ONLINEをサポートしません.JUDGE.お互いに伝えてください.評価機はlinux
Jijijieは恐怖の科学の変人で、彼は特殊な邪悪な科学技術Song'ci Crashを持っています.
Dashは彼の家庭農場にn個の連続した所有者の黒と金色が混ざったDa'shgua畑を持っている.Song'ci Crash攻撃は連続するDa'shgua畑を打撃し、[L,R]の範囲内の畑生産量をx(x!=0)からfloor(ln(x))に変える.tty、Long'Aotianクラスの騎士は、彼のknightmare、tgopknightを運転して、Jijieと対戦します.ttyがDa'shgua畑を取り戻すたびに、この畑はOwaski天神の庇護の下で生気を得て、畑の生産量を突然変異させます.
王Papafishは戦況を知りたくて、連続したDa'shgua畑の生産量の和を尋ねる.
機知に富んだあなたは、彼の質問に答えることができますか?
試験場では一見線分樹裸の問題だったが、区間logが同じではないことに気づき、区間を暴力的に書き換え、log(0)が合法ではないことを考慮せずに爆発した.
テーマが与えられた範囲では,最大log 4回で0になるので,区間内sumが0でない数を線分ツリー上で修正すればよい,最大4 n,通過可能である.(TMは本当に線分樹の裸問題だ).
%%%__debug大神.
書類の読み書きは一切しないでください.今回の試合はifndef ONLINEをサポートしません.JUDGE.お互いに伝えてください.評価機はlinux
Jijijieは恐怖の科学の変人で、彼は特殊な邪悪な科学技術Song'ci Crashを持っています.
Dashは彼の家庭農場にn個の連続した所有者の黒と金色が混ざったDa'shgua畑を持っている.Song'ci Crash攻撃は連続するDa'shgua畑を打撃し、[L,R]の範囲内の畑生産量をx(x!=0)からfloor(ln(x))に変える.tty、Long'Aotianクラスの騎士は、彼のknightmare、tgopknightを運転して、Jijieと対戦します.ttyがDa'shgua畑を取り戻すたびに、この畑はOwaski天神の庇護の下で生気を得て、畑の生産量を突然変異させます.
王Papafishは戦況を知りたくて、連続したDa'shgua畑の生産量の和を尋ねる.
機知に富んだあなたは、彼の質問に答えることができますか?
試験場では一見線分樹裸の問題だったが、区間logが同じではないことに気づき、区間を暴力的に書き換え、log(0)が合法ではないことを考慮せずに爆発した.
テーマが与えられた範囲では,最大log 4回で0になるので,区間内sumが0でない数を線分ツリー上で修正すればよい,最大4 n,通過可能である.(TMは本当に線分樹の裸問題だ).
%%%__debug大神.
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=100001,MAXM=400001,MAXNODE=3*MAXN;
int n,m,w[MAXN];
struct SegMentTree{
long long sum[MAXNODE];
SegMentTree(){memset(sum,0,sizeof(sum));}
void maintain(int now)
{
int lc=now<<1,rc=now<<1|1;
sum[now]=sum[lc]+sum[rc];
}
void set(int now,int l,int r,int o,int v)
{
if(l==r&&l==o)
{
sum[now]=0;
sum[now]+=v;
return;
}
int mid=(l+r)>>1,lc=now<<1,rc=now<<1|1;
if(o<=mid)
set(lc,l,mid,o,v);
else
set(rc,mid+1,r,o,v);
maintain(now);
}
void query(int now,int l,int r,int ql,int qr,long long& ans)
{
if(l>=ql&&r<=qr)
{
ans+=sum[now];
return;
}
int mid=(l+r)>>1,lc=now<<1,rc=now<<1|1;
if(ql<=mid)
query(lc,l,mid,ql,qr,ans);
if(qr>mid)
query(rc,mid+1,r,ql,qr,ans);
}
void change(int now,int l,int r,int ql,int qr)
{
if(!sum[now])return;
if(l==r)
{
sum[now]=log(sum[now]);
return;
}
int mid=(l+r)>>1,lc=now<<1,rc=now<<1|1;
if(ql<=mid)
change(lc,l,mid,ql,qr);
if(qr>mid)
change(rc,mid+1,r,ql,qr);
maintain(now);
}
}Tree;
void Read(int &x)
{
x=0;int flag=0;char c;
while(c=getchar())
{
if(c>='0'&&c<='9'){flag=1;x*=10;x+=c-'0';}
else if(flag)break;
}
}
int main()
{
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
Read(n);Read(m);
for(int i=1;i<=n;i++)
{
int a;
Read(a);
Tree.set(1,1,n,i,a);
}
int op,a,b;
for(int i=1;i<=m;i++)
{
long long ans=0;
Read(op);Read(a);Read(b);
if(op==1)
Tree.set(1,1,n,a,b);
else if(op==2)
Tree.change(1,1,n,a,b);
else if(op==3)
{
Tree.query(1,1,n,a,b,ans);
printf("%I64d
",ans);
}
}
}