题解：P11622 [Ynoi Easy Round 2025] TEST_176

· · 题解

给点长 n 的序列 \{a\}，q 次询问，要求 x 从 l 开始走到 r，每次令 x \gets \max(x,a_i-x)，最终 x 的值。

考虑离线，一个 trick 是对于这种问题我们可以维护一个数据结构扫描线时动态维护每个点所有询问的值。

具体地，分类讨论一下，对于 x \in (- \infty,\lfloor \frac{a_i}{2}\rfloor]，需要令其 x \gets a_i - x，其余部分不变。

可以使用平衡树维护分裂后修改的操作，但是两部分操作后值域可能有交，我们需要带交合并。

考虑暴力维护合并，我们将两部分拆成若干无交的连续段，再暴力 merge 起来，这样可以通过势能分析证明复杂度是均摊 O(n\log^2 n) 的。

为了保证复杂度，需要对平衡树内的数去重，并查集即可，每次有相同数删掉一个并连边。

:::info[代码]

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define pr putchar(10)
#define fi first
#define se second
#define pp putchar(' ')
#define pii pair<ll,ll>
#define tri tuple<ll,ll,ll>
#define gt(k,x) (get<k>(x))
#define pdi pair<double,ll>
#define mem(aa,bb) memset(aa,bb,sizeof(aa))
#define fo(a,i,b) for(ll i = (a) ; i <= (b) ; ++ i )
#define Fo(a,i,b) for(ll i = (a) ; i >= (b) ; -- i )
#define pb push_back
#define reg register
#define eb emplace_back
#define bct __builtin_popcount 
#define mk make_pair
#define IT iterator
#define all(x) x.begin(),x.end()
#define lbd lower_bound
#define ubd upper_bound
#define lowbit(x) ((x)&(-(x)))
#define gb(x,i) (((x)>>i)&1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define deb(a...) [&](auto...b){char s[]=" , ,"#a;strtok(s,",");((cerr<<strtok(0,",")<<"="<<b<<"; "),...)<<endl;}(__LINE__,a)
//#pragma GCC optimize(2)
using namespace std;
bool ST;

typedef long long i64;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef unsigned long long ull;
typedef __int128 i128;
typedef __uint128_t u128;
typedef double db;

// typedef int ll;
typedef long long ll;
// typedef __int128 ll;

#define getchar getchar_unlocked
#define putchar putchar_unlocked

const ll mod=1e9+7;
template <class T> inline bool ckmn(T &a,T b){return a>b?a=b,1:0;}
template <class T> inline bool ckmx(T &a,T b){return a<b?a=b,1:0;}
template <class T> inline void _A(T &x,T y){x=(x+y>=mod?x+y-mod:x+y);}
template <class T> inline void _M(T &x,T y){x=1ll*x*y%mod;}
template <class T> inline T A_(T x,T y){return (x+y>=mod?x+y-mod:x+y);}
template <class T> inline T M_(T x,T y){return 1ll*x*y%mod;}
template <class T> inline void read(T &s)
{
   s=0;reg int f=1;reg char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
   while(isdigit(c))s=(s<<3)+(s<<1)+(c^48),c=getchar();s*=f;return;
}
template <class T> inline void wr(T x)
{
   if(x<0)putchar('-'),x=-x;int buf[21],top=0;while(x)buf[++top]=x%10,x/=10;
   if(!top)buf[++top]=0;while(top)putchar(buf[top--]^'0');return;
}
template <class T, class ...A> inline void read(T &x,A &...a){read(x);read(a...);}
template <class T, class ...A> inline bool ckmn(T &x,T y,A ...a){return ckmn(x,y)|ckmn(x,a...);}
template <class T, class ...A> inline bool ckmx(T &x,T y,A ...a){return ckmx(x,y)|ckmx(x,a...);}
template <class T, class ...A> inline void _A(T &x,T y,A ...a){_A(x,y),_A(x,a...);}
template <class T, class ...A> inline void _M(T &x,T y,A ...a){_M(x,y),_M(x,a...);}
template <class T, class ...A> inline T A_(T x,T y,A ...a){return A_(A_(x,y),a...);}
template <class T, class ...A> inline T M_(T x,T y,A ...a){return M_(M_(x,y),a...);}

const ll _N=1e6+5;ll Pre[_N],Inv[_N];
inline ll qpow(ll a,ll b){return !b?1ll:M_(1ll*qpow(M_(a,a),b>>1ll),((b&1ll)?a:1ll));}
inline ll C(ll n,ll m){return (n<m||n<0||m<0)?0ll:M_(Pre[n],Inv[m],Inv[n-m]);}
inline void InitC(ll n){Pre[0]=1;fo(1,i,n) Pre[i]=M_(Pre[i-1],i);Inv[n]=qpow(Pre[n],mod-2);Fo(n-1,i,1) Inv[i]=M_(Inv[i+1],(i+1));Inv[0]=1;}

const ll N=1e6+5,M=1e5+5;
ll n,q,a[N],x,l,r,root,tot,ID[N],fa[N],ans[N],st[N];vector<pii> I[N],A[N];
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline ll Find(ll x){return fa[x]==x?x:fa[x]=Find(fa[x]);}
inline void Link(ll x,ll y){x=Find(x),y=Find(y);if(x!=y) fa[x]=y;}
struct FHQTreap{ll l,r,sum,siz,lz1,lz2,f;u32 val;}t[N];
#define rt t[x]
#define ls t[t[x].l]
#define rs t[t[x].r]
inline void ps(ll x){rt.siz=ls.siz+rs.siz+1;rt.f=0;if(rt.l) ls.f=x;if(rt.r) rs.f=x;}
inline void mdf(ll x,ll k){if(x) rt.sum+=k,rt.lz2+=k;}
inline void Mdf(ll x,ll k){if(x) rt.sum*=k,rt.lz1*=k,rt.lz2*=k;}
inline void pd(ll x){if(rt.lz1==-1) Mdf(rt.l,-1),Mdf(rt.r,-1),swap(rt.l,rt.r),rt.lz1=1;if(rt.lz2) mdf(rt.l,rt.lz2),mdf(rt.r,rt.lz2),rt.lz2=0;}
inline void sp(ll x,ll k,ll &u,ll &v){if(!x) return u=v=0,void();pd(x);if(rt.sum<=k) u=x,sp(rt.r,k,t[u].r,v);else v=x,sp(rt.l,k,u,t[v].l);ps(x);}
inline ll mrg(ll x,ll y){if(!x||!y) return x|y;if(rt.val<t[y].val) return pd(x),t[x].r=mrg(t[x].r,y),ps(x),x;return pd(y),t[y].l=mrg(x,t[y].l),ps(y),y;}
inline ll ins(ll k){ll x,y,z;sp(root,k-1,x,y),sp(y,k,y,z),!y?t[++tot]={0,0,k,1,1,0,0,rnd()},fa[tot]=tot,y=tot:1,root=mrg(x,mrg(y,z));return y;}
inline ll Merge(ll x,ll y)
{
    if(!x||!y) return x|y;if(t[x].val>t[y].val) swap(x,y);pd(x),pd(y);
    ll L1=t[x].l,R1=t[x].r,L2=0,R2=0,equ=0;sp(y,t[x].sum-1,L2,R2),sp(R2,t[x].sum,equ,R2);
    if(equ) Link(equ,x);t[x].l=Merge(L1,L2),t[x].r=Merge(R1,R2);return ps(x),x;
}
inline ll qry(ll x){ll z=0,y=x;while(x) st[++z]=x,x=rt.f;while(z) pd(st[z--]);return t[y].sum;}
bool ED;
signed main(){
    read(n,q);fo(1,i,n) read(a[i]);fo(1,i,q) read(x,l,r),I[l].pb(mk(i,x)),A[r].pb(mk(i,x));
    fo(1,i,n)
    {
        for(auto [id,x]:I[i]) ID[id]=ins(x);
        ll x,y;sp(root,a[i]>>1,x,y),Mdf(x,-1),mdf(x,a[i]),root=Merge(x,y);
        for(auto [id,x]:A[i]) ans[id]=qry(Find(ID[id]));
    }fo(1,i,q) wr(ans[i]),pr;

    cerr << "Time: " << (double)clock()/CLOCKS_PER_SEC << "s\n";
    cerr << "Memory: " << abs(&ST - &ED) / 1024.0 / 1024.0 << " MB\n";
    return 0;
}

:::