题解：P14379 【MX-S9-T2】「LAOI-16」摩天大楼

liuchang09 · 2025-11-08 22:00:16 · 题解

计算 f 的过程

正着计算有多少种方法可以使 f(i,j)=1 不太好解决，因此我们可以计算有多少个 f(i,j)=0 ，再拿总的减去这个值就行了。下面我们来想什么时候 f(i,j)=0 。

对于一对 i,j ，我们进行分类讨论。

• 若 [i,j] 中没有 1 ，那么就可以最低高度就永远等于 1 ，f(i,j)=0 。

• 若 [i,j] 中有 1 ，设 [i,j] 中 x 为最后一个满足 a[x]=1 的点。

  • 若 a[r] \ne 1 ，那么令 k=x+1 ，则 k 右半部分的最低高度为 1 ，而左半段不为 1 ，f(i,j)=1 。对称过来也可以得到 a[l] \ne 1 时同样有 f(i,j)=1 。
  • 若 a[i]=1 且 a[j]=1 ，类比探究 1 对 f(i,j) 的影响可以得到 2 对 f(i,j) 的影响，即当 [i,j] 中存在 2 时，只有当 a[i]=2 且 a[j]=2 时 f(i,j)=0 ，但因为这种情况前提条件为 a[i]=1 且 a[j]=1 ，所以在这种情况下当 [i,j] 中存在 2 时就一定有 f(i,j)=1 。

处理维护操作

我们通过上述方法可以将问题转化成总方案减去 f(i,j)=0 的方案，而 f(i,j)=0 的方案即为连续的不含 1 的序列的贡献加上连续的不含 2 的序列中 1 的贡献。其中若长度为 L ，由组合得贡献为 \frac{1}{2} \times L \times (L-1) 。

因此，我们仅需处理上述序列长度的贡献即可。用线段树存储。两个子节点合并时，只有两个节点都存在多端合法序列即存在边界时才累加到总的计数器上。

为了求出上一次修改到下一次修改总计数器的改变量，对于每一个节点的贡献，设为其两个子节点合并时产生的贡献即可，这样就不会因某一段序列的改变而对其相邻序列的贡献产生影响。修改总计数器时减去这个节点上一次修改时的贡献在加上这一次修改时的贡献即可。

#include <bits/stdc++.h>
#define int long long//不开long long过不了
using namespace std;
const int maxn=1e6+1e1;
struct Node{
    int lsum,rsum;
    bool duan;
};
Node a[maxn*4][3];//两个线段树存储两种不同情况
int now[maxn];
int gong[maxn*4][3];
int n,T;
int sum,zong;
int lc(int x){return 2*x;};
int rc(int x){return 2*x+1;};
int suan(int x){return (x*(x-1))/2;};
int pushup(int x,int flag){//合并操作
    int res=0;
    if(a[lc(x)][flag].duan==1&&a[rc(x)][flag].duan==1){
        res=suan(a[lc(x)][flag].rsum+a[rc(x)][flag].lsum);
        a[x][flag].lsum=a[lc(x)][flag].lsum;
        a[x][flag].rsum=a[rc(x)][flag].rsum;
    }
    if(a[lc(x)][flag].duan==1||a[rc(x)][flag].duan==1){
        a[x][flag].duan=1;
        if(a[lc(x)][flag].duan==1&&a[rc(x)][flag].duan==0){
            a[x][flag].lsum=a[lc(x)][flag].lsum;
            a[x][flag].rsum=a[lc(x)][flag].rsum+a[rc(x)][flag].lsum;
        }
        if(a[lc(x)][flag].duan==0&&a[rc(x)][flag].duan==1){
            a[x][flag].rsum=a[rc(x)][flag].rsum;
            a[x][flag].lsum=a[rc(x)][flag].lsum+a[lc(x)][flag].rsum;
        }
    }
    else{
        a[x][flag].duan=0;
        a[x][flag].lsum=a[lc(x)][flag].lsum+a[rc(x)][flag].lsum;
        a[x][flag].rsum=a[lc(x)][flag].lsum+a[rc(x)][flag].rsum;
    }
    return res;
}
void build(int rt,int l,int r,int flag){
    if(l==r){
        if(flag==0){
            if(now[l]==1||now[l]==-1){
                a[rt][flag].lsum=a[rt][flag].rsum=0;
                a[rt][flag].duan=1;
            }
            else{
                a[rt][flag].rsum=a[rt][flag].lsum=1;
                a[rt][flag].duan=0;
            }
        }
        else{
            if(now[l]==2||now[l]==-1){
                a[rt][flag].lsum=a[rt][flag].rsum=0;
                a[rt][flag].duan=1;
            }
            else if(now[l]==1){
                a[rt][flag].lsum=a[rt][flag].rsum=1;
                a[rt][flag].duan=0;
            }
            else{
                a[rt][flag].lsum=a[rt][flag].rsum=0;
                a[rt][flag].duan=0;             
            }
        }
        return ;
    }
    int mid=(l+r)/2;
    build(lc(rt),l,mid,flag);
    build(rc(rt),mid+1,r,flag);
    gong[rt][flag]=pushup(rt,flag);
    sum=sum+gong[rt][flag];
    return ;
}
void gai(int rt,int l,int r,int p,int q,int flag){
    if(l==r){
        if(flag==0){
            if(q==1){
                a[rt][flag].lsum=a[rt][flag].rsum=0;
                a[rt][flag].duan=1;
            }
            else{
                a[rt][flag].rsum=a[rt][flag].lsum=1;
                a[rt][flag].duan=0;
            }
        }
        else{
            if(q==2){
                a[rt][flag].lsum=a[rt][flag].rsum=0;
                a[rt][flag].duan=1;
            }
            else if(q==1){
                a[rt][flag].lsum=a[rt][flag].rsum=1;
                a[rt][flag].duan=0;
            }
            else{
                a[rt][flag].lsum=a[rt][flag].rsum=0;
                a[rt][flag].duan=0;
            }
        }
        return ;
    }
    int mid=(l+r)/2;
    if(p<=mid) gai(lc(rt),l,mid,p,q,flag);
    if(p>=mid+1) gai(rc(rt),mid+1,r,p,q,flag);
    int res=pushup(rt,flag);
    sum=sum-gong[rt][flag]+res;
    gong[rt][flag]=res;
    return ;
}
signed main() {
//  freopen("1.in","r",stdin);
    scanf("%lld%lld",&n,&T);
    zong=suan(n);
    for(int i=1;i<=n;i++) scanf("%lld",&now[i]);
    now[0]=-1;now[n+1]=-1;
    build(1,0,1+n,0);//连续不包含1的长度
    build(1,0,1+n,1);//不含2的长度 
    while(T--){
        int x,y;
        scanf("%lld%lld",&x,&y);
        gai(1,0,1+n,x,y,1);
        gai(1,0,1+n,x,y,0);
        now[x]=y;
        printf("%lld\n",zong-sum);
    }
    return 0;
}