题解：P16543 [EGOI 2026] 给花浇水 / Watering Plants

· · 题解

考虑维护两个数组 lst_r 和 cnt_r，分别表示 r 这个点从哪个时刻开始连续接受别人浇水，以及在 lst_r 之前累计被浇水多少次。

对于时刻 i 的修改操作，显然只有 r - 1 和 r 的 lst 与 cnt 会改变，其他点不受影响。不妨分讨两边的变化情况：如果原来被浇水但现在不浇了，则可以令 cnt_r \leftarrow cnt_r + (i - lst_r + 1)，表示把这段时间的浇水量累计存下，然后再令 lst_r = d + 1 表示从来没有被连续浇过水即可；如果原来没被浇水但现在被浇，则直接令 lst_r = i + 1 表示第二天起开始接受浇水即可。

对于查询，可以分成 lst_r 之前和之后两部分。前者的贡献显然是 cnt_r，后者的贡献显然是 i - lst_r + 1，加起来即可。

注意我们使用 lst_r = d + 1 表示 r 暂时没有被楼上的人浇水，因此使用 i - lst_r + 1 时应当将其对 0 取 \max。

:::info[参考代码]

#include<bits/stdc++.h>
// #define int long long
#define fo(i, l, r) for(decltype((l) + (r)) i = (l); i <= (r); ++i)
#define fd(i, l, r) for(decltype((l) + (r)) i = (l); i >= (r); --i)
#define fu(i, l, r) for(decltype((l) + (r)) i = (l); i <  (r); ++i)
#define y1 zhang_kevin
#define pii pair<int, int>
#define fi first
#define se second
#define vec vector
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define ll long long
#define ull unsigned long long
#define flush() (fwrite(obuf, 1, p3 - obuf, stdout), p3 = obuf)
using namespace std;
bool ST;
char ibuf[1 << 20], *p1 = ibuf, *p2 = ibuf, obuf[1 << 20], *p3 = obuf;
inline char gc(){
    if(p1 == p2){
        p1 = ibuf, p2 = ibuf + fread(ibuf, 1, 1 << 20, stdin);
        if(p1 == p2) return EOF;
        return *p1++;
    }
    return *p1++;
}
inline char pc(char ch){
    if(p3 == obuf + (1 << 20)) flush();
    *p3 = ch;
    return *p3++;
}
template<typename type>
inline int rd(type &x){
    x = 0; bool f = 0; char ch = gc();
    while(!isdigit(ch)) f |= ch == '-', ch = gc();
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
    return f ? x = -x : 0;
}
template<typename type, typename ...T>
inline void rd(type &x, T &...y){rd(x), rd(y...);}
inline void gs(string &s){
    s.clear(); char c = gc();
    while(c == ' ' || c == '\n' || c == '\t' || c == '\r') c = gc();
    while(c != ' ' && c != '\n' && c != '\t' && c != '\r' && c != EOF) s += c, c = gc();
    return;
}
class Flush{public: ~Flush(){flush();}}___;
template<typename type>
inline void wr(type x){
    if(x < 0) pc('-'), x = -x;
    if(x > 9) wr(x / 10);
    pc(x % 10 + '0');
    return;
}
inline void wrs(const string& s){for(auto ch : s) pc(ch);}
namespace Solution{
    int n, d, a[200005], lst[200005], cnt[200005];
    inline void Solve(){
        rd(n, d); fo(i, 1, n) rd(a[i]), lst[i - 1] = a[i] < a[i - 1] ? 1 : d + 1;
        fo(i, 1, d){
            char ch = gc(); while(ch != '!' && ch != '?') ch = gc();
            if(ch == '!'){
                int r, x; rd(r, x), r++;
                if(r > 1 && a[r - 1] > x){
                    if(a[r - 1] <= a[r]){
                        lst[r - 1] = i + 1;
                    }
                }else if(r > 1 && a[r - 1] <= x){
                    if(a[r - 1] > a[r]){
                        cnt[r - 1] += max(i - lst[r - 1] + 1, 0);
                        lst[r - 1] = d + 1;
                    }
                }
                if(r < n && a[r + 1] < x){
                    if(a[r + 1] >= a[r]){
                        lst[r] = i + 1;
                    }
                }else if(r < n && a[r + 1] >= x){
                    if(a[r + 1] < a[r]){
                        cnt[r] += max(i - lst[r] + 1, 0);
                        lst[r] = d + 1;
                    }
                }
                a[r] = x;
            }else{
                int r; rd(r);
                wr(max(i - lst[r] + 1, 0) + cnt[r]), pc('\n');
            }
            // cerr << cnt[1] << '\n';
        }
        return;
    }
}
bool ED;
signed main(){
    clock_t START = clock();
    // freopen("input.in", "r", stdin), freopen("output.out", "w", stdout);
    Solution::Solve();
    cerr << (double)(clock() - START) / CLOCKS_PER_SEC << " s" << '\n';
    cerr << 1.0 * abs(&ED - &ST) / 1024 / 1024 << " MB" << '\n';
    return 0;
}

:::