CF1172F

YZMyangziming · 2024-12-18 18:12:18 · 题解

这道题目题解区都是线段树，我来写一发平衡树合并的做法。

首先这道题目相比于 P5609 是没有强制在线的，所以我们可以考虑离线下来。我们可以先把所有的询问按照左端点排序之后，在左端点处将询问加入平衡树之中，而在右端点的位置统计答案（可以把这个节点删掉，但是我很懒，就保留在平衡树之中了）。

考虑我们现在考虑到第 i 个数，我们会进行将整颗平衡树加上 a_i 的操作。然后我们可以很轻松地在平衡树上找出所有大于等于 p 的数，然后对这些数打上一个区间减的标记。

接下来的这一步是最关键的。我们考虑如何把这两棵树合并回去。合并如果暴力合并是 O(n) 的，但是我们如果可以让每次合并的复杂度为段数（像归并排序一样，把第一颗树的一段放在第一个，然后把第二颗树的一段放在第二部分就可以）。最后的均摊复杂度就是 O(\log^2n) 证明见：https://www.luogu.com/article/mjzkkix。

这是代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T &x){
    x=0;T f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-48;c=getchar();}x=x*f;return;
}
template <typename T>
inline void write(T x){
    if(x<0){putchar('-');x=-x;}
    if(x>9)write(x/10);
    putchar(x%10+48);
}
const int N = 1e6+10;
#define int ll
#define pii pair<int,int>
#define mp make_pair
ll a[N];
struct Query{
    int l,opt,num;
}q[N];
int ans[N],to[N],fa[N];
int n,m,p;
double xx;
clock_t be,ed;
mt19937 rd(time(0));
struct FHQ{
    int rt,siz[N];
    int ch[N][2],cntnode;
    ll tag[N],key[N],maxn[N],val[N];
    #define ls(x) ch[x][0]
    #define rs(x) ch[x][1]
    #define mid ((l+r)>>1)
    void pushdown(int p){
        val[ls(p)]+=tag[p];val[rs(p)]+=tag[p];
        maxn[ls(p)]+=tag[p];maxn[rs(p)]+=tag[p];
        tag[ls(p)]+=tag[p];tag[rs(p)]+=tag[p];
        tag[p]=0;
    }
    void pushup(int p){
        fa[p]=0;//??不确定是否正确
        maxn[p]=max(val[p],max(maxn[ls(p)],maxn[rs(p)]));siz[p]=siz[ls(p)]+siz[rs(p)]+1;
        fa[ls(p)]=fa[rs(p)]=p;
    }
    int merge(int x,int y){
        if(!x||!y)return x|y;
        if(key[x]<key[y]){pushdown(x);rs(x)=merge(rs(x),y);pushup(x);return x;}
        else   {pushdown(y);ls(y)=merge(x,ls(y));pushup(y);return y;}
    }
    pii split(int p,int k){
        if(!p)return mp(0,0);
        pii cur;pushdown(p);
        if(siz[ls(p)]<k){
            cur=split(rs(p),k-siz[ls(p)]-1);rs(p)=cur.first;
            pushup(p);cur.first=p;return cur;
        }else{
            cur=split(ls(p),k);ls(p)=cur.second;
            pushup(p);cur.second=p;return cur;
        }
    }
    int newnode(int pos){
       tag[++cntnode]=0;fa[cntnode]=0;key[cntnode]=rd();
       to[pos]=cntnode;ls(cntnode)=rs(cntnode)=0;
       maxn[cntnode]=0;siz[cntnode]=1;val[cntnode]=0;
       return cntnode;
    }
    int getrank(int p,ll k){
        if(!p)return 0;
        pushdown(p);
        if(val[p]<=k)return siz[ls(p)]+1+getrank(rs(p),k);
        else return getrank(ls(p),k);
    }
    void add(int pos){
        int t=getrank(rt,0);
        pii cur=split(rt,t);
        cur.first=merge(cur.first,newnode(pos));
        rt=merge(cur.first,cur.second);
    }
    ll getf(int x){
        pushdown(x);
        if(ls(x))return getf(ls(x));
        return val[x];
    }
    void mtree(int x,int y){
        // be=clock();
        bool flag=0;
        int t;pii cur;
        rt=0;
        while(x&&y){
            if(!flag){
                t=getrank(x,getf(y));
                cur=split(x,t);
                rt=merge(rt,cur.first);
                x=cur.second;
            }else{
                t=getrank(y,getf(x));
                cur=split(y,t);
                rt=merge(rt,cur.first);
                y=cur.second;
            }
            flag^=1;
        }
        rt=merge(rt,x|y);
        // ed=clock();
        // xx+=1.0*(ed-be);
    }
    void update(int k){
        tag[rt]+=k;maxn[rt]+=k;val[rt]+=k;
        int t=getrank(rt,p-1);
        pii cur=split(rt,t);
        // cout<<"cur.second"<<cur.second<<endl;
        // print(cur.second);
        // cout<<"____"<<endl;
        tag[cur.second]-=p;maxn[cur.second]-=p;
        val[cur.second]-=p;
        mtree(cur.first,cur.second);
    }
    void print(int p){
        if(!p)return;
        pushdown(p);
        print(ls(p));
        cout<<val[p]<<' '<<fa[p]<<' '<<siz[p]<<endl;
        print(rs(p));
        pushup(p);
    }
    #undef mid
}tr;
bool cmp(Query x1,Query x2){
    return x1.l<x2.l;
}
signed main(){
    // clock_t begin,end;
    // freopen("input.txt","r",stdin);
    // freopen("1.out","w",stdout);
    // begin =clock();
    int x;
    read(n);read(m);read(p);
    for(int i=1;i<=n;i++){read(a[i]);}
    for(int i=1;i<=m;i++){read(q[2*i-1].l);read(q[2*i].l);q[2*i].l++;q[2*i-1].opt=1;q[2*i].opt=-1;q[2*i-1].num=i;q[2*i].num=i;}
    sort(q+1,q+1+2*m,cmp);
    int now=1;
    for(int i=1;i<=n+1;i++){
        // cout<<i<<endl;

        for(int &j=now;q[j].l<=i&&j<=2*m;j++){
            if(q[j].opt==1){
                tr.add(q[j].num);
            }else{
                // be=clock();
                x=to[q[j].num];
                ans[q[j].num]=tr.val[x];
                x=fa[x];
                while(x){ans[q[j].num]+=tr.tag[x];x=fa[x];}
                // ed=clock();
                // xx+=1.0*(ed-be);
            }
        }
        tr.update(a[i]);
    }
    for(int i=1;i<=m;i++){
        write(ans[i]);puts("");
    }
    // end=clock();
    // cout<<(xx)/CLOCKS_PER_SEC<<endl;
    return 0;
}