题解：P8010 「Wdsr-3」令人感伤的红雨

· · 题解

P8010 「Wdsr-3」令人感伤的红雨

提供一个 O(n\log{n}) 的卡常做法。

思路

我们先来看这令人头大的三堆函数。

首先我们可以发现 A(l,r) 指的是 l\sim r 中最靠右的最大值出现的位置。
令 S_i = A(1,i)，那么序列 S_n 一定单调不降。

所以有：

\begin{aligned} &\min\limits_{j=1}^i\{A(j,i)\} = A(1,i)\\ &\max\limits_{j=1}^i\{A(j,i)\} = A(i,i)=i \end{aligned}

那么我们可以对 B(l,r) 中关于 A(j,i) 的两个式子做进一步转化：

\begin{aligned} &\max\limits_{i=l}^r\{\min\limits_{j=1}^i\{A(j,i)\}\} = \max\limits_{i=l}^r\{A(1,i)\} = A(1,r)\\ &\min_{i=l}^r\{\max_{j=1}^i\{A(j,i)\}\} = \min\limits_{i=l}^r\{i\} = l \end{aligned}

于是我们得到了 B(l,r) 关于 A(l,r) 的转化：

\begin{aligned} &B(l,r) = A(1,r)-l\\ \end{aligned}

那么我们能得到 \Omega(l,r) 关于 A(i,j) 的转化：

\begin{aligned} &\Omega(l,r) = \min\limits_{i=l}^{r}\{\min\limits_{j=i}^r\{\mid A(1,j)-i\mid \}\} \end{aligned}

我们发现，在 \min\limits_{j=i}^r\{\mid A(1,j)-i\mid\} 中，由于 A(1,j)-i 单调不增且不大于零，所以我们可以得到：

\begin{aligned} &\Omega(l,r) = \mid A(1,r)-l\mid = l-A(1,r) \end{aligned}

其实就是要维护 l\sim r 中 A(1,r) 到 l 的距离。如果此时 l<A(1,r)，则不存在答案，应输出 0。

维护区间最大值的位置，我们考虑用线段树。在左右区间合并时做分类讨论即可。

即使线段树的 \log 大，但是理论来讲 2.5 秒是可以跑 2\times 10^8 的，所以我们卡卡常。

比如我们标记永久化，使用非递归线段树，把要调用的非递归函数都放到主函数里。

具体内容见代码。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T>
inline void read(T&x){
    int w=0;x=0;
    char ch = getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') w=1;
        ch = getchar();
    }
    while(ch>='0' && ch<='9'){
        x = (x<<1)+(x<<3)+(ch^48);
        ch = getchar();
    }
    if(w) x=-x;
}
template <typename T,typename...Args>
inline void read(T&t,Args&...args){
    read(t);read(args...);
}
template <typename T>
inline T Max(T x,T y){return (x > y ? x : y);}
const int N = 6e6+10;
int n,m;
int P=1,DEP=0;
struct Tree{
    ll mx; int pos;
    Tree(){
        mx = 0; pos = 0;
    }
    Tree(ll tmx,int tpos){
        mx = tmx; pos = tpos;
    }
    inline Tree operator + (const Tree&G) const{
        if(mx==G.mx) return Tree(mx,Max(pos,G.pos));
        else if(mx>G.mx) return Tree(mx,pos);
        else return G;
    }
}tr[N*3];
ll tag[N*3];
int main(){
//  freopen("in.in","r",stdin);
//  freopen("out.out","w",stdout);

    read(n,m);
    while(P<=n+1) P<<=1;
    for(int i=1,x;i<=n;++i){
        read(x); tr[i+P] = Tree(1ll*x,i);//直接读入省掉建树的常数
    }
    for(int i=P-1;i;--i) tr[i] = tr[i<<1]+tr[i<<1|1];//用重载运算符
    for(int i=1,opt,x,y;i<=m;++i){
        read(opt,x,y);
        if(opt==1){//把update内容搬到主函数里
            int l = 1+P-1,r = x+P+1; ll k = 1ll*y;
            while(l^1^r){
                if(~l&1) tr[l^1].mx+=k,tag[l^1]+=k;
                if(r&1) tr[r^1].mx+=k,tag[r^1]+=k;
                l>>=1;r>>=1;
                tr[l] = tr[l<<1]+tr[l<<1|1];
                tr[l].mx += tag[l];//标记永久化要加累加标记值
                tr[r] = tr[r<<1]+tr[r<<1|1];
                tr[r].mx += tag[r];
            }
            for(l>>=1; l ;l>>=1){//更新上传
                tr[l] = tr[l<<1]+tr[l<<1|1];
                tr[l].mx += tag[l];
            }
        }
        else{//把query内容搬到主函数里
            int l = 1+P-1,r = y+P+1; Tree resl,resr;
            while(l^1^r){
                if(~l&1) resl = resl+tr[l^1];//注意左右区间合并顺序
                if(r&1) resr = tr[r^1]+resr;
                l>>=1;r>>=1;
                resl.mx += tag[l];//累加标记值
                resr.mx += tag[r];
            }
            printf("%d\n",Max(0,x-(resl+resr).pos));//没有答案输出0
        }
    }

    // fclose(stdin);
    // fclose(stdout);
    return 0;
}