P11622 [Ynoi Easy Round 2025] TEST_176 题解

· · 题解

插入标记回收算法的板子题。

这个算法类似扫描线，可以解决的是一些离线的函数复合维护问题，要求维护的函数可以快速对多个数字进行变换。

比如这题出现的 f_i(x)=\max(x,a_i-x)，如果要对多个数字同时进行 x\gets f_i(x)，我们显然用平衡树维护，然后考虑拆 \max，这个值域分裂成两部分，一部分不变，一部分取反再整体加就行，最后套一个平衡树合并。

我们从左到右扫描，当扫描到位置 i 时：

时间复杂度 \mathcal O(n\log^2n)，瓶颈是平衡树合并。

问题是李欣隆很邪恶，这题卡常，怎么办呢？考虑平衡树合并减小常数，我们分讨值域，值域大的时候我们跑经典的随机有交合并，值域小我们跑启发式合并。

#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
const int N=3e5+5;
int n,m,Rt;
struct Tree
{
    int Ls,Rs,Fa,R,P;
    LL Lz,V;
}t[N];

LL A[N],Ans[N];
mt19937 Rnd(time(0));
struct Query{LL x;int Id;};
vector<Query>Q[N],C[N];
inline void Ad(int u,LL x)
{
    if(!u)return;
    t[u].V+=x,t[u].Lz+=x;
}
inline void Rv(int u,int x)
{
    if(!u||!x)return;
    t[u].V=-t[u].V,t[u].R^=x,t[u].Lz=-t[u].Lz;
    swap(t[u].Ls,t[u].Rs);
}
inline void Down(int u)
{
    if(t[u].R!=0)Rv(t[u].Ls,t[u].R),Rv(t[u].Rs,t[u].R),t[u].R=0;
    if(t[u].Lz!=0)Ad(t[u].Ls,t[u].Lz),Ad(t[u].Rs,t[u].Lz),t[u].Lz=0;
}
inline void Up(int u)
{
    if(t[u].Ls)t[t[u].Ls].Fa=u;
    if(t[u].Rs)t[t[u].Rs].Fa=u;
}
void Mrg(int &u,int u1,int u2)
{
    if(!u1||!u2)u=u1+u2;
    else
    {
        Down(u1),Down(u2);
        if(t[u1].P<t[u2].P)u=u1,Mrg(t[u1].Rs,t[u1].Rs,u2);
        else u=u2,Mrg(t[u2].Ls,u1,t[u2].Ls);        
        Up(u);
    }
}
void Spl(int u,int &u1,int &u2,LL x)
{
    if(!u)u1=u2=0;
    else
    {
        Down(u);
        if(t[u].V<=x)u1=u,Spl(t[u].Rs,t[u].Rs,u2,x);
        else u2=u,Spl(t[u].Ls,u1,t[u].Ls,x);
        Up(u);
    }
}
LL Min(int u)
{
    while(t[u].Ls)Down(u),u=t[u].Ls;
    return t[u].V;
}
void Merg(int &z,int x,int y)
{
    z=0;
    while(x&&y){
        LL vx=Min(x),vy=Min(y);
        if(vx>vy)swap(vx,vy),swap(x,y);
        int w;Spl(x,w,x,vy);
        Mrg(z,z,w);
    }
    Mrg(z,z,x),Mrg(z,z,y);
}
LL Mx=0;
void Merge(int &u,int u1,int u2)
{
    if(Mx<=1000000)return Merg(u,u1,u2),void();
    if(!u1||!u2)u=u1+u2;
    else
    {
        Down(u1),Down(u2);
        if(t[u1].P>t[u2].P)swap(u1,u2);
        u=u1;
        int u3,u4;
        Spl(u2,u3,u4,t[u1].V);
        Merge(t[u1].Ls,t[u1].Ls,u3),Merge(t[u1].Rs,t[u1].Rs,u4);
        Up(u);
    }   
}
inline void Ins(int u,LL x)
{
    t[u].V=x,t[u].P=Rnd();
    int u1,u2;
    Spl(Rt,u1,u2,x);
    Mrg(u1,u1,u),Mrg(Rt,u1,u2);
}
inline LL Qry(int x)
{
    int h=x;
    vector<int>F;
    while(t[x].Fa)F.pb(x),x=t[x].Fa;
    F.pb(x);
    reverse(F.begin(),F.end());
    for(int i:F)Down(i);
    return t[h].V;
}
inline void Work(LL x)
{
    int u1,u2;
    Spl(Rt,u1,u2,x>>1);
    Rv(u1,1),Ad(u1,x);
    Merge(Rt,u1,u2);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&A[i]),Mx=max(Mx,A[i]);
    for(int i=1,l,r;i<=m;i++)
    {
        LL x;
        scanf("%lld%d%d",&x,&l,&r);
        Q[r].pb({x,i}),C[l].pb({x,i});
    }
    for(int i=1;i<=n;i++)
    {
        for(auto x:C[i])Ins(x.Id,x.x);
        Work(A[i]);
        for(auto x:Q[i])Ans[x.Id]=Qry(x.Id);
    }
    for(int i=1;i<=m;i++)printf("%lld\n",Ans[i]);
}