主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
【CCPC-桂林 2022】Problem H. Hysteretic Racing 线段树-LogUpdate
最后更新于 2025-07-31 11:13:31
作者
George_Plover
分类
题解
复制 Markdown
查看原文
删除文章
更新内容
## 【CCPC-桂林 2022】Problem H. Hysteretic Racing 线段树-LogUpdate ### 问题分析 https://codeforces.com/gym/104008/problem/H #### 【题意】 给出一个长度为 $n$ 的环,标号为 $0,1,2\cdots n-1$,第 $i$ 号单元的下一个位置是 $i+1\mod n$ 。 第 $i$ 个单元有个困难度 $d_i$ 。 当车在行驶时,假设当前速度是 $v$ ,当车进入困难度为 $d_i$ 的单元时,速度会变成 $\min (\frac{1}{d_i},v)$ 。 车通过一个难度为 $d_i$ 的单元需要用时 $\frac{d_i}{v}$ 。 现在对这个环有 $m$ 个操作: 1. 将环上一个区间的困难度 $+\Delta$ 2. 将环上一个区间的困难度设置为 $d^\prime$ 3. 询问,从 $s$ 单元出发,初速度为 $1$ ,行驶 $t$ 个单位时间后,停在哪个单元。 保证每时每刻每个单元的困难度不超过 $10^6$,$n,m\le 2\times 10^5,t\le 2\times10^{17}$ 。 #### 【思路】 稍加分析,就会发现,车在行使的时候,会保持当前速度直到遇见比自己速度倒数更大的困难度。 因此,单单考虑计算一段行驶的花费时间,实际上就是把行驶过程划为了若干段假设每一段的单元困难度之和为 $h_i$,总时间可以写作 $\sum d_ih_i$ 。其中 $d_i$ 单调递增。 这个模型是 线段树-LogUpdate 的经典模型,在一年前的多校赛出现过,当时我是补了这个题目的,但是没有形成文字记录,比赛时也没有找到合适的时机去写这个题。 --- 我们先思考一个在序列上的问题: $$ D(L,R,d_s) $$ 这个三元组表示从 $L$ 开车开到 $R$ ,初始速度的倒数是 $d_s$ ,所花费的时间。 这个三元组可以区间合并:考虑 $D(L,mid,d_s)+D\big(mid+1,R,\max(d_s,d_{[L.mid]})\big)$ 。 即,先用 $d_s$ 的难度去走左边的区间,走出来之后的难度一定是左半部分最大值和 $d_s$ 取个 $\max$ ,然后再去走右边的区间。但并不是要我们朴素的在线段树上做这个的合并,只是说明这样的性质,它在查的时候用得上。 --- 我们用线段树来维护一个东西: 对结点 $x$ ,假设它左右端点是 $L,R$ 。我们维护 $ti(x)$ 表示 $D\big (mid+1,R,\max(d_i,i\in [L,mid])\big)$ 。 也就是,对每个非叶节点,维护其左子树最大值,并维护以这个最大值作为初始难度,走过右子树区间所花费的时间。 **有了 $ti(x)$ 我们就可以在 $O(\log n)$ 的时间去求解线段树结点区间上任何一个 $D(L,R,d_s)$ 了。** 具体方法是,考虑现在在求解 线段树结点 $x$ 管辖范围的 $D(L,R,d_s)$ ,我们比较 $d_s$ 和 $\max (d_i),i\in[L,mid]$ 的大小,如果 $d_s$ 更小,说明经过了左半部分区间之后,难度值一定恰好变成了左半区间的最值,于是答案就是 $D(L,mid,d_s)+ti(x)$ ,左半部分的求值还需要继续调用,但是其区间缩小了一半;如果 $d_s$ 更大,说明左半部分的时间可以直接用 $d_s\times \sum d_i,i\in[L,mid]$ 求出,这个维护好了之后也是 $O(1)$ 的,答案就是 $(d_s\times \sum d_i)+D(mid+1,R,d_s)$ 。右半部分的求值还需要继续调用。于是发现这个调用只需要在线段树上递归到叶子就能解决。 --- 上面说的是一个结点的 $D(L,R,d_s)$ 问题,限定了左右端点。线段树区间查询通常需要我们把 $O(\log n)$ 个结点的区间合并起来,我们直接按顺序合并,就是 $O(\log^2 n)$ 的复杂度。 然后,关键的一点是,如何维护 $ti(x)$ 。其实就是 $pushup$ 的时候,调用上述算法求解一下,也就是 $D\big(mid+1,R,\max(d_i)\big ),i\in[L,mid]$ 。调用的过程中会用到子树的 $ti(x)$ 值,但因为我们是从下到上的,这样更新没有后效性,而且因为这个原因,$pushup$ 操作复杂度是 $O(\log n)$ 了,这便是它叫做 线段树-LogUpdate 的原因。 也正是这个原因,在这棵线段树上做区间修改也是 $O(\log ^2 n)$ 。 --- #### 【回到这道题】 大致思路:用一棵线段树维护上面的模型,但是要支持区间覆盖和区间加法。 我们通过两倍的链来处理环,在线段树上二分找到最后停下来的位置。**一个细节是**,有可能绕环很多次,但我们知道绕圈一圈速度肯定是整个环最大困难度的倒数,这个时候再绕的每一圈时间都固定,可以mod一下这个周期再跑一遍二分就行了。 在支持区间加法的时候,我们发现维护 $ti(x)$ 出现了一点小困难。我们可以把 $ti(x)$ 写作分段式的代价和,即 $\sum d_i h_i$ ,在区间加上一个 $\Delta$ 的时候,会变成 $\sum (d_i+\Delta)(h_i+w_i\Delta)$ 。其中 $w_i$ 表示的是这个段的单元个数,$h_i$ 是这个段的单元难度值之和。 我们把这个变化结果展开得到四项: $$ \sum d_ih_i \ +\ \Delta\cdot\sum h_i \ +\ \Delta \cdot \sum d_iw_i \ +\ \Delta^2\sum w_i $$ 第一项就是原来的值;第二项是常数乘上整个区间的困难值之和,区间和维护即可;第三项是我们要添加的维护值,不妨记作 $val(x)$ ;第四项就是区间长度乘上常数,直接算就行。 所以我们还需要对每个结点维护 $val(x)$ ,方法和 $ti(x)$ 一致,所以直接把 $D(L,R,d_s)$ 返回的值改成 pair 类型一起维护就可以了,代码复用良好。 ---- #### 【踩坑记录】 在推一个结点的修改的时候,可能会用到右孩子的区间和……然后我就挂了,写完之后硬是没看出来,这是因为在pushdown之前任何调用子结点状态的行为都是危险的。但是我们不能直接暴力调用 pushdown ,这会导致复杂度不对,因为 pushdown 里面也有对结点的修改。 我是在对照杜老师代码的时候发现这个bug的,我发现杜老师对每个结点多维护了一个右孩子的区间和解决了这个问题。我在修bug的时候,选择临时用 $x$ 的 tag 计算了右孩子区间和的真实值,而并不pushdown下去。 ```cpp if(add){ if(L!=R){ if(tr[x].tag_cover)real_r_sum=(R-(L+R)/2)*1ll*tr[x].tag_cover; else real_r_sum = tr[tr[x].r].dis_sum; real_r_sum+=(R-(L+R)/2)*1ll*tr[x].tag_add; } tr[x].tag_add+=add; tr[x].maxx += add; tr[x].l2r_time += add*(L==R?tr[x].dis_sum:real_r_sum) + add*tr[x].l2r_val + add*1ll*add*(R-mid+(L==R)); tr[x].l2r_val += add*1ll*(R-mid+(L==R)); tr[x].dis_sum += (R-L+1)*1ll*add; } ``` --- ### 【参考代码】 感觉写完后,加强了我线段树上二分的实现能力。 总之整体复杂度 $O(n\log ^2 n)$ ```cpp #include <cstdio> #include <assert.h> #include <cstring> #include <iostream> #include <algorithm> #define MAXN 410000 #define LL long long using namespace std; int n,m; int a[MAXN]; struct Segment_Tree{ struct node{ int l,r; int tag_add,tag_cover; int maxx; LL dis_sum; LL l2r_time; LL l2r_val; node(){ l=r=tag_add=tag_cover=0; dis_sum=l2r_time=l2r_val=0; } }tr[MAXN*4]; int num; Segment_Tree(){num=1;} void update_node(int x,int L,int R,int add,int cover){ int mid=(L+R)/2; LL real_r_sum=0; if(cover){ tr[x].tag_add=0;tr[x].tag_cover=cover; tr[x].maxx = cover; tr[x].dis_sum = (R-L+1)*1ll*cover; tr[x].l2r_val = 1ll*cover*(R-mid+(L==R)); tr[x].l2r_time = 1ll*cover*cover*(R-mid+(L==R)); } if(add){ if(L!=R){ if(tr[x].tag_cover)real_r_sum=(R-(L+R)/2)*1ll*tr[x].tag_cover; else real_r_sum = tr[tr[x].r].dis_sum; real_r_sum+=(R-(L+R)/2)*1ll*tr[x].tag_add; } tr[x].tag_add+=add; tr[x].maxx += add; tr[x].l2r_time += add*(L==R?tr[x].dis_sum:real_r_sum) + add*tr[x].l2r_val + add*1ll*add*(R-mid+(L==R)); tr[x].l2r_val += add*1ll*(R-mid+(L==R)); tr[x].dis_sum += (R-L+1)*1ll*add; } } void pushdown(int x,int L,int R){ int mid=(L+R)/2; update_node(tr[x].l,L,mid,tr[x].tag_add,tr[x].tag_cover); update_node(tr[x].r,mid+1,R,tr[x].tag_add,tr[x].tag_cover); tr[x].tag_add=tr[x].tag_cover=0; } pair<LL,LL> Walk(int x,int L,int R,int st){ if(L==R){ if(st<=tr[x].maxx)return make_pair(tr[x].maxx*1ll*tr[x].maxx,tr[x].maxx); else return make_pair(st*1ll*tr[x].maxx,st); } if(st>=tr[x].maxx)return make_pair(st*1ll*tr[x].dis_sum,st*1ll*(R-L+1)); int mid=(L+R)/2; pushdown(x,L,R); if(tr[tr[x].l].maxx > st){ auto Ql = Walk(tr[x].l,L,mid,st); return make_pair(Ql.first+tr[x].l2r_time,Ql.second+tr[x].l2r_val); } else { auto Qr = Walk(tr[x].r,mid+1,R,st); return make_pair(Qr.first+st*1ll*tr[tr[x].l].dis_sum,Qr.second+st*1ll*(mid-L+1)); } } void pushup(int x,int L,int R){ int ls=tr[x].l,rs=tr[x].r; tr[x].maxx = max(tr[ls].maxx,tr[rs].maxx); tr[x].dis_sum = tr[ls].dis_sum+tr[rs].dis_sum; auto tmp = Walk(tr[x].r,(L+R)/2+1,R,tr[ls].maxx); tr[x].l2r_time = tmp.first; tr[x].l2r_val = tmp.second; } void Build(int x,int L,int R){ if(L==R){ tr[x].l2r_time = 1ll*a[L]*a[L]; tr[x].l2r_val = a[L]; tr[x].maxx = tr[x].dis_sum = a[L]; return; } int mid=(L+R)/2; tr[x].l=++num; Build(tr[x].l,L,mid); tr[x].r=++num; Build(tr[x].r,mid+1,R); pushup(x,L,R); } void Update(int x,int L,int R,int al,int ar,int add,int cover){ if(R<al||ar<L)return; if(al<=L&&R<=ar){ update_node(x,L,R,add,cover); return; } int mid=(L+R)/2; pushdown(x,L,R); Update(tr[x].l,L,mid,al,ar,add,cover); Update(tr[x].r,mid+1,R,al,ar,add,cover); pushup(x,L,R); } void Work(int x,int L,int R,int al,int ar,LL &ti,int &v,int &loc){ if(R<al||ar<L)return; if(al<=L&&R<=ar){ if(L==R){ v=max(v,tr[x].maxx); if(ti<v*1ll*tr[x].maxx){ //loc = L; ti = 0; } else{ ti-=v*1ll*tr[x].maxx; loc=L+1; } return; } else{ auto tmp = Walk(x,L,R,v); if(tmp.first<=ti){ v=max(v,tr[x].maxx); ti-=tmp.first; loc=R+1; return; } } } int mid=(L+R)/2; pushdown(x,L,R); Work(tr[x].l,L,mid,al,ar,ti,v,loc); if(!ti)return; Work(tr[x].r,mid+1,R,al,ar,ti,v,loc); } }seg; int main(){ int Case=0; scanf("%d%d",&n,&m); for(int i=0;i<n;i++){ scanf("%d",&a[i]); a[i+n]=a[i]; } seg.Build(1,0,n+n-1); for(int i=1;i<=m;i++){ char op[10]; int l,r,d; scanf("%s",op); if(op[0]=='P'){ scanf("%d%d%d",&l,&r,&d); if(l<=r){ seg.Update(1,0,2*n-1,l,r,d,0); seg.Update(1,0,2*n-1,l+n,r+n,d,0); } else{ seg.Update(1,0,2*n-1,0,r,d,0); seg.Update(1,0,2*n-1,l,r+n,d,0); seg.Update(1,0,2*n-1,l+n,n+n-1,d,0); } } else if(op[0]=='R'){ scanf("%d%d%d",&l,&r,&d); if(l<=r){ seg.Update(1,0,2*n-1,l,r,0,d); seg.Update(1,0,2*n-1,l+n,r+n,0,d); } else{ seg.Update(1,0,2*n-1,0,r,0,d); seg.Update(1,0,2*n-1,l,r+n,0,d); seg.Update(1,0,2*n-1,l+n,n+n-1,0,d); } } else{ ++Case; LL ti; int loc; int v=1; scanf("%d%lld",&loc,&ti); seg.Work(1,0,n+n-1,loc,n+n-1,ti,v,loc); if(!ti){ printf("%d\n",loc%n); } else{ int maxx = seg.tr[1].maxx; LL maxti = maxx*1ll*seg.tr[1].dis_sum; loc=0; ti%=maxti; seg.Work(1,0,n+n-1,0,n+n-1,ti,maxx,loc); printf("%d\n",loc%n); } } } return 0; } ```
正在渲染内容...
点赞
1
收藏
0