CF1876G

loverintime · 2023-10-09 09:49:37 · 题解

场上想出来了， 但是没时间写了。

首先显然的贪心： 从 r 到 l 扫， 如果当前位置的 a 小于 x， 那就在这里操作一次， 直到其不小于 x。

可以发现在 r 处要操作 \max \{0,\lceil \dfrac{x-a_r}{2} \rceil \} 次。 并且可以发现， 接下来的操作相当于是把 x 减去这个值然后递归到 (l,r-1) 这个子问题中。

所以对于一个询问 (l,r) 可以如下处理：

从 r 扫到 l， 假设当前扫到的是 i。

• 如果当前 x\leq a_i， 那什么都不做。

• 否则将答案加上 \lceil \dfrac{x-a_i}{2} \rceil\times i， 然后将 x 变成 x-\lceil \dfrac{x-a_i}{2} \rceil=\lfloor \dfrac{x+a_i}{2} \rfloor。

考虑所有询问一起处理。 从 n 扫到 1， 扫到 i 时需要做的事情有：

• 加入 r=i 的询问。

• 更新 x>a_i 的询问的 x 以及答案。

• 删除 l=i 的询问。

可以发现瓶颈在于更新 x 以及答案。

注意到排序后的 x 数组在经过更新后顺序是不会变化的。

考虑将所有当前 x 相同的询问合并在一起， 用平衡树维护， 并且暴力更新。

设当前排序后的 x 数组为 x_1,x_2\cdots x_m， 定义势能为 \sum_{i=1}^{m-1} \log(x_{i+1}-x_{i})。 可以发现， 每次加入一个数会增加 O(\log V) 的势能。 每次暴力更新会用 O(k) 的时间减小 k 的势能， 所以暴力操作的总次数是 O(n\log V) 的。

总时间复杂度是 O(n\log nV) 的。

可以通过一些其他东西来代替平衡树。 实现时有一定细节。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mk make_pair
#define lowbit(x) (x&(-x))
#define pb emplace_back
#define pr pair<int,int>
#define let const auto
#define all(A) A.begin(),A.end()
void chkmin(int &x,int y){x=min(x,y);}
void chkmax(int &x,int y){x=max(x,y);}
const int N=3e5+5;
int read(){
    int x=0,f=1; char c=getchar();
    while(('0'>c||c>'9')&&c!='-') c=getchar();
    if(c=='-') f=0,c=getchar();
    while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?x:-x;
}
int n,q,a[N],fa[N],vis[N];;
vector <int> qry[N],nd[N];
ll ans[N],realans[N];
struct node{
    int curx;
    vector <int> ids;
    ll inc;
    node(){curx=0,ids={},inc=0;}
    void init(int _id,int _x){
        curx=_x;
        ids={_id};
    }
    bool operator<(const node &b) const{return curx<b.curx;}
    bool operator==(const node &b) const{return curx==b.curx;}
}s[N];
vector <vector <int> > vec;
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void comb(int &l,int &r){
    if(s[l].ids.size()<s[r].ids.size()) swap(l,r);
    for(auto x:s[r].ids){
        s[l].ids.pb(x);
        ans[x]+=s[r].inc-s[l].inc;
    }
    fa[r]=l;
    s[r].ids.clear();
}
void adj(vector <int> &nw){
    if(nw.size()>1&&s[nw.back()]==s[*prev(prev(nw.end()))]){
        int t=nw.back(); nw.pop_back();
        comb(nw.back(),t);
    }
};
void merge(vector <int> &S,vector <int> &t){
    vector <int> nw;
    int lens=S.size(),lent=t.size();
    int poss=0,post=0;

    for(int i=0; i<lens+lent; i++){
        if(poss==lens||(post!=lent&&s[t[post]]<s[S[poss]]))
            nw.pb(t[post++]);
        else nw.pb(S[poss++]);
        adj(nw);
    }
    swap(S,nw);
}
void insert(int id){
    vec.push_back({id});
    while(vec.size()>1&&vec.back().size()>=(*prev(prev(vec.end()))).size()/2){
        merge(*prev(prev(vec.end())),vec.back());
        vec.pop_back();
    }
}
void solve(int x,int p){
    for(auto &o:vec){
        int len=o.size(),pos;
        for(pos=len; pos&&s[o[pos-1]].curx>x; pos--);
        vector <int> nw(o.begin()+pos,o.end());
        o.resize(pos);
        for(auto pp:nw){
            s[pp].inc+=(s[pp].curx-x+1ll)/2*p;
            s[pp].curx=(s[pp].curx+x)/2;
            o.push_back(pp);
            adj(o);
        }
    }
}
int main(){
    n=read();
    for(int i=1; i<=n; i++) a[i]=read();
    q=read();
    for(int i=1; i<=q; i++) fa[i]=i;
    for(int i=1; i<=q; i++){
        int l=read(),r=read(),x=read();
        qry[r].pb(i),nd[l].pb(i);
        s[i].init(i,x);
    }
    for(int i=n; i; i--){
        for(auto id:qry[i])
            insert(id);
        solve(a[i],i);
        for(auto id:nd[i]){
            int t=find(id);
            realans[id]=ans[id]+s[t].inc;
        }
    }
    for(int i=1; i<=q; i++) printf("%lld\n",realans[i]);
    return 0;
}