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

Purslane · 2025-05-09 21:50:27 · 题解

Solution

简单数据结构题。考虑上一些小套路。

将第一问的和式改为：

考虑稍微转化一下，设 a 的上界为 V，改为：

这个怎么看呢，考虑记 b_i = [a_i \ge t]，b 中相邻两个 1 的距离分别为 len_{1,2,\cdots,z}（特别的认为 b_0=b_{n+1}=1），那么 t 固定的时候和式就是 \sum_{i=1}^z \max\{0,len_i - k + 1\}。你把 len 扔进一个树状数组中，就可以快速求解。

由于只有 a_k \leftarrow a_k+1 的操作，所以每次只会有 O(1) 个 len 发生改变，直接暴力修改。

有一个小问题，你怎么处理初始的 len。有用的观察：存在 t 使得 b_i = b_j = 1，b_{i+1} = b_{i+2} = \cdots = b_{j-1} = 0 的 (i,j) 只有 O(n) 对。具体怎么做可以参考 JOISC 的铁道旅行（其实就是一个简单的单调栈）。

复杂度 O(n \log n)，足以通过本题。

非常罕见的不是特别慢。

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=5e5+10;
int n,q,a[MAXN],t[MAXN<<2],V=2e9;
int tr[MAXN][2];
void Update(int pos,int v1,int v2) {
    pos=n-pos+1;
    while(pos<=n) tr[pos][0]+=v1,tr[pos][1]+=v2,pos+=pos&-pos;
    return ;
}
pair<int,int> Query(int pos) {
    int ans1=0,ans2=0;
    pos=n-pos+1;
    while(pos) ans1+=tr[pos][0],ans2+=tr[pos][1],pos-=pos&-pos;
    return {ans1,ans2}; 
}
#define lson (k<<1)
#define rson (k<<1|1)
#define mid (l+r>>1)
void build(int k,int l,int r) {
    if(l==r) return t[k]=a[l],void();
    build(lson,l,mid),build(rson,mid+1,r);
    return t[k]=max(t[lson],t[rson]),void();    
}
int query(int k,int l,int r,int x,int y) {
    if(x<=l&&r<=y) return t[k];
    if(y<=mid) return query(lson,l,mid,x,y);
    if(x>mid) return query(rson,mid+1,r,x,y);
    return max(query(lson,l,mid,x,y),query(rson,mid+1,r,x,y));  
}
void modify(int k,int l,int r,int pos,int v) {
    if(l==r) return t[k]=v,void();
    if(pos<=mid) modify(lson,l,mid,pos,v);
    else modify(rson,mid+1,r,pos,v);
    return t[k]=max(t[lson],t[rson]),void();    
}
int bfind1(int k,int l,int r,int pos,int v) {
    if(r<pos||t[k]<v) return -1;
    if(l==r) return l;
    int tans=bfind1(lson,l,mid,pos,v);
    if(tans!=-1) return tans;
    return bfind1(rson,mid+1,r,pos,v);  
}
int bfind2(int k,int l,int r,int pos,int v) {
    if(l>pos||t[k]<v) return -1;
    if(l==r) return l;
    int tans=bfind2(rson,mid+1,r,pos,v);
    if(tans!=-1) return tans;
    return bfind2(lson,l,mid,pos,v);
}
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    ffor(i,1,n) cin>>a[i];
    a[0]=a[n+1]=V,build(1,0,n+1);
    stack<int> st; st.push(0);
    ffor(i,1,n+1) {
        while(!st.empty()&&a[i]>=a[st.top()]) {
            int l=st.top()+1,r=i-1;
            st.pop();
            if(l<=r) Update(r-l+1,min(a[l-1],a[r+1])-query(1,0,n+1,l,r),(r-l+1)*(min(a[l-1],a[r+1])-query(1,0,n+1,l,r)));
        }
        if(!st.empty()) {
            int l=st.top()+1,r=i-1; 
            if(l<=r) Update(r-l+1,min(a[l-1],a[r+1])-query(1,0,n+1,l,r),(r-l+1)*(min(a[l-1],a[r+1])-query(1,0,n+1,l,r)));
        }
        st.push(i);
    }
    ffor(i,1,q) {
        char op;
        int k;
        cin>>op>>k;
        if(op=='?') {
            auto pr=Query(k);
            cout<<V*(n-k+1)-(pr.second-(k-1)*pr.first)<<'\n';
        }
        else {
            int L=bfind2(1,0,n+1,k,a[k]+1)+1,R=bfind1(1,0,n+1,k,a[k]+1)-1;
            Update(R-L+1,-1,-(R-L+1));
            if(L<=k-1) Update(k-L,1,k-L);
            if(k+1<=R) Update(R-k,1,R-k);
            a[k]++,modify(1,0,n+1,k,a[k]);
        }
    }
    return 0;
}