C. Alyona and towers
题目大意
现在有\(n\)个数，\(m\)个操作，每次区间加一个数，对于每一次操作，你要找出最长的$\ a_l...a_r\ $，满足
\[\exists k\! \in\![l,r],a_l<a_{l+1}<a_{l+2}<...<a_k>a_{k+1}>a_{k+2}>...>a_r \]输出其长度。
分析
我们考虑，前一段是递增，后一段是递减，的最长子段长。
与子段有关，我们考虑维护一个从左端点和右端点以及整个区间维护的值。
这里，最难想到的应该是差分。但其实，因为我们考虑相对数字关系时，最常见的思路，是考虑差分。同时，因为我们进行的是区间加，差分也可以将区间加变为单点加。如果不转为差分，我们很难在区间加的时候维护相对的数字。这里也是比较常见的思路。
我们维护其差分数组。我们发现我们要求的变为了。
求最长的前一段是正数，后一段是负数的子段。
根据我们的经验，我们很容易的能想出，维护的三个值分别为。
mx表示维护的区间的符合条件的最大值。lmx区间内从左端点开始的最大的符合条件的值。rmx区间内以右端点结束的最大的符合条件的值。
接下来直接看代码就好啦。
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
struct Node
{
int l,r;
LL mx,lmx,rmx;
}tr[N<<2];
int n,m;
LL a[N],b[N];
int getsign(LL x)
{
return x>0?1:-1;
}
void pushup(int u)
{
tr[u].mx = max(tr[u<<1].mx,tr[u<<1|1].mx);
tr[u].mx = max(tr[u].mx,max(tr[u<<1].lmx,tr[u<<1|1].rmx));
if(!b[tr[u<<1].r]||!b[tr[u<<1|1].l]||getsign(b[tr[u<<1].r])<getsign(b[tr[u<<1|1].l]))
tr[u].rmx = tr[u<<1|1].rmx,tr[u].lmx = tr[u<<1].lmx;
else
{
tr[u].mx = max(tr[u].mx,tr[u<<1].rmx+tr[u<<1|1].lmx);
tr[u].rmx = tr[u<<1|1].rmx,tr[u].lmx = tr[u<<1].lmx;
if(tr[u<<1].lmx==tr[u<<1].r-tr[u<<1].l+1) tr[u].lmx += tr[u<<1|1].lmx;
if(tr[u<<1|1].rmx==tr[u<<1|1].r-tr[u<<1|1].l+1) tr[u].rmx += tr[u<<1].rmx;
}
}
void build(int u,int l,int r)
{
if(l==r)
{
tr[u] = {l,r};
if(!b[l]) tr[u].mx = tr[u].lmx = tr[u].rmx = 0;
else tr[u].mx = tr[u].lmx = tr[u].rmx = 1;
return ;
}
tr[u] = {l,r};
int mid = l + r >> 1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
void modify(int u,int x,int k)
{
if(tr[u].l==tr[u].r)
{
b[x] += k;
if(!b[x]) tr[u].mx = tr[u].lmx = tr[u].rmx = 0;
else tr[u].mx = tr[u].lmx = tr[u].rmx = 1;
return ;
}
int mid = tr[u].l + tr[u].r >> 1;
if(x<=mid) modify(u<<1,x,k);
else modify(u<<1|1,x,k);
pushup(u);
}
int main()
{
ios;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
if(n==1)
{
cin>>m;
for(int i=1;i<=m;i++)
{
int l,r,d;cin>>l>>r>>d;
cout<<"1\n";
}
return 0;
}
for(int i=1;i<n;i++) b[i] = a[i+1] - a[i];
build(1,1,n-1);
cin>>m;
while(m--)
{
int l,r,d;cin>>l>>r>>d;
if(l!=1) modify(1,l-1,d);
if(r!=n) modify(1,r,-d);
cout<<tr[1].mx+1<<'\n';
}
return 0;
}