题解 CF739C 【Alyona and towers】
MyukiyoMekya
·
·
题解
线段树打标记
首先我们对整个数组做一次差分，这样可以更好的反应两个数之间的大小关系，以及可以把区间加变成单点加
这样就不用 pushdown 传 lazytag 了
转换为差分后就可以把问题转换一下：
求 [l,r] 之间最长的一个连续段使得：由一个连续的负数段和一个连续的正数段拼接起来
先说明节点信息意思：u 当前节点，lson 左子节点，rson 右子节点
$up_{u}$ 当前节点区间从最左开始往右的答案的长度
$down_{u}$ 当前节点区间从最右开始往左的答案的长度
转移：
显然，$ans_u=\max(ans_{lson},ans_{rson})
如果 lson 和 rson 区间的交点的两个位置中有 1 个是 0，或者 lson 的交点是负数而 rson 的交点是正数
那么说明 lson 和 rson 不可能把两个区间合并拼成一个新答案
所以，up_u=up_{lson},down_u=down_{rson}
如果可以合并：
那么可以更新一下答案： ans_u=\max(ans_{lson},ans_{rson},down_{lson}+up_{rson})
如果 up_{lson} 的长度恰好等于 lson 的区间长度，那么就可以把 up_{lson} 和 up_{rson} 合并在一起变成 up_u
否则 up_u=up_{lson}
```cpp
// This code writed by chtholly_micromaker(MicroMaker)
#include <bits/stdc++.h>
#define reg register
#define int long long
using namespace std;
const int MaxN=300050;
struct Node
{
int Ans;
int l,r;
int uplen,downlen;
}tr[MaxN<<2];
template <class t> inline void read(t &s)
{
s=0;
reg int f=1;
reg char c=getchar();
while(!isdigit(c))
{
if(c=='-')
f=-1;
c=getchar();
}
while(isdigit(c))
s=(s<<3)+(s<<1)+(c^48),c=getchar();
s*=f;
return;
}
#define lson (u<<1)
#define rson (u<<1|1)
int a[MaxN],inp[MaxN];
int n;
inline int getsign(int x)
{
if(!x)
return 0;
return x>0?1:-1;
}
inline void checkmax(int &x,int y)
{
if(x<y)
x=y;
return;
}
inline void pushup(int u)
{
tr[u].Ans=max(tr[lson].Ans,tr[rson].Ans);
checkmax(tr[u].Ans,max(tr[lson].uplen,tr[rson].downlen));
if(!a[tr[lson].r]||!a[tr[rson].l]||
getsign(a[tr[lson].r])<getsign(a[tr[rson].l]))
{
tr[u].uplen=tr[lson].uplen,tr[u].downlen=tr[rson].downlen;
}
else
{
checkmax(tr[u].Ans,tr[lson].downlen+tr[rson].uplen);
if(tr[lson].uplen==tr[lson].r-tr[lson].l+1)
tr[u].uplen=tr[lson].uplen+tr[rson].uplen;
else
tr[u].uplen=tr[lson].uplen;
if(tr[rson].downlen==tr[rson].r-tr[rson].l+1)
tr[u].downlen=tr[rson].downlen+tr[lson].downlen;
else
tr[u].downlen=tr[rson].downlen;
}
return;
}
inline void print()
{
for(int i=1;i<=20;++i)
{
puts("======================");
printf("Node [ %lld , %lld ]\n",tr[i].l,tr[i].r);
printf("Ans %lld\n",tr[i].Ans);
printf("up %lld down %lld\n",tr[i].uplen,tr[i].downlen);
}
puts("-=-==");
for(int i=1;i<=6;++i)
printf("%d ",a[i]);puts("");
puts("======");
return;
}
inline void buildtr(int u,int l,int r)
{
tr[u].l=l;tr[u].r=r;
if(l==r)
{
if(!a[l])
tr[u].Ans=tr[u].uplen=tr[u].downlen=0;
else
tr[u].uplen=tr[u].downlen=tr[u].Ans=1;
return;
}
reg int mid=(l+r)>>1;
buildtr(lson,l,mid);
buildtr(rson,mid+1,r);
pushup(u);
return;
}
inline void modify(int u,int l,int r,int p,int k)
{
if(l==r)
{
a[l]+=k;
if(!a[l])
tr[u].Ans=tr[u].uplen=tr[u].downlen=0;
else
tr[u].Ans=tr[u].uplen=tr[u].downlen=1;
return;
}
reg int mid=(l+r)>>1;
if(p<=mid)
modify(lson,l,mid,p,k);
else
modify(rson,mid+1,r,p,k);
pushup(u);
return;
}
signed main(void)
{
// freopen("J.in","r",stdin);
// freopen("J.out","w",stdout);
int m;
cin>>n;
for(int i=1;i<=n;++i)
read(inp[i]);
if(n==1)
{
cin>>m;
for(int i=1;i<=m;++i)
puts("1");
return 0;
}
for(int i=1;i<n;++i)
a[i]=inp[i+1]-inp[i];
buildtr(1,1,n-1);
cin>>m;
reg int l,r,d;
for(int i=1;i<=m;++i)
{
// puts("O-oooooooooo AAAAE-A-A-I-A-U- JO-oooooooooooo AAE-O-A-A-U-U-A- E-eee-ee-eee AAAAE-A-E-I-E-A- JO-ooo-oo-oo-oo EEEEO-A-AAA-AAAA");
read(l);read(r);read(d);
if(l!=1)
modify(1,1,n-1,l-1,d);
if(r!=n)
modify(1,1,n-1,r,-d);
// if(l!=1)
// printf("modify %d +\n",l-1);
// if(r!=n)
// printf("modify %d -\n",r);
printf("%lld\n",tr[1].Ans+1);
// print();
}
return 0;
}
```