当我跨过沉沦的一切
向着永恒开战的时候
你是我的军旗

给定长度为 n 的序列 \{a_i\}_{i=1}^n,有 q 组询问 [l,r],定义三元组 (A,B,C)

  • 是合法的当且仅当 L \le A < B < C \le R(B-A) \leq (C-B)
  • 的权值为 a_A + a_B + a_C

求给定区间内三元组的最大权值。 n ,q \leq 5 \times 10^5,\ a_i \leq 10^9

题解

我们考虑先枚举三元组中的 A,B,注意到一对 (A,B) 是有效的当且仅当 \forall A < x < Ba_x < a_A \land a_x < a_B,否则我们一定可以找到一个 (A,B) 的替代品比 (A,B) 更优。合法的 (A,B)O(n) 的。

剩下的我们用扫描线+线段树维护 f_i 表示 Ci 的三元组最大权值来查询即可。

时间复杂度 O(n \log n)

反思

考场上想到了单调栈维护的思路,但没有去注意状态数。实际上,如果从缩减状态数的角度入手,可能就能想到了吧。

感觉自己在缩减状态数这个方面还是少根弦啊 QAQ。

代码

#include<bits/stdc++.h>
template<class T> inline void read(T &x){
    x=0; register char c=getchar(); register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
}
template<class T> inline void print(T x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10); putchar(x%10+'0');
}
template<class T> inline void print(T x,char c){print(x),putchar(c);}
const int N=5e5+10;
int n,m,top,a[N],ans[N],stk[N];
std::vector<int> b[N];
std::vector<std::pair<int,int>> q[N];
struct node{int l,r,mid,max,flag,local;}p[N<<2];
inline void pushup(int u,int w){
    p[u].flag=std::max(p[u].flag,w);
    p[u].max=std::max(p[u].max,p[u].local+w);
}
inline void pushdown(int u){
    if(p[u].flag==-1||p[u].l==p[u].r)return;
    pushup(u<<1,p[u].flag),pushup(u<<1|1,p[u].flag),p[u].flag=-1;
}
void build(int u,int l,int r){
    p[u].l=l,p[u].r=r,p[u].mid=(l+r)>>1,p[u].max=p[u].flag=-1;
    if(l==r){p[u].local=a[l];return;}
    build(u<<1,l,p[u].mid);
    build(u<<1|1,p[u].mid+1,r);
    p[u].local=std::max(p[u<<1].local,p[u<<1|1].local);
}
void modify(int u,int l,int r,int w){
    // printf("modify %d %d %d %d\n",u,l,r,w);
    pushdown(u);
    if(p[u].l==l&&p[u].r==r){pushup(u,w);return;}
    if(r<=p[u].mid)modify(u<<1,l,r,w);
    else if(l>p[u].mid)modify(u<<1|1,l,r,w);
    else modify(u<<1,l,p[u].mid,w),modify(u<<1|1,p[u].mid+1,r,w);
    p[u].max=std::max(p[u<<1].max,p[u<<1|1].max);
}
int query(int u,int l,int r){
    // printf("query %d %d %d\n",u,l,r);
    pushdown(u);
    if(p[u].l==l&&p[u].r==r)return p[u].max;
    if(r<=p[u].mid)return query(u<<1,l,r);
    if(l>p[u].mid)return query(u<<1|1,l,r);
    return std::max(query(u<<1,l,p[u].mid),query(u<<1|1,p[u].mid+1,r));
}
int main(){
#ifdef memset0
    freopen("1.in","r",stdin);
#endif
    read(n);
    for(int i=1;i<=n;i++)read(a[i]);
    for(int i=1;i<=n;i++){
        while(top&&a[stk[top]]<a[i])b[stk[top--]].push_back(i);
        b[stk[top]].push_back(i),stk[++top]=i;
    }
    // for(int i=1;i<=n;i++)for(int j:b[i])printf("> %d %d\n",i,j);
    read(m);
    for(int l,r,i=1;i<=m;i++){
        read(l),read(r);
        q[l].push_back(std::make_pair(r,i));
    }
    build(1,1,n);
    for(int i=n;i>=1;i--){
        // printf("=== %d ===\n",i);
        for(int j:b[i])if(j*2-i<=n)modify(1,j*2-i,n,a[i]+a[j]);
        for(auto it:q[i])ans[it.second]=query(1,i,it.first);
    }
    for(int i=1;i<=m;i++)print(ans[i],'\n');
}

线段树 扫描线 Favorite

【LGR-060】洛谷10月月赛 I - 谢罪抽奖
上一篇 «
暂别
» 下一篇