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。
来源
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;
}
