[Ynoi2015] 纵使日薄西山

题传

考虑一个 \(a_i\) 变为最大值的时候，由于它与两边的值相对大小不变，因此 \(a_i\) 造成的贡献必然是它自己，进一步地，题目操作可以简化为每次选择一个靠左地最大值，将其和左右删除，删除代价为最大值。

考虑最终是哪些值作为最大值被删除，手摸一会样例，将最终选出来的序列拆分成若干个单调序列，发现奇偶性是相同的（因为每删除一个值就会将两边奇偶性不同的删除），注意单调序列之间的位置要小分讨，计算贡献时把每个单调队列的头塞入 set 中，这样就珂以快速计算贡献了。

对于单点修改，首先其自身和其前后形成的单调序列的方向会改变，注意相邻两位的贡献都会因为序列的方向而贡献产生变化，拿个树状数组记录前缀和即可，

复杂度 \(O(n\log n)\)。

Code:

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cctype>
#include <vector>
#include <queue>
#include <bitset>
#include <set>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define int long long
using namespace std;
typedef long long ll;
typedef pair <int, int> Pii;
const int INF=0x3f3f3f3f;
const int cp=1e9+7;
inline int plust(int x, int y){x+=y;if(x>=cp) x-=cp;if(x<0) x+=cp;return x;}
inline int minut(int x, int y){x-=y;if(x>=cp) x-=cp;if(x<0) x+=cp;return x;}
inline int read(){
	char ch=getchar();int x=0, f=1;
	while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f;
}
inline void write(int x){
    if(x<0) putchar('-'), x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline int ksm(int a, int b=cp-2){
	int ret=1;
	for(; b; b>>=1, a=1ll*a*a%cp)
		if(b&1) ret=1ll*ret*a%cp;
	return ret;
}
const int N=1e5+5;
int n, m, a[N];
set <int> S;
set <int> :: iterator l, r;
#define lowbit(x) (x&(-x))
int bit[2][N];
void add(int op, int x, int v){for(; x<=n; x+=lowbit(x)) bit[op][x]+=v;}
int query(int op, int x, int t=0){for(; x; x-=lowbit(x)) t+=bit[op][x];return t;}
int rangeQ(int op, int l, int r){return query(op, r)-query(op, l-1);}
#undef lowbit
bool checkin(int x){return (a[x-1]<a[x]&&a[x]>=a[x+1])||(a[x-1]>=a[x]&&a[x]<a[x+1]);}
ll ans;
ll value(int x){
	if(S.find(x)==S.end()||x<1||x>n) return 0;
	if(x==1){int nxt=*S.upper_bound(x);return a[x]<a[nxt]?query(nxt&1, nxt-1):0;}
	if(x==n){int lst=*(--S.lower_bound(x));return a[x]<=a[lst]?rangeQ(lst&1, lst, x):a[x];}
	int lst=*(--S.lower_bound(x)), nxt=*S.upper_bound(x);
	if(a[x]<=a[lst]&&a[x]<a[nxt]){
		int tmp=rangeQ(lst&1, lst, x-1)+rangeQ(nxt&1, x+1, nxt-1);
		return ((x&1)==(lst&1)&&(x&1)==(nxt&1))?(tmp+a[x]):tmp;
    }
    return 0;
}
signed main(){
	n=read();
	for(int i=1; i<=n; ++i) a[i]=read(), add(i&1, i, a[i]);
	S.insert(0), S.insert(1), S.insert(-1), S.insert(-2);
	S.insert(n), S.insert(n+1), S.insert(n+2), S.insert(n+3);
	for(int i=2; i<n; ++i) if(checkin(i)) S.insert(i);
	for(auto v:S) ans+=value(v);
	m=read();
	for(int i=1; i<=m; ++i){
		int x=read(), y=read();ans-=value(x);
        l=S.lower_bound(x);r=S.upper_bound(x);
        l--;ans-=value(*l)+value(*r);
        l--, r++;ans-=value(*l)+value(*r);
        S.erase(x);S.erase(x-1);S.erase(x+1);
		add(x&1, x, -a[x]), a[x]=y, add(x&1, x, a[x]);
		for(int j=x-1; j<=x+1; ++j)
			if((j>1&&j<n)&&checkin(j)) S.insert(j);
			else if(j<=1||j>=n) S.insert(j);
		while(l!=r) ans+=value(*l), ++l;
        ans+=value(*r);
		printf("%lld\n", ans);
	}
	return 0;
}