瓜野高彦

takanashi_mifuru · 2024-10-11 13:36:18 · 题解

我从来没有想过这个专栏名字真的能和题目名字这么契合。。

开题不会做，数据范围根号能过，先想想分块。

首先这个东西转化一下就是时刻 k 的时候第 i 个点变成往前数 k+1 个数的最大值。

考虑分块之后变成了整块和散块，散块可以 ST 表直接查询，问题就是整块。

考虑如果我们能对第 i 个整块求出其在第 j 个时刻的和就可以了。

如果要维护每个点的变化这是不可能求出的，我们考虑只考虑这个块，如果块外面有一个神秘权值想要影响进来的话，他必须打过第一个点，这意味着每次从外面进来的权值必然是递增的，这启发我们暴力计算块内贡献再考虑块外贡献。

具体地，先用 ST 表暴力算出 j 在块长以下的时候的答案，然后考虑这个时候这个块里必然是一个单谷的，每次操作相当于是第一个点和前面的打架，赢的加入，然后谷前面的区间整体右移，再把谷丢掉。

这个东西是很好实现的，所以就做完了。

当然 256 兆肯定存不下，逐块处理就可以了。

时间复杂度 O(n\sqrt n)，空间复杂度 O(n\log n)。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<ctime>
#define ll long long
#define rep(i, f, t) for (int i = (f), ed##i = (t); i <= ed##i; ++i)
#define re(i, t) rep (i, 1, t)
#define per(i, t, f) for (int i = (t), ed##i = (f); i >= ed##i; --i)
#define ste(i, f, t, s) for (int i = (f), ed##i = (t); i <= ed##i; i += s)
#define each(i, x) for (auto& i : (x))
#define nxt(i, f, g) for (int i = g.h[f]; i; i = g.e[i].n)
#define dbg(x) (cerr << "(dbg) " << #x " = " << (x) << '\n')
#define umod(x) ((x) >= mo && ((x) -= mo))
#define dmod(x) ((x) < 0 && ((x) += mo))
#define up(x, y) (((x) < (y)) && ((x) = (y)))
#define down(x, y) (((x) > (y)) && ((x) = (y)))
#define y1 y1__
namespace FastIO {
    const int SZ=(1<<23)+1;
    struct I {
        char ibuf[SZ],*iS,*iT,c;int f,_eof;FILE*fi;
        I(FILE*f):fi(f){}
        inline char Gc(){return iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SZ,fi),(iS==iT?EOF:*iS++)):*iS++;}
        inline ll operator()(){ll x;operator()(x);return x;}
        inline I&operator()(char&x){x=Gc();return*this;}
        inline I&operator()(char*s){for(c=Gc();c<32||c>126||c==' ';)c=Gc();for(;c>31&&c<127&&c!=' '&&c!='\n'&&c!='\r';++s,c=Gc())*s=c;*s=0;return*this;}
        template<class T>inline I&operator()(T&x){_eof=0;for(f=1,c=Gc();(c<'0'||c>'9')&&!_eof;c=Gc()){if(c=='-')f=-1;_eof|=c==EOF;}for(x=0;c<='9'&&c>='0'&&!_eof;c=Gc())x=x*10+(c&15),_eof|=c==EOF;x*=f;return*this;}
        template<class T>I&operator()(T*x,const int&n,const int&st=1){rep(i,st,n){operator()(x[i]);}return*this;}
    } in(stdin);
    struct O {
        char obuf[SZ],*oS=obuf,*oT=oS+SZ-1,qu[55];int f,qr;FILE*fi;
        O(FILE*f):fi(f){}
        ~O(){Flush();}
        inline void Flush(){fwrite(obuf,1,oS-obuf,fi),oS=obuf;}
        inline O&operator()(char x){*oS++=x;if(oS==oT)Flush();return*this;}
        inline O&operator()(const char*s){int len=strlen(s);for(f=0;f<len;++f)operator()(s[f]);return*this;}
        template<class T>inline O&operator()(T x){if(!x)operator()('0');if(x<0)operator()('-'),x=-x;while(x)qu[++qr]=x%10+'0',x/=10;while(qr)operator()(qu[qr--]);return*this;}
        template<class T>O&operator()(T*x,const int&n,const char&ed=' ',const int&st=1){rep(i,st,n)operator()(x[i])(ed);return*this;}
    } out(stdout);
}
using FastIO::in;using FastIO::out;
// #define int long long
// using namespace std;
int n,q;
int a[200005];
struct node{
    int tim,lt,rt;
}Q[200005];
long long ans[200005];
int Block,num;
int st[200005];
int ed[200005];
int belone[200005];
int L[200005];
int stk[200005];
int top;
class rmq{
    public:
    int ST[200005][20];
    int lg[200005];
    void init(int a[],int n){
        lg[0]=-1;
        for(int i=1;i<=n;i++){
            lg[i]=lg[i/2]+1;
        }
        for(int i=1;i<=n;i++){
            ST[i][0]=a[i];
        }
        for(int j=1;j<=18;j++){
            for(int i=1;i+(1<<j)-1<=n;i++){
                ST[i][j]=std::max(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
            }
        }
        return;
    }
    int query(int lt,int rt){
        int len=rt-lt+1;
        return std::max(ST[lt][lg[len]],ST[rt-(1<<lg[len])+1][lg[len]]);
    }
}P;
long long need[200005];
signed main(){
    in(n)(q);
    for(int i=1;i<=n;i++){
        in(a[i]);
    }
    P.init(a,n);
    for(int i=1;i<=q;i++){
        int tim,lt,rt;
        in(tim)(lt)(rt);
        Q[i]=node{tim,lt,rt};
    }
    for(int i=n;i>=1;i--){
        while(top&&a[stk[top]]<a[i]){
            L[stk[top]]=i;
            top--;
        }
        stk[++top]=i;
    }
    Block=sqrt(n);
    num=(n+Block-1)/Block;
    for(int i=1;i<=num;i++){
        st[i]=(i-1)*Block+1;
        ed[i]=std::min(i*Block,n);
        for(int j=st[i];j<=ed[i];j++){
            belone[j]=i;
        }
    }
    for(int i=1;i<=num;i++){//处理第Block个块的答案，然后枚举每个询问录入答案。
        for(int j=0;j<=n;j++)need[j]=0;
        for(int k=st[i];k<=ed[i];k++){
            int Max=0;
            for(int j=0;j<=Block;j++){
                if(k>j)Max=std::max(Max,a[k-j]);
                need[j]+=Max;
            }
        }
        int S=st[i],T=st[i]-1;
        int Min=2e9,mini=-1;
        for(int k=st[i];k<=ed[i];k++){
            stk[++T]=P.query(std::max(k-Block,1),k);
        }
        int posL=-1,posR=-1;
        for(int i=S;i<T;i++){
            if(stk[i]<stk[i+1]){//以点i为谷底
                posL=i,posR=i+1;
                break;
            }
        }
        if(posL==-1)posL=T,posR=T+1;
        int seta=P.query(std::max(st[i]-Block,1),st[i]);
        for(int j=Block+1;j<=n;j++){
            if(j<st[i]){//仍在取用新的贡献点
                seta=std::max(seta,a[st[i]-j]);
                stk[--S]=seta;
            }
            //永远不丢掉第一个，如果最小值是第一个那就不做
            need[j]=need[j-1];
            if(posR>T){
                if(posL==S){//不丢第一个
                    continue;
                }
                need[j]+=stk[S]-stk[posL--];
            }
            else{
                if(stk[posL]<stk[posR]){
                    if(posL==S)continue;
                    need[j]+=stk[S]-stk[posL--];
                }
                else{
                    need[j]+=stk[S]-stk[posR++];
                }
            }
        }
        for(int j=1;j<=q;j++){
            if(Q[j].lt<st[i]&&Q[j].rt>ed[i]){
                ans[j]+=need[Q[j].tim];
            }
        }
        //现在stk是单谷的，每次就会丢掉谷的权值，也就是最小值。
    }
    for(int i=1;i<=q;i++){
        int lt=Q[i].lt,rt=Q[i].rt;
        int L=belone[lt];
        int R=belone[rt];
        if(L==R){
            for(int j=lt;j<=rt;j++){
                ans[i]+=P.query(std::max(j-Q[i].tim,1),j);
            }
            continue;
        }
        for(int j=lt;j<=ed[L];j++){
            ans[i]+=P.query(std::max(j-Q[i].tim,1),j);
        }
        for(int j=st[R];j<=rt;j++){
            ans[i]+=P.query(std::max(j-Q[i].tim,1),j);
        }
    }
    for(int i=1;i<=q;i++){
        out(ans[i])('\n');
    }
    return 0;
}