CF1567E 题解

· · 个人记录

题面简述

一个数列 a ，支持单点修改，区间查询不下降子串数，子串要求连续。

Hint

  1. 区间问题考虑线段树求解
  2. 能否不加修改操作？能否考虑全局查询情况？
  3. 考虑区间最大子段和做法。

如果看到这里有思路，就先关掉题解写写看吧！

题解

这题的题解区怎么都是一种解法啊……

这道题一看就是个动态 DP 题吧……

先考虑没有修改且全局查询的情况，我们可以用简单的 DP 来解决这个问题，令 dp_i 表示以 i 结尾的不下降子串数列，则分类讨论，转移方程如下：

dp_i= \begin{cases} dp_{i-1}+1\quad &a_i\geq a_{i-1} \\ 1\quad &a_i\lt a_{i-1} \end{cases}

最后的结果即所有 dp_i 的和。

考虑怎么加上区间查询，注意到这个转移方程可以写成矩阵乘法的形式，于是我们继续分类讨论：

  1. $$ \begin{bmatrix}dp_i & 1 & sm_i\end{bmatrix} \times \begin{bmatrix}1 & 0 & 1\\ 1 & 1 & 1\\ 0 & 0 & 1\end{bmatrix} = \begin{bmatrix}dp_{i+1} & 1 & sm_{i+1}\end{bmatrix} $$
  2. $$ \begin{bmatrix}dp_i & 1 & sm_i\end{bmatrix} \times \begin{bmatrix}0 & 0 & 0\\ 1 & 1 & 1\\ 0 & 0 & 1\end{bmatrix} = \begin{bmatrix}dp_{i+1} & 1 & sm_{i+1}\end{bmatrix} $$

最终得到的 sm_n 即答案。

容易发现，矩阵乘法满足结合律，所以我们可以用线段树来维护一个区间的矩阵乘积，这样带上修改也很容易了。

AC Code

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define inf (ll)(1e18)
using namespace std;

ll n,q,b[200005];

struct mat{
    ll mat[4][4],n,m;
}a[200005],base;

mat tree[800005];

mat mul(mat a,mat b){
    mat ans;
    memset(ans.mat,0,sizeof(ans.mat));

    ans.n=a.n,ans.m=b.m;
    for (ll i=1;i<=a.n;i++){
        for (ll j=1;j<=b.m;j++){
            for (ll k=1;k<=b.n;k++){
                ans.mat[i][j]+=a.mat[i][k]*b.mat[k][j];
            }
        }
    }
    return ans;
}

void build(ll root,ll l,ll r){
    if (l==r){
        tree[root]=a[l];
        return;
    }
    ll mid=(l+r)/2;
    build(root*2,l,mid);
    build(root*2+1,mid+1,r);
    tree[root]=mul(tree[root*2],tree[root*2+1]);
}

void update(ll root,ll l,ll r,ll pos,ll tp){
    if (l==pos&&pos==r){
        memset(tree[root].mat,0,sizeof tree[root].mat);
        if (tp){
            tree[root].n=tree[root].m=3;
            tree[root].mat[1][1]=tree[root].mat[1][3]=tree[root].mat[2][1]=tree[root].mat[2][2]=tree[root].mat[2][3]=tree[root].mat[3][3]=1;
        }else{
            tree[root].n=tree[root].m=3;
            tree[root].mat[2][1]=tree[root].mat[2][2]=tree[root].mat[2][3]=tree[root].mat[3][3]=1;
        }
        return;
    }
    ll mid=(l+r)/2;
    if (pos<=mid)update(root*2,l,mid,pos,tp);
    else update(root*2+1,mid+1,r,pos,tp);
    tree[root]=mul(tree[root*2],tree[root*2+1]);
}

mat query(ll root,ll l,ll r,ll L,ll R){
    if (L<=l&&r<=R){
        return tree[root];
    }
    ll mid=(l+r)/2;
    mat ans;
    ans.n=ans.m=3;
    memset(ans.mat,0,sizeof ans.mat);
    ans.mat[1][1]=ans.mat[2][2]=ans.mat[3][3]=1;
    if (L<=mid)ans=mul(ans,query(root*2,l,mid,L,R));
    if (R>mid)ans=mul(ans,query(root*2+1,mid+1,r,L,R));
    return ans;
}

int main(){
    ll n,q;
    scanf("%lld%lld",&n,&q);
    for (ll i=1;i<=n;i++){
        scanf("%lld",b+i);
        if (b[i]>=b[i-1]){
            a[i].n=a[i].m=3;
            a[i].mat[1][1]=a[i].mat[1][3]=a[i].mat[2][1]=a[i].mat[2][2]=a[i].mat[2][3]=a[i].mat[3][3]=1;
        }else{
            a[i].n=a[i].m=3;
            a[i].mat[2][1]=a[i].mat[2][2]=a[i].mat[2][3]=a[i].mat[3][3]=1;
        }
    }
    b[n+1]=1e18;
    build(1,1,n);
    for (ll i=1;i<=q;i++){
        ll op,l,r;
        scanf("%lld%lld%lld",&op,&l,&r);
        if (op==1){
            b[l]=r;
            if (r>=b[l-1]){
                update(1,1,n,l,1);
            }

            else{
                update(1,1,n,l,0);
            }

            if (l+1>n)continue;
            if (b[l+1]>=r){
                update(1,1,n,l+1,1);
            }

            else{
                update(1,1,n,l+1,0);
            }
        }else{
            base.n=1,base.m=3;
            base.mat[1][1]=base.mat[1][2]=base.mat[1][3]=1;
            base=mul(base,query(1,1,n,l+1,r));
            printf("%lld\n",base.mat[1][3]);
        }
    }
    return 0;
}

注意事项

  1. 由于线段树和矩阵乘法的常数都很大，所以需要注意常数优化。
  2. 矩阵不清空，爆零两行泪。