题解：P12448

Danslapiscine · 2025-11-16 13:48:23 · 题解

首先可以想到一个静态的做法。按照原式计算是困难的，不妨变换顺序，计算每个点对答案的贡献，需要处理出 L[i], R[i] 表示 i 点最大值能延申到的区间。推一下式子，贡献可表示为 3 段加等差数列的形式，可用线段树简单维护（注意标记的首项下传细节！）。

观察修改的样子，发现修改前后只是在某些区间的答案上简单加 1，故考虑求这些区间的个数。容易发现这只跟左边、右边第一个大于等于 a[x] 的位置有关，与静态相似地做。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int rd(){
    char c = getchar();
    while(c < '0' || c > '9') c = getchar();
    int ret = 0;
    while('0' <= c && c <= '9') ret = (ret << 3) + (ret << 1) + c - '0', c = getchar();
    return ret;
}

int n, m, ID;
long long a[500002];

struct Segment_Tree{
    #define l(pos) pos << 1
    #define r(pos) (pos << 1) | 1
    struct Node {
        int num;
        int tagl, tags;
        bool havetag;
    }t[4000002];
    void pushdown(int pos,int l,int r){
        int mid = (l + r) >> 1;
        if(t[pos].havetag){
            t[pos].num += (2*t[pos].tagl + (r-l)*t[pos].tags) * (r-l+1) / 2;
            t[l(pos)].havetag = 1, t[l(pos)].tagl += t[pos].tagl, t[l(pos)].tags += t[pos].tags;
            t[r(pos)].havetag = 1, t[r(pos)].tagl += t[pos].tagl + (mid+1-l)*t[pos].tags, t[r(pos)].tags += t[pos].tags;
            t[pos].tagl = 0, t[pos].tags = 0, t[pos].havetag = 0;
        }
    }
    void Add(int pos,int l,int r,int tarl,int tarr,int x,int y){
        if(tarl > tarr) return;
        pushdown(pos, l, r);
        if(tarl <= l && r <= tarr){
            t[pos].havetag = 1;
            t[pos].tagl = x, t[pos].tags = y;
            pushdown(pos, l, r);
            return;
        }
        int mid = (l + r) >> 1;
        if(tarl <= mid) Add(l(pos), l, mid, tarl, tarr, x, y);
        if(mid+1 <= tarr) {
            if(tarl <= mid+1) Add(r(pos), mid+1, r, mid+1, tarr, x+(mid+1-tarl)*y, y);
            else Add(r(pos), mid+1, r, tarl, tarr, x, y);
        }
        pushdown(l(pos), l, mid), pushdown(r(pos), mid+1, r);
        t[pos].num = t[l(pos)].num + t[r(pos)].num;
    }
    int Query(int pos,int l,int r,int tarl,int tarr){
        pushdown(pos, l, r);
        if(tarl <= l && r <= tarr) return t[pos].num;
        int mid = (l + r) >> 1, ret = 0;
        if(tarl <= mid) ret += Query(l(pos), l, mid, tarl, tarr);
        if(mid+1 <= tarr) ret += Query(r(pos), mid+1, r, tarl, tarr);
        return ret;
    }
};
Segment_Tree T;
struct Line_Tree{
    #define l(pos) pos << 1
    #define r(pos) (pos << 1) | 1
    int Max[4000002];
    void Add(int pos,int l,int r,int tar,int s){
        if(l == r) {
            Max[pos] += s;
            return;
        }
        int mid = (l + r) >> 1;
        if(tar <= mid) Add(l(pos), l, mid, tar, s);
        else Add(r(pos), mid+1, r, tar, s);
        Max[pos] = max(Max[l(pos)], Max[r(pos)]);
    }
    int Finderl(int pos,int l,int r,int tar,int tars){
        if(l == r){
            if(Max[pos] < tars) return -1;
            return l;
        }
        int mid = (l + r) >> 1;
        if(tar <= mid) return Finderl(l(pos), l, mid, tar, tars);
        if(mid < tar && tar < r){
            int R = Finderl(r(pos), mid+1, r, tar, tars);
            if(R != -1) return R;
            return Finderl(l(pos), l, mid, tar, tars);
        }
        if(Max[r(pos)] >= tars) return Finderl(r(pos), mid+1, r, tar, tars);
        return Finderl(l(pos), l, mid, tar, tars);
    }
    int Finderr(int pos,int l,int r,int tar,int tars){
        if(l == r){
            if(Max[pos] < tars) return -1;
            return l;
        }
        int mid = (l + r) >> 1;
        if(tar >= mid+1) return Finderr(r(pos), mid+1, r, tar, tars);
        if(l < tar && tar < mid+1){
            int R = Finderr(l(pos), l, mid, tar, tars);
            if(R != -1) return R;
            return Finderr(r(pos), mid+1, r, tar, tars);
        }
        if(Max[l(pos)] >= tars) return Finderr(l(pos), l, mid, tar, tars);
        return Finderr(r(pos), mid+1, r, tar, tars);
    }
};
Line_Tree L;

signed main(){
    //freopen("data.in","r",stdin);
    //freopen("my.out","w",stdout);

    n = rd(), m = rd(), ID = rd();
    L.Add(1, -1, n+2, 0, 1e18);
    L.Add(1, -1, n+2, n+1, 1e18);
    L.Add(1, -1, n+2, -1, 1e18);
    L.Add(1, -1, n+2, n+2, 1e18);
    for(int i=1;i<=n;i++) {
        a[i] = rd();
        L.Add(1, -1, n+2, i, a[i]);
    }

    for(int i=1;i<=n;i++){
        int l = L.Finderl(1, -1, n+2, i-1, a[i]+1) + 1, r = L.Finderr(1, -1, n+2, i+1, a[i]) - 1;

        int s = min(r - i + 1, i - l + 1);
        T.Add(1, 1, n, 1, s-1, a[i], a[i]);
        T.Add(1, 1, n, s, r-l+1-s, s*a[i], 0);
        T.Add(1, 1, n, r-l+2-s, r-l+1, s*a[i], -a[i]);
    }

    for(int i=1;i<=m;i++){
        int opt;
        int x;
        opt = rd(), x = rd();
        if(opt == 1){
            printf("%lld\n",T.Query(1, 1, n, x, x));
        }
        else {
            a[x]++;
            int l = L.Finderl(1, -1, n+2, x-1, a[x]) + 1, r = L.Finderr(1, -1, n+2, x+1, a[x]) - 1;
            //cout << l << ' ' << r << endl;

            int MIN = min(x-l+1, r-x+1), MAX = max(x-l+1, r-x+1);
            T.Add(1, 1, n, 1, MIN-1, 1, 1);
            T.Add(1, 1, n, MIN, MAX - 1, MIN, 0);
            T.Add(1, 1, n, MAX, r-l+1, MIN, -1);

            L.Add(1, -1, n+2, x, 1);
        }
    }

    return 0;
}