题解：P7922 [Kubic] Pyramid

_lbw_ · 2024-08-05 17:05:12 · 题解

爆标做法。

观察题目，发现这个又是最小值又是最大值非常难搞，每次 AB 操作次数相等看起来也没什么用。

我们考虑通过枚举 w，将 \geq w 转为 1，剩下的为 0，这里复杂度看起来全错，但是等一下就对了。

这个东西怎么计算答案呢？我们知道 A=\sum_{i}(w_i-w_{i-1})[A\geq w_i] 于是把每个 w_i 对询问时的贡献即为最终序列中 1 个数乘上 w_i-w_{i-1}。

取出初始序列中所有极长 1 连续段，模拟可知：

每次 A 操作会使 1 连续段右端点左移一位
每次 B 操作会使 1 连续段左端点左移一位

因此，做完一个整段操作后，会使所有段往左移动 a_i 位，并且长度小于 a_i 的段会被删除。

这个形式的性质非常好！同时，它启发我们找出所有初始序列中所有极长 1 连续段。

每一次 w_i 增加的时候，会变化的极长 1 连续段是 \mathcal{O}(1) 的，我们把相同的极长 1 连续段缩起来，这样最多只会有 \mathcal{O}(n) 个段 (l_i,r_i,v_i)，记段长为 L_i。

这一段的代码如下：

IV add(i64 l,i64 r,i64 v){
    tot++;
    L[tot]=l;R[tot]=r;V[tot]=v;
}
int main(){
    n=read();m=read();q=read();
    FL(i,1,n)pi[i]=make_pair(b[i]=read(),i);
    F(i,1,m)a[i]=read();sort(pi+1,pi+1+n);
    add(1,n,0);
    st.insert({1,n});
    F(i,1,n){
        i64 v=pi[i].first,pos=pi[i].second;
        auto p=prev(st.upper_bound({pos}));
        auto[l,r]=*p;add(l,r,v);st.erase(p);
        if(l<pos)st.insert({l,pos-1}),add(l,pos-1,-v);
        if(pos<r)st.insert({pos+1,r}),add(pos+1,r,-v);
    }
}

如果只会在整段处询问，问题即为每次给定 w,\Delta_l,\Delta_r,ql,qr 求：

\sum_{L_i\geq w}v_i\left|[l_i-\Delta_l ,r_i-\Delta_r]\cap[ql,qr]\right|

这里 \Delta_l=\Delta_r，所以我们可以直接把 [ql,qr] 往后平移。

于是，此问题可以通过直接从小到大枚举 L_i 同时维护区间加-区间查询的数据结构做到 n\log n。

若查询不在整段，我们仍然可以计算一个 w 表示区间最小可能长度，而 \Delta_l 和 \Delta_r 不一定相等。

注意到分类讨论一堆大小关系多维偏序就可以做到 \textsf{polylog} 了，考虑优化 \log 数量。

首先有 \Delta_l\leq \Delta_r，平移区间，问题转化为：

\sum_{L_i\geq w}v_i|[l_i ,r_i-k]\cap[ql_i,qr_i]|

拆分左右端点贡献，枚举左/右端点取值，列出区间长度 \geq 0 的不等式，为三维偏序，时间复杂度 \mathcal{O}((n+q)\log ^2n)。

代码。

进一步，考虑容斥，有：

前半部分与查询不在整段一致，容易解决。

容易发现后半部分不同位置 r_i 的贡献为分段一次函数，可以用树状数组维护单点加，区间查询 \sum v 和 \sum v\times pos。

时间复杂度 \mathcal{O}((n+q)\log n)，代码如下。

#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#include<cstdio>
#include<vector>
#include<random>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
#define her1 20081214
#define cht 998244353
#define I i64
#define IV void
#define ull unsigned long long
#define mem(x,val) memset(x,val,sizeof x)
#define F(i,j,n)for(register int i=j;i<=n;i++)
#define D(i,j,n)for(register int i=j;i>=n;i--)
#define E(i,now)for(register int i=first[now];i;i=e[i].nxt)
#define FL(i,j,n)for(register i64 i=j;i<=n;i++)
#define DL(i,j,n)for(register i64 i=j;i>=n;i--)
#define EL(i,now)for(register i64 i=first[now];i;i=e[i].nxt)
ll read(){
    ll ans=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')ans=ans*10+c-'0',c=getchar();
    return ans*f;
}
#undef ll
#include "assert.h"
mt19937_64 rnd(her1);
#include "functional"
using i64 = long long;
const int maxn = 1.5e5+5;
i64 n,m,q,b[maxn],a[maxn];char s[maxn];
struct sg{
    i64 l,r;
    bool operator<(const sg&V)const{
        return l<V.l;
    }
};
set<sg>st;pair<i64,i64>pi[maxn];
i64 L[maxn],R[maxn],V[maxn],tot,all;
struct node{
    i64 l,r,len,v,K,id;
}qwq[maxn*5];
IV add(i64 l,i64 r,i64 v){
    tot++;
    // L[tot]=l;R[tot]=r;V[tot]=v;
    qwq[tot]={l,r,r-l+1,v,0,0};
}
i64 sa[maxn],mx[maxn],sl[maxn],sr[maxn];

long long Ans[maxn];
struct BIT{
    long long c[maxn],qwq[maxn],tot,ans;bool vis[maxn];
    IV clr(){F(i,1,tot)vis[qwq[i]]=c[qwq[i]]=0;tot=0;}
    IV add(i64 p,long long v){
        for(;p<=n;p+=p&-p){
            if(!vis[p])vis[qwq[++tot]=p]=1;
            c[p]+=v;
        }
    }
    i64 Q(i64 p){
        if(p<1)return 0;p=min(p,n);
        ans=0;for(;p;p-=p&-p)ans+=c[p];return ans;
    }
    i64 Q(i64 l,i64 r){
        if(r<1||l>n)return 0;
        return Q(r)-Q(l-1);
    }
};

struct DS{
    #define ls (o<<1)
    #define rs (o<<1|1)
    i64 len[4*maxn],sum[4*maxn],tag[4*maxn];
    IV upd(i64 o){sum[o]=sum[ls]+sum[rs];}
    IV givet(i64 o,i64 v){sum[o]+=len[o]*v;tag[o]+=v;}
    IV pd(i64 o){if(!tag[o])return;givet(ls,tag[o]);givet(rs,tag[o]);tag[o]=0;}
    IV M(i64 o,i64 l,i64 r,i64 x,i64 y,i64 v){
        if(x<=l&&r<=y)return givet(o,v);if(r<x||l>y)return;pd(o);
        i64 mid=l+r>>1;M(ls,l,mid,x,y,v);M(rs,mid+1,r,x,y,v);upd(o);
    }
    i64 Q(i64 o,i64 l,i64 r,i64 x,i64 y){
        if(x<=l&&r<=y)return sum[o];if(r<x||l>y)return 0;pd(o);
        i64 mid=l+r>>1;return Q(ls,l,mid,x,y)+Q(rs,mid+1,r,x,y);
    }
    IV Build(i64 o,i64 l,i64 r){
        len[o]=r-l+1;if(l==r)return;i64 mid=l+r>>1;
        Build(ls,l,mid);Build(rs,mid+1,r);
    }
}ds;
struct DS2{
    BIT b1,b2;
    IV add(i64 p,i64 v){
        b1.add(p,v);
        b2.add(p,p*v);
    }
    i64 Q(i64 ql,i64 qr,i64 k){
        i64 sum=0;
        if(qr-ql+1>=k){
            sum+=b2.Q(ql,ql+k-1)-(ql-1)*b1.Q(ql,ql+k-1);
            sum+=(qr+k)*b1.Q(qr+1,qr+k-1)-b2.Q(qr+1,qr+k-1);
            sum+=k*b1.Q(ql+k,qr);
        }
        else{
            sum+=b2.Q(ql,qr)-(ql-1)*b1.Q(ql,qr);
            sum+=b1.Q(qr+1,ql+k-1)*(qr-ql+1);
            sum+=(qr+k)*b1.Q(ql+k,qr+k-1)-b2.Q(ql+k,qr+k-1);
        }
        return sum;
    }
}ds2;
int main(){
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);

    n=read();m=read();q=read();
    FL(i,1,n)pi[i]=make_pair(b[i]=read(),i);
    F(i,1,m)a[i]=read();sort(pi+1,pi+1+n);

    F(i,1,m){
        F(j,1,a[i])s[++all]='A';
        F(j,1,a[i])s[++all]='B';
    }
    F(i,1,all){
        sr[i]=sr[i-1]+(s[i]=='A');
        sl[i]=sl[i-1]+(s[i]=='B');
    }
    F(i,1,m){
        mx[i]=max(mx[i-1],a[i]);
        sa[i]=sa[i-1]+2*a[i];
    }
    add(1,n,0);
    st.insert({1,n});
    F(i,1,n){
        i64 v=pi[i].first,pos=pi[i].second;
        auto p=prev(st.upper_bound({pos}));
        auto[l,r]=*p;add(l,r,v);st.erase(p);
        if(l<pos)st.insert({l,pos-1}),add(l,pos-1,-v);
        if(pos<r)st.insert({pos+1,r}),add(pos+1,r,-v);
    }
    F(i,1,q){
        i64 x=read(),ql=read(),qr=read(),ans=0;
        i64 pos=lower_bound(sa+1,sa+1+m,x)-sa-1;
        i64 nd=max(mx[pos],min(x-sa[pos],a[pos+1]));
        i64 dl=sl[x],dr=sr[x],K=dr-dl;ql+=dl;qr+=dl;
        qwq[++tot]={ql,qr,nd,0,K,i};
    }
    sort(qwq+1,qwq+1+tot,[](node A,node B){
        return A.len==B.len?A.id>B.id:A.len>B.len;
    });
    ds.Build(1,1,n);
    F(i,1,tot){
        if(!qwq[i].id){
            ds.M(1,1,n,qwq[i].l,qwq[i].r,qwq[i].v);
            ds2.add(qwq[i].r,qwq[i].v);
        }
        else{
            Ans[qwq[i].id]+=ds.Q(1,1,n,qwq[i].l,qwq[i].r);
            Ans[qwq[i].id]-=ds2.Q(qwq[i].l,qwq[i].r,qwq[i].K);
        }
    }
    F(i,1,q)printf("%lld\n",Ans[i]);
    return 0;
}