CodeForces 1136E-Nastya Hasn't Written a Legend（二分优化线段树）

题目链接：https://codeforces.com/problemset/problem/1136/E

题目大意：给你n个数$a_i$，n-1个附加值$k_i$，操作1，将第$x$位置的值加上$val$如果，此时$a_x+k_x>a_{x+1}$那么$a_{x+1}=a_x+k_x$以此类推直到不满足为止，操作2，查询$[l,r]$的和。

Examples

Input

Output

5
7
8

Input

Output

emmm，可以先整个暴力的，单点更新的时候如果后面的那个数满足更新条件就再次单点更新。。。然后T在22了，以下是暴力代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define lc rt<<1
#define rc rt<<1|1
typedef long long ll;
const int mac=1e5+10;
const int inf=1e9+10;

ll sum[mac<<2],a[mac];
int b[mac],n;

void push_up(int rt)
{
    sum[rt]=sum[lc]+sum[rc];
}

void build(int l,int r,int rt)
{
    if (l==r){
        scanf ("%lld",&a[l]);
        sum[rt]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lson);build(rson);
    push_up(rt);
}

void update(int l,int r,int rt,int pos,ll x,int id)
{
    if (l==r){
        if (id) {sum[rt]=x; a[l]=x;}
        else {sum[rt]+=x; a[l]+=x;}
        if (l<n && a[l]+b[l]>a[l+1]) update(1,n,1,l+1,a[l]+b[l],1);
        return;
    }
    int mid=(l+r)>>1;
    if (mid>=pos) update(lson,pos,x,id);
    else update(rson,pos,x,id);
    push_up(rt);
}

ll query(int l,int r,int rt,int L,int R)
{
    ll ans=0;
    if (l>=L && r<=R) return sum[rt];
    int mid=(l+r)>>1;
    if (mid>=L) ans+=query(lson,L,R);
    if (mid<R) ans+=query(rson,L,R);
    return ans;
}

int main()
{
    //freopen("in.txt","r",stdin);
    int q;
    scanf ("%d",&n);
    //for (int i=1; i<=10; i++) printf("%lld ",sum[i]);printf("
");
    build(1,n,1);
    for (int i=1; i<n; i++)
        scanf ("%d",&b[i]);
    scanf ("%d",&q);
    while (q--){
        char s[5];
        int pos,x,l,r;
        scanf ("%s",s);
        if (s[0]=='+'){
            scanf ("%d%d",&pos,&x);
            update(1,n,1,pos,1LL*x,0);
        }
        else {
            scanf ("%d%d",&l,&r);
            printf("%lld
",query(1,n,1,l,r));
        }
    }
    return 0;
}

View Code

然后我们就要考虑怎么优化了，实际上我们应该知道更新的过程是一个单调的，也就是说如果要从$i$更新到$j$那么$i$和$j$之间的也一定会更新，后面的一定不存在更新条件。也就是说我们可以考虑用二分来找到需要更新的最远的那个点，然后进行区间修改而不是单点修改。接下来的关键就是怎么找，对于合法的序列有以下式子：

$a_1+k_1<=a_2$

$a_2+k_2<=a_3$

$a_3+k_3<=a_4$

$vdots $

$a_i+k_i<=a_{i+1}$

那么做个合并就是$a_1+sum_{j=1}^{i}<=a_{i+1}$，那么对于不满足的情况就是大于了，我们直接对$k$值做个前缀和然后二分找到最远的位置。二分如下：

scanf ("%d%d",&pos,&val);
ll now=query(1,n,1,pos,pos);
int lf=pos,rf=n,res=pos;
while (lf<=rf) {
    int mid=(lf+rf)>>1;
    ll tmp=query(1,n,1,mid,mid);
    if (tmp<now+val+sum[mid-1]-sum[pos-1]) {
        res=mid;
        lf=mid+1;
    }
    else rf=mid-1;
}

然后就是区间更新的操作了，对于整个区间来讲，由于是更新区间，那么一定有$a_x=a_{x-1}+k_{x-1}$，那么也就是说对于整个区间$[l,r]$来讲，他们在变化之后整个区间的和值$sum$变化如下：

$sum=a_l+x+a_l+x+k_l+a_l+x+k_l+k_2+a_l+x+k_l+k_2+k_3cdots $

令$b_l=a_l+x$

$sum=b_l+b_l+k_l+b_l+k_l+k_2+b_l+k_l+k_2+k_3cdots +b_l+k_1+...k_{r-1}$

这里的$k$值的处理比较麻烦，要对前缀和再做个前缀和，那么对于第$l$个数而言，其$ss[l]=k_1+k_2+...k_l$但实际上我们只需要$k_l$所以我们需要对区间中每个数再减去$s[l-1]$，那么就会得到如下式子：

$sum[l,r]=(a_1+x-s[l-1])*(r-l+1)+sum_{i=l-2}^{r-1}s[i]$

那么代码也就出来了，还需要注意的一点是打标记别打0。。。打个永远也达不到的值。

以下是AC代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define lc rt<<1
#define rc rt<<1|1
typedef long long ll;
const int mac=1e5+10;
const ll inf=-1e18+10;

struct node
{
    int l,r;
    ll sum,f;
}tree[mac<<2];
int b[mac];
ll sum[mac],ss[mac];

int deal(int x){return x>=0?x:0;}

void build(int l,int r,int rt)
{
    tree[rt].f=inf;
    tree[rt].l=l; tree[rt].r=r;
    if (l==r){
        scanf ("%lld",&tree[rt].sum);
        return;
    }
    int mid=(l+r)>>1;
    build(lson);build(rson);
    tree[rt].sum=tree[lc].sum+tree[rc].sum;
}

void push_down(int rt)
{    
    tree[lc].sum=tree[rt].f*(tree[lc].r-tree[lc].l+1)+ss[tree[lc].r-1]-ss[deal(tree[lc].l-2)];
    tree[rc].sum=tree[rt].f*(tree[rc].r-tree[rc].l+1)+ss[tree[rc].r-1]-ss[deal(tree[rc].l-2)];
    tree[lc].f=tree[rt].f; tree[rc].f=tree[rt].f;
    tree[rt].f=inf;
}

void update(int l,int r,int rt,int L,int R,ll val)
{
    if (l>=L && r<=R){
        tree[rt].f=val;
        tree[rt].sum=val*(r-l+1)+ss[r-1]-ss[deal(l-2)];
        return;
    }
    int mid=(l+r)>>1;
    if (tree[rt].f!=inf) push_down(rt);
    if (mid>=L) update(lson,L,R,val);
    if (mid<R) update(rson,L,R,val);
    tree[rt].sum=tree[lc].sum+tree[rc].sum;
}

ll query(int l,int r,int rt,int L,int R)
{
    ll ans=0;
    if (l>=L && r<=R) return tree[rt].sum;
    if (tree[rt].f!=inf) push_down(rt);
    int mid=(l+r)>>1;
    if (mid>=L) ans+=query(lson,L,R);
    if (mid<R) ans+=query(rson,L,R);
    return ans;
}

int main()
{
    //freopen("in.txt","r",stdin);
    int n,q;
    scanf ("%d",&n);
    build(1,n,1);
    for (int i=1; i<n; i++)
        scanf ("%d",&b[i]),sum[i]=sum[i-1]+b[i];
    for (int i=1; i<n; i++) ss[i]=ss[i-1]+sum[i];
    scanf ("%d",&q);
    while (q--){
        char s[5];
        int l,r,pos,val;
        scanf ("%s",s);
        if (s[0]=='s') {
            scanf ("%d%d",&l,&r);
            printf("%lld
",query(1,n,1,l,r));
        }
        else {
            scanf ("%d%d",&pos,&val);
            ll now=query(1,n,1,pos,pos);
            int lf=pos,rf=n,res=pos;
            while (lf<=rf){
                int mid=(lf+rf)>>1;
                ll tmp=query(1,n,1,mid,mid);
                if (tmp<now+val+sum[mid-1]-sum[pos-1]){
                    res=mid;
                    lf=mid+1;
                }
                else rf=mid-1;
            }
            update(1,n,1,pos,res,now+val-sum[pos-1]);
        }
    }
    return 0;
}

路漫漫兮