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大神.
#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); } } }