题解：P3246 [HNOI2016] 序列

kevinZ99 · 2024-12-10 13:31:58 · 题解

这是一篇五分钟可以写完的乱搞做法

solution

看到这个询问第一可以很明显看的出来可以使用最值分治，我们可以使用 st 表找到最值的位置，复杂度 \mathcal{O}(qn)，超时，考虑优化，由于没有修改，所以直接使用记忆化，将 [l,r] 的答案记下来即可 AC 。

code

//Author:Kevin Z K Y
#include <bits/stdc++.h>
#define up(a,b,c) for(int (a)=(b);(a)<=(c);(a)++)
#define dn(a,b,c) for(int (a)=(b);(a)>=(c);(a)--)
#define fst first
#define sed second
using namespace std;
using ll = long long ;using hint = __int128 ;
using pii = pair<int,int> ;using pll = pair<ll,ll> ;
using vi = vector<int> ;using vl = vector<ll> ;
using vpi = vector<pii> ;using vpl = vector<pll> ;
using db = double ;namespace mystl{
    #define gc() getchar()
    ll qpow(ll a,ll b,const ll&p){if (a==0ll) return 0ll; ll c=1ll;
        while(b) { if(b & 1) c=a*c%p; a=a*a%p; b>>=1; } return c; }
    template<typename T>void read(T&x) {x=0; bool f=false; char ch;
        ch = gc(); while(ch<'0'||ch>'9') f |= ( ch=='-') , ch=gc();
        while(ch>='0'&&ch<='9') x=x*10+ch-'0' , ch=gc(); x=f?-x:x;}
    template<typename T>void write(T x){char s[40];short d=0;T y=x;
        if(x<0) putchar('-'),y=-y;if(x==0){ putchar('0'); return; }
        while(y){s[++d]=y%10+'0';y/=10;}while(d>0)putchar(s[d--]);}
    template<typename T>void wris(T x,char c){write(x);putchar(c);}
}using namespace mystl;
namespace my{
    const int N=100005;
    ll a[N];
    map<pii,ll>G;
    ll f[N][25];
    int n,q;
    int id[N][25];
    void build_st_table(){
        up(i,1,n)f[i][0]=a[i],id[i][0]=i;
        for(int i=1;(1<<i)<=n;i++)
            for(int j=1;j+(1<<i)-1<=n;j++)
                if(f[j][i-1]<f[j+(1<<(i-1))][i-1])
                    f[j][i]=f[j][i-1],id[j][i]=id[j][i-1];
                else 
                    f[j][i]=f[j+(1<<(i-1))][i-1],id[j][i]=id[j+(1<<(i-1))][i-1];
    }
    int query(int l,int r){
        int len=(r-l+1);
        int kget=log2(r-l+1);
        if(f[l][kget]<f[r-(1<<(kget))+1][kget])
            return id[l][kget];
        else 
            return id[r-(1<<(kget))+1][kget];
    }
    ll solve(int l,int r){
        if(l>r)return 0;
        if(l==r)return a[l];
        pii p={l,r};
        if(G[p])return G[p];
        int pos=query(l,r);
        return G[p]=solve(l,pos-1)+solve(pos+1,r)+(pos-l+1)*(r-pos+1)*a[pos];   
    } 
    void solve(){
        cin>>n>>q;
        up(i,1,n)cin>>a[i];
        build_st_table();
        while(q--){
            int L,R;cin>>L>>R;
            cout<<solve(L,R)<<'\n';
        }
    }
}
int main(){
//  freopen("","r",stdin);
//  freopen("","w",stdout);
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int _=1;while(_--)my::solve();return 0;
}

闲话

这个数据还是非常的逆天，这都能过，确实非常离谱。