题解：P12448 [COTS 2025] 观草 / Trava

· · 题解

题目：观草。

观观草草，草草观观，草观草观草。

观草观草，草观草观，观草观草观。

请注意，这并不是一首有名的诗歌。

Part 0

当求和本身不好计算的时候，我们应该考虑 a 能产生的贡献。

于是研究 a_i 对长度 k 的区间的贡献次数。

从 a_i 开始往两边拓展，若拓展到比它大的数，区间最大值就不是它了，此时终止拓展。右侧同理。

:::success[PICTURE] :::

对于区间 $(L_i,R_i)$，从 $a_i$ 开始**往左的可拓展距离** $^\clubsuit$ 为 $d_1$。从 $a_i$ 开始**往右的可拓展距离** $^\diamondsuit $ 为 $d_2$。 :::info $\clubsuit$：即 $L_i+1,L_i+2,\cdots,i$，共 $d_1=i-(L_i+1)+1=i-L_i$ 个数。 $\diamondsuit $：即 $i+1,i+2,\cdots,R_i-1$，共 $d_2=(R_i-1)-i+1=R_i-i$ 个数。 题外话：这里的初始 $L,R$ 我用单调栈算，是因为我的单调栈和线段树查询有点不一样，如果修改合适可以直接线段树二分求答案。 ::: ## Part 1 当区间长度 $k \in [1,d_1]$，此时区间起点可以从 $\operatorname{\max} (L_i+1,i-k+1)=i-k+1$ 一直到 $i$。 为什么到了 $A_i$ 不能再往右了？ 因为我们求的是 **$A_i$ 对长度 $k$ 的区间的贡献次数**。自然这个区间必须包含 $A_i$。 :::success[PICTURE] ![](https://cdn.luogu.com.cn/upload/image_hosting/uouzhot1.png) ::: $k\le d_1 \le d_2$，以 $A_i$ 开头往右走还有 $d_2$ 的距离，所以可以保证 $[A_i,A_{i+k-1}]$ 这一段不会碰到 $R_i$。 所以贡献次数等于可能区间起点数，也就是 $i-k+1 \rightarrow A_i$，共 $k$ 个数。 ## Part 2 当区间长度 $k \in (d_1,d_2)$。起点可以是 $L_i+1 \rightarrow i$ 的任意一个。 因为超过 $d_1$ 的覆盖长度保证了从这些起点开始一定盖的住 $A_i$。并且不会超出右侧 $d_2$ 的限制。 :::success[PICTURE] ![](https://cdn.luogu.com.cn/upload/image_hosting/uouzhot1.png) ::: 和上面一样的，到了 $A_i$ 不能再往右是因为这个区间必须包含 $A_i$。不然就不是 $A_i$ 做的贡献了。 此时总贡献次数为 $d_1$。 ## Part 3 $k \in [d_2,R_i-L_i]$。 个数取决于区间长度。我们终点从 $R_i-1$ 开始，往左延申起点。 :::success[PICTURES] ![](https://cdn.luogu.com.cn/upload/image_hosting/abydidtu.png) ![](https://cdn.luogu.com.cn/upload/image_hosting/vybaxm2k.png) ::: 不难发现 $k$ 与可行区间个数有关联。 - $k=d_2 \rightarrow num=d1$。 - $k=d_2+1 \rightarrow num=d1-1$。 - $\cdots

省流

CODE

:::success[code]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define For(i,L,R) for(int i=L;i<=R;i++)
#define lc u<<1
#define rc u<<1|1
const int N=5e5+10;
int n,m,a[N];
int stk[N],top;
int L[N],R[N];
int t[N<<2];
void pushup(int u){
    t[u]=max(t[lc],t[rc]);
}
void build(int u,int L,int R){
    if(L==R){
        t[u]=a[L];
        return;
    }
    int m=(L+R)>>1;
    build(lc,L,m);
    build(rc,m+1,R);
    pushup(u);
}
void upd(int u,int L,int R,int p,int v){
    if(L==R){t[u]+=v;return;}
    int m=(L+R)>>1;
    if(p<=m)upd(lc,L,m,p,v);
    else upd(rc,m+1,R,p,v);
    pushup(u);
}
int fl(int u,int L,int R,int l,int r,int v){
    if(t[u]<v||l>r)return -1;
    if(L==R)return L;
    int m=(L+R)>>1,res=-1;
    if(l<=m)res=fl(lc,L,m,l,r,v);
    if(res==-1&&r>m)res=fl(rc,m+1,R,l,r,v);
    return res;
}
int fr(int u,int L,int R,int l,int r,int v){
    if(t[u]<v||l>r)return -1;
    if(L==R)return L;
    int m=(L+R)>>1,res=-1;
    if(r>m)res=fr(rc,m+1,R,l,r,v);
    if(res==-1&&l<=m)res=fr(lc,L,m,l,r,v);
    return res;
}
ll k[N],d[N];
void add(int x,ll vk,ll vd){
    for(;x<=n;x+=x&-x){
        k[x]+=vk;
        d[x]+=vd;
    }
}
void work(int L,int R,ll vk,ll vd){
    if(L>R)return;
    add(L,vk,vd);
    add(R+1,-vk,-vd);
}
pair<ll,ll>qry(int x){
    ll sk=0,sd=0;
    for(;x;x-=x&-x){sk+=k[x];sd+=d[x];}
    return make_pair(sk,sd);
}
void upr(int u,int lp,int rp,ll x){
    int d1=u-lp,d2=rp-u,t=rp-lp-1;
    if(d1>d2)swap(d1,d2);
    work(1,d1,x,0);
    if(d1<d2)work(d1+1,d2,0,d1*x);
    if(d2<t)work(d2+1,t,-x,(t+1)*x);
}
ll solve(int u){
    pair<ll,ll>p=qry(u);
    return p.first*u+p.second;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    For(i,1,n){
        cin>>a[i];
        while(top&&a[stk[top]]<=a[i]){
            R[stk[top--]]=i;
        }
        L[i]=stk[top];
        stk[++top]=i;
    }
    while(top){
        R[stk[top--]]=n+1;
    }
    For(i,1,n){
        upr(i,L[i],R[i],a[i]);
    }
    build(1,1,n);
    while(m--){
        char op;int k;
        cin>>op>>k;
        if(op=='?')cout<<solve(k)<<"\n";
        else{
            a[k]++;
            upd(1,1,n,k,1);
            int l=fr(1,1,n,1,k-1,a[k]);
            if(l==-1)l=0;
            int r=fl(1,1,n,k+1,n,a[k]);
            if(r==-1)r=n+1;
            upr(k,l,r,1);
        }
    }
    return 0;
}

:::