3973: seq

题目描述

小y 的男朋友送给小y 一个数列{ai}{ai}，并且刁难小y 要她维护这个序列。

具体而言，小y 的男朋友要求小y 完成两个操作：

1. 修改数列中的一个数

2. 设pipi表示maxij=1ajmaxj=1iaj，求出n∑i=1pi∑i=1npi。

小y 不会做，于是向你求助。

输入

第一行一个数nn表示数列长度。

第二行nn个由空格隔开的数表示数列aa。

第三行一个数mm表示修改数。

接下来mm行，每行两个数pos,valuepos,value，表示把aposapos改成valuevalue。

输出

mm行，每行一个数，表示对于每次修改后的n∑i=1pi∑i=1npi。

样例输入

<span style="color:#333333"><span style="color:#333333">10

114 357 904 407 100 624 449 897 115 846

20

5 357

6 350

2 939

9 1182

7 1062

2 3300

4 6867

4 2076

3 8458

9 6575

10 5737

10 338

9 10446

4 7615

2 5686

4 10091

1 6466

6 15551

3 10914

7 3234</span></span>

样例输出

<span style="color:#333333"><span style="color:#333333">7703

7703

8565

9051

9297

29814

54783

29814

71078

71078

71078

71078

75054

75054

77440

85605

92737

119327

123429

123429</span></span>

提示

对于前30%30%的数据,n,m≤5000n,m≤5000;

对于前60%60%的数据,n,m≤50000n,m≤50000;

对于100%100%的数据,n≤3×105,ai≤109n≤3×105,ai≤109。

来源

2018年10月hnsdfz集训

solution

传说中的套路题，可是我不会

理解了好久

首先最终每个数的答案一定是递增的，也就是每个数会被之前的某个数“盖住”

我们用线段树维护l~r的答案和最大值

这里的答案只考虑l~r，不受其他影响

那么修改很好实现，主要是怎么维护区间

分类

1.tree[k*2].max>=tree[k*2+1].max

也就是左边完全盖住了右边

那答案就是tree[k*2].max*tree[k*2+1].len+tree[k*2].sum

2.tree[k*2].max<tree[k*2+1].max

左边盖住右边的一小部分

再分类，设M为tree[k*2].max，ls为右儿子的左儿子，rs为右儿子的右儿子

（1）M<tree[ls].max

那么rs的答案是正确的，而左儿子未知

所以递归算左儿子，右儿子用减的

(2)M>tree[ls].max

左儿子被完全盖住，右儿子递归算

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#define ll long long

#define maxn 300005

using namespace std;

int n,m,a[maxn],p,val;

struct node{

    int l,r,len;ll Max,sum;

}tree[maxn*4];

ll pushup(int k,ll v){

    if(v>tree[k].Max)return tree[k].len*v;

    if(tree[k].l==tree[k].r)return max(tree[k].Max,v);

    if(tree[k*2].Max>v){

        return pushup(k*2,v)+tree[k].sum-tree[k*2].sum;

    }//right remain

    if(tree[k*2].Max<=v){

        return tree[k*2].len*v+pushup(k*2+1,v);

    }//left covered

}

void wh(int k){

    tree[k].Max=max(tree[k*2].Max,tree[k*2+1].Max);

    tree[k].sum=tree[k*2].sum+pushup(k*2+1,tree[k*2].Max);

}

void build(int k,int L,int R){

    tree[k].l=L;tree[k].r=R;tree[k].len=R-L+1;

    if(L==R){

        tree[k].Max=tree[k].sum=a[L];return;

    }

    int mid=L+R>>1;

    build(k*2,L,mid);build(k*2+1,mid+1,R);

    wh(k);

}

void change(int k){

    if(tree[k].l==tree[k].r){

        tree[k].sum=tree[k].Max=val;

        return ;

    }

    int mid=tree[k].l+tree[k].r>>1;

    if(p<=mid)change(k*2);

    else change(k*2+1);

    wh(k);

}

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++)scanf("%d",&a[i]);

    build(1,1,n);

    cin>>m;

    for(int i=1;i<=m;i++){

        scanf("%d%d",&p,&val);

        change(1);

        printf("%lld\n",tree[1].sum);

    }

    return 0;

}

巴特西

3973: seq

3973: seq

题目描述

输入

输出

样例输入

样例输出

提示

来源

最新文章

热门文章