【vijos1659】河蟹王国

2013年12月30日1,5962

描述

河蟹王国有一位河蟹国王,他的名字叫羊驼。河蟹王国富饶安定,人们和谐相处。有一天,羊驼国王心血来潮,想在一部分人中挑出最和谐的人。于是,羊驼国王将他的子民排成了一列(==!!b汗~好长呀)。每个人都有一个初始的和谐值。羊驼国王每次会选择一个区间[L,R],这个区间中和谐值最大的人就是国王选出的人。而且,在某一时间,区间[L’,R’]里的人会变得熟悉,因此他们每个人的和谐值都会上升一个相同的值C。羊驼国王想知道,对于每一次选择,他选出的最大和谐值是多少。

输入格式

第一行是一个数N(1<=N<=100000),表示人数。

接下来的N行,每行一个数,表示排成的序列第i个人和谐值的初始值。

接下来是一个数M(1<=M<=100000),表示羊驼国王或他的子民有所活动(羊驼国王选择一个区间算一次,某区间里的人增长和谐值算一次)的总次数。

接下来的M行,每行第一个是一个数K,K是1或2,若K=1,接下来有三个数L,R,C,表示区间[L,R]的所有人增加C的和谐值;若K=2,接下来有两个数L,R,表示国王选择了区间[L,R]。

输出格式

每次对于国王选择区间,输出选择区间里的最大和谐值。

样例输入

样例输出

限制

每个测试点1s。

代码

 

  • 一个蠢到死的大沙茶2016年3月14日 下午8:30 回复

    黄学长,请问这段代码如何理解,能不能解释下,代码每步是做什么操作==,谢谢!!!

    void pushdown(int k)
    {
    tr[k<<1].tag+=tr[k].tag;
    tr[k<<1|1].tag+=tr[k].tag;
    tr[k<<1].mx+=tr[k].tag;
    tr[k<<1|1].mx+=tr[k].tag;
    tr[k].tag=0;
    }

    #1  
    • hzwer2016年3月29日 上午12:32 回复
      admin

      左右子区间分别加上标记,左右子区间更新最大值,将该区间标记清空

      #11