CF739C Alyona and towers题解

· · 题解

$\rm Difficulty:2500

题意

给出一个长度为 n(1\le n\le3\times10^5) 的序列 a(1\le a_i\le10^9)，q(1\le q\le3\times10^5) 次区间加，每次操作后回答最长的区间 [l,r] 长度使得

\exists k\! \in\![l,r],a_l<a_{l+1}<a_{l+2}<...<a_k>a_{k+1}>a_{k+2}>...>a_r

广义矩乘

没学过矩乘请前往矩乘模板或看其它题解的思路。

我们先回顾常用的矩乘，假设 A 为一个 n \times k 的矩阵，B 为一个 k \times m 的矩阵，C=A \times B。

那么对于 1\le i \le n,1 \le j \le m ，有：

C_{i,j}=\sum_{p=1}^k A_{i,p}\times B_{p,j}

广义矩乘就是把求和和乘法换成别的运算。

在广义矩阵乘法中，对于 1\le i \le n,1 \le j \le m ，有：

C_{i,j}=\oplus_{p=1}^k A_{i,p}\otimes B_{p,j}

这里要求两种算法有分配律，即对于任意 x,y,z，满足：

(x\oplus y)\otimes z=(x\otimes z)\oplus(y\otimes z)

例如，在常用的矩乘中，有 (x+y)\times z=(x\times z)+(y\times z).

本题做法

本题中，我们使用的广义矩阵乘法为 C_{i,j}=\max_{p=1}^k A_{i,p}+ B_{p,j}，两种运算显然满足分配律。

考虑直接 dp 怎么做。

设 f_i 表示以 i 结尾的最长上升子串长度，不难得出转移式：

f_i=\begin{cases}f_{i-1}+1 & a_i>a_{i-1} \\ 1 & a_i\le a_{i-1}\end{cases}

设 g_i 表示以 i 结尾的最长先上升后下降子串长度，不难得出转移式：

g_i=\begin{cases}\max(f_{i-1}+1,g_{i-1}+1) & a_i<a_{i-1} \\ 1 & a_i\ge a_{i-1}\end{cases}

设 ans_i 表示到 i 为止最长满足要求的子串长度，即 ans_i=\max\{f_i,g_i,ans_{i-1}\}。

将 f_i 和 g_i 的转移式代入可得：

ans_i=\begin{cases}\max\{1,f_{i-1}+1,ans_{i-1}\} & a_i>a_{i-1} \\ \max(1,ans_{i-1}) & a_i=a_{i-1} \\ \max\{1,f_{i-1}+1,g_{i-1}+1,ans_{i-1}\} & a_i<a_{i-1}\end{cases}

于是，我们可以得出状态矩阵：

\begin{bmatrix} f_i & g_i & 0 & ans_i \end{bmatrix}

以及三个转移矩阵。

当 a_i>a_{i-1} 时，转移矩阵为：

\begin{bmatrix} 1 & -\infin & -\infin & 1 \\ -\infin & -\infin & -\infin & -\infin \\ 1 & 1 & 0 & 1 \\ -\infin & -\infin & -\infin & 0 \end{bmatrix}

当 a_i=a_{i-1} 时，转移矩阵为：

\begin{bmatrix} -\infin & -\infin & -\infin & -\infin \\ -\infin & -\infin & -\infin & -\infin \\ 1 & 1 & 0 & 1 \\ -\infin & -\infin & -\infin & 0 \end{bmatrix}

当 a_i<a_{i-1} 时，转移矩阵为：

\begin{bmatrix} -\infin & 1 & -\infin & 1 \\ -\infin & 1 & -\infin & 1 \\ 1 & 1 & 0 & 1 \\ -\infin & -\infin & -\infin & 0 \end{bmatrix}

注意本题中的区间加减并不用真的去区间加减，只需要在差分数组上修改两个位置就好了，a_i 和 a_{i-1} 之间的大小关系可以直接用差分数组的正负性体现，于是每次修改只需两次单点修改和一次全局查询就好了。

复杂度 O(\xi^3n\log n)，其中 \xi 为矩阵边长，本做法中 \xi=4。

代码

这个做法虽然在码长和效率上不占优势，但是它好写啊，线段树是标准线段树，以及矩阵都只需要复制下来改一改就可以了。

#include<bits/stdc++.h>
#define cint const int
#define iint inline int
#define uint unsigned int
#define iuint inline unsigned int
#define cuint const unsigned int
#define ll long long
#define cll const long long
#define ill inline long long
#define ull unsigned long long
#define iull inline unsigned long long
#define cull const unsigned long long
#define sh short
#define csh const short
#define ish inline short
#define ush unsigned short
#define iush inline unsigned short
#define cush const unsigned short
using namespace std;
iint read()
{
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch-'0');
        ch=getchar();
    }
    return x;
}
cint inf=1e9;
struct matrix{
    short n,m;
    int a[4][4];
}f,emp,A,B,C;
matrix operator*(const matrix x,const matrix y)
{
    matrix z;
    z.n=x.n;
    z.m=y.m;
    for(short i=0;i<x.n;++i)
    {
        for(short j=0;j<y.m;++j)
        {
            z.a[i][j]=-inf;
            for(short k=0;k<x.m;++k)
            {
                z.a[i][j]=max(z.a[i][j],x.a[i][k]+y.a[k][j]);
            }
        }
    }
    return z;
}
inline void init()
{
    emp.n=emp.m=4;
    for(short i=0;i<4;++i)
    {
        for(short j=0;j<4;++j)
        {
            emp.a[i][j]=(i==j?0:-inf);
        }
    }
    f.n=1;
    f.m=4;
    f.a[0][0]=f.a[0][1]=f.a[0][2]=f.a[0][3]=0;
    B.n=B.m=4;
    for(short i=0;i<4;++i)
    {
        for(short j=0;j<4;++j)
        {
            B.a[i][j]=(i==2?(j==2?0:1):-inf);
        }
    }
    B.a[3][3]=0;
    A=C=B;
    A.a[0][0]=A.a[0][3]=1;
    C.a[0][1]=C.a[1][1]=C.a[0][3]=C.a[1][3]=1;
}
int n,q;
ll a[300001];
namespace T{
    struct node{
        int l,r;
        matrix prod;
    }t[1200001];
    void Build(cint p,cint l,cint r)
    {
        t[p].l=l;
        t[p].r=r;
        if(l==r)
        {
            if(a[l]>0)t[p].prod=A;
            else if(a[l]==0)t[p].prod=B;
            else t[p].prod=C;
            return;
        }
        cint mid=l+r>>1;
        Build(p<<1,l,mid);
        Build(p<<1|1,mid+1,r);
        t[p].prod=t[p<<1].prod*t[p<<1|1].prod;
    }
    void build()
    {
        Build(1,1,n);
    }
    void Update(cint p,cint x)
    {
        if(t[p].l>x||t[p].r<x)return;
        if(t[p].l==x&&t[p].r==x)
        {
            if(a[x]>0)t[p].prod=A;
            else if(a[x]==0)t[p].prod=B;
            else t[p].prod=C;
            return;
        }
        Update(p<<1,x);
        Update(p<<1|1,x);
        t[p].prod=t[p<<1].prod*t[p<<1|1].prod;
    }
    void update(cint x)
    {
        Update(1,x);
    }
    iint ask()
    {
        return (f*t[1].prod).a[0][3];
    }
}
void solve()
{
    cint l=read();
    cint r=read();
    cint d=read();
    a[l]+=d;
    T::update(l);
    if(r!=n)
    {
        a[r+1]-=d;
        T::update(r+1);
    }
    printf("%d\n",T::ask());
}
int main()
{
    init();
    n=read();
    for(int i=1;i<=n;++i)
    {
        a[i]=read();
    }
    for(int i=n;i>=1;--i)
    {
        a[i]-=a[i-1];
    }
    T::build();
    q=read();
    while(q--)solve();
    return 0;
}