题解 喜欢序列 题解

F 喜欢序列

观察到每次操作会分别在左右端点分裂一段序列或者合并两段序列，用 set 维护即可。

//Man always remember love because of romance only!
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
set<int> s;
int a[200001];
int tr[800001],tag[800001];
void pushup(int x){
	tr[x]=max(tr[x<<1],tr[x<<1|1]);
}
void pushdown(int x){
	if(tag[x]){
		tag[x<<1]+=tag[x];
		tag[x<<1|1]+=tag[x];
		tr[x<<1]+=tag[x];
		tr[x<<1|1]+=tag[x];
		tag[x]=0;
	}
}
int maxn[4000001];
void build(int x,int l,int r){
	if(l==r){
		tr[x]=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	pushup(x);
}
void update(int x,int k,int l,int r,int nl,int nr){
	if(nl<=l&&nr>=r){
		tr[x]+=k;
		tag[x]+=k;
		return;
	}
	pushdown(x);
	int mid=(l+r)/2;
	if(mid>=nl) update(x<<1,k,l,mid,nl,nr);
	if(mid<nr) update(x<<1|1,k,mid+1,r,nl,nr);
	pushup(x);
}
int query(int x,int l,int r,int nl,int nr){
	if(nl<=l&&nr>=r) return tr[x];
	int res=-1e9,mid=(l+r)/2;
	pushdown(x);
	if(mid>=nl) res=max(res,query(x<<1,l,mid,nl,nr));
	if(mid<nr) res=max(res,query(x<<1|1,mid+1,r,nl,nr));
	return res;
}
signed main(){
	int n=read(),q=read();
	for(int i=1;i<=n;i++) a[i]=read();
	build(1,1,n);
	int ans=0;
	for(int i=1;i<=n;i++){
		int l=i,r=i;
		while(r<n&&a[r+1]==a[r]+1) r++;
		s.insert(l);
		i=r; 
		ans+=(r-l+1)*(r-l+1);
	}
	s.insert(n+1);
	while(q--){
		int l=read(),r=read(),w=read();
		auto itl=s.upper_bound(l);itl--;
		auto itr=s.upper_bound(r);
		update(1,w,1,n,l,r);
		int l1=*itl,l2=l;
		if(l1!=l2){
			if(w!=0){
				auto tp=itl;tp++;
				ans-=((*tp)-l1)*((*tp)-l1);
				ans+=(l2-l1)*(l2-l1);
				ans+=((*tp)-l2)*((*tp)-l2);
				s.insert(l2);
			}
		}else{
			if(itl!=s.begin()){
				if(query(1,1,n,l1-1,l1-1)+1==query(1,1,n,l1,l1)){
					auto tp=itl;tp++;
					int nr=(*tp)-1;
					ans-=((*tp)-l1)*((*tp)-l1);
					tp--,tp--;
					ans-=(l1-(*tp))*(l1-(*tp));
					int nl=*tp;
					ans+=(nr-nl+1)*(nr-nl+1);
					s.erase(l1);
				}
			}
		}
		int r1=*itr,r2=r+1;
		if(r1!=r2){
			if(w!=0){
				auto tp=itr;tp--;
				ans-=(r1-(*tp))*(r1-(*tp));
				ans+=(r2-(*tp))*(r2-(*tp));
				ans+=(r1-r2)*(r1-r2);
				s.insert(r2);
			}
		}else{
			if(r1!=n+1){
				if(query(1,1,n,r1-1,r1-1)+1==query(1,1,n,r1,r1)){
					auto tp=itr;tp++;
					int nr=(*tp)-1;
					ans-=((*tp)-r1)*((*tp)-r1);
					tp--,tp--;
					ans-=(r1-(*tp))*(r1-(*tp));
					int nl=*tp;
					ans+=(nr-nl+1)*(nr-nl+1);
					s.erase(r1);
				}
			}
		}
		write(ans);
		puts("");
	}
	return 0;
}