CF739C Alyona and towers 题解
题意
给你一个数组，每次区间加后求最长单峰。
思路
考虑一个区间加的常用 trick，将数组差分，于是每次区间加只需要在差分数组上修改两处即可。
单峰的定义在差分数组上变为前一部分为正整数，后一部分为负整数的子序列。
考虑使用两个 set 维护最长单峰，第一个 set 用来维护单峰的划分情况，第二个 multiset 用来维护所有已划分出的单峰的长度。
由于差分后单峰定义只和子序列里元素的符号有关，所以只用管元素符号变化的情况，但是要注意 0 元素的特判。
省流：大分讨
当正数变负数时，若该元素不为单峰里的最后一个元素，将该元素所在的单峰按该元素的位置切成两半，若该元素为单峰里的第一个元素且前面不是 0，则将该元素合并到前面一个单峰上去，注意若该元素之后的数都为负数，则后面的数也要合并到前面去。
负数变正数时同理。
当非 0 变为 0 时，前后切割即可。
当 0 变非 0 时，左右分情况合并。
对于维护单峰长度，每次操作时将会被影响的单峰的长度在第二个 multiset 里删除，操作完后再塞回 multiset 就行。
上面的简化了很多情况写的时候还是要注意多分析。
思路还算简单，代码也许不是很易懂，反正我写的依托（总比线段树分讨好写）。
码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MaxN=300000;
typedef multiset<int,greater<int>>::iterator Iter;
multiset<int,greater<int>>ans;
struct ODT{
ODT(int l,int r):l(l),r(r){
it=ans.insert(r-l+1);
}
ODT(const ODT&obj){
l=obj.l;
r=obj.r;
it=ans.insert(*obj.it);
}
~ODT(){
ans.erase(it);
}
int l,r;
Iter it;
bool operator<(const ODT&obj)const{return l>obj.l;}
};
multiset<ODT>tree;
int n,a[MaxN+1],m;
int arr[MaxN+1];
set<ODT>::iterator Merge(set<ODT>::iterator it,int pos,int val){
arr[pos]+=val;
int l=it->l,r=it->r;
auto p=tree.lower_bound(ODT(l-1,0));
if(p!=tree.end()&&p->r+1==l&&(arr[p->r]>0||(arr[p->r]<0&&arr[l]<0))){
int temp=p->l;
tree.erase(it);
tree.erase(p);
it=tree.emplace(temp,r);
}
l=it->l,r=it->r;
p=tree.lower_bound(ODT(r+1,0));
if(p!=tree.end()&&r==p->l-1&&(arr[r]>0||(arr[r]<0&&arr[p->l]<0))){
int temp=p->r;
tree.erase(it);
tree.erase(p);
it=tree.emplace(l,temp);
}
arr[pos]-=val;
return it;
}
void Update(int pos,int x){
if(pos<=1)return;
if(pos>n)return;
if(arr[pos]==0&&arr[pos]+x!=0){
Merge(tree.emplace(pos,pos),pos,x);
}else if(arr[pos]!=0&&arr[pos]+x==0){
auto it=tree.lower_bound(ODT(pos,0));
int l=it->l,r=it->r;
tree.erase(it);
if(arr[pos]>0){
if(l<=pos-1)Merge(tree.emplace(l,pos-1),pos,x);
if(pos+1<=r)Merge(tree.emplace(pos+1,r),pos,x);
}else{
if(l<=pos-1)Merge(tree.emplace(l,pos-1),pos,x);
if(pos+1<=r)Merge(tree.emplace(pos+1,r),pos,x);
}
}else{
auto it=tree.lower_bound(ODT(pos,0));
int l=it->l,r=it->r;
if(arr[pos]>0&&arr[pos]+x<0){
tree.erase(it);
Merge(tree.emplace(l,pos),pos,x);
if(pos+1<=r)Merge(tree.emplace(pos+1,r),pos,x);
}else if(arr[pos]<0&&arr[pos]+x>0){
tree.erase(it);
if(l<=pos-1)Merge(tree.emplace(l,pos-1),pos,x);
Merge(tree.emplace(pos,r),pos,x);
}
}
arr[pos]+=x;
}
void Solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
arr[1]=0;
for(int i=2;i<=n;i++)arr[i]=a[i]-a[i-1];
int last=1,p=1;
while(p<=n){
int cnt=0;
while(p<=n&&arr[p]>0)p++,cnt++;
while(p<=n&&arr[p]<0)p++;
if(last>=p){
p++;
last=p;
}else{
tree.emplace(last,p-1);
last=p;
}
}
cin>>m;
for(int i=1;i<=m;i++){
int l,r,d;
cin>>l>>r>>d;
Update(l,d);
Update(r+1,-d);
cout<<max(1ll,*ans.begin()+1)<<'\n';
}
}
#undef int
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
Solve();
return 0;
}