[DS记录]P5609 [Ynoi2013] 对数据结构的爱

**题意** ： 给定常数 $p$ ，定义函数 ： $$ {\rm add}(x,y)= \begin{cases} x+y-p&(x+y\geq p)\\ x+y&\rm otherwise \end{cases} $$ 给出一个长为 $n$ 的序列 $A$。 定义 $S(l,r)$ ： $$ S(l,r)= \begin{cases} A_l&(l=r)\\ {\rm add}\big(S(l,r-1),A_r\big)&\rm otherwise \end{cases} $$ 即用 $\rm add$ 从左往右“求和”。 $m$ 次查询 $S(l,r)$ 的值。 $n\leq 10^6,m\leq 2\times 10^5$ ，时限$\texttt{2s}$ ，空限 $\texttt{512M}$。 ------------ 好题。 $n$ 很大，考虑 ${\rm polylog}$ 数据结构。 我们只需求出 “减 $p$” 发生的次数 $t$ ，答案即为 $\sum A_{l\sim r}-tp$。 - **观察** ： 初始值越大，后面进行同样的加法，所触发的减法次数越多。 使用线段树维护。 对于每个节点，记 $t_i$ 表示初始值为 $i$ 时出发的减法次数。 记 $c_i$ 表示触发 $i$ 次减法所需的最小初始值，这里有 $i\leq r-l+1$。 然后 $t$ 可以由 $c$ 描述，其中 $t_{[c_i,c_{i+1})}=i$。 考虑如何合并 $L,R$ 两个节点。 $$U.t_i=L.t_i+R.t_{L.s-p\times L.t_i}$$ 用上式可以快速求 $t$。利用单调性可以二分求解 $c$ ，但效率低下，难以通过。 注意到上式的 $i$ 只需考虑 $c$ 中的值，可以写出由 $c$ 到 $c$ 的转移： $$U.c_{x+y}=\min_{x,y}\max\big(L.c_x,R.c_y-(L.s-xp)\big)$$ 对 $\max$ 分类讨论。 考虑 $\max$ 内的判据 $R.c_y-(L.s-xp)\leq L.c_x$ （贡献为左侧 $L.c.x$），移项可得 $R.c_y\leq L.c_x+L.s-xp$ ，可以证明右边是单调不降的。 - **说明** ： 即证 $c_x-c_{x-1}\geq p$ 。这容易理解 ： 若想要减法多触发一次，至少将初值增大 $p$。 这可以说明，随着 $x$ 的增大，满足条件的 $y$ 的前缀单调不缩。这造就了如下的分界线 ：  如图，蓝色部分是贡献为左的，红色部分是贡献为右的。 由于 $c_x$ 单调增加，蓝色部分的贡献值越靠左贡献值越小，（结合贡献直线的形式）只需考虑分界上的方案。 于是只需线性扫描即可。建树的时空复杂度均为 $O(n\log n)$。 查询时，需要支持给定一个初值求出通过区间后的值。直接在 $c$ 数组中二分即可，复杂度 $O(m\log^2n)$。 代码很简短： ```cpp #include<algorithm> #include<cstdio> #define ll long long #define MaxN 1050000 using namespace std; struct Node{int len;ll *c,s;}a[MaxN<<1]; ll _buf[MaxN*22],*tp=_buf; int p; void up(int u) { int l=u<<1,r=u<<1|1; a[u].s=a[l].s+a[r].s; for (int i=0;i<=a[u].len;i++)a[u].c[i]=1ll<<60; #define chk(x,y) a[u].c[x+y]=min(a[u].c[x+y],max(a[l].c[x],a[r].c[y]-(a[l].s-1ll*x*p))); int x=0,y=0; for (;x<=a[l].len;x++){ chk(x,y);if (x>0&&y<a[r].len)chk((x-1),y+1); while(y<a[r].len&&a[r].c[y+1]<=a[l].c[x]+a[l].s-1ll*x*p) {y++;chk(x,y);if (x>0&&y<a[r].len)chk((x-1),y+1);} }while(y<a[r].len){y++;chk(a[l].len,y);} } int x[MaxN]; void build(int l,int r,int u) { a[u].len=r-l+1; a[u].c=tp;tp+=a[u].len+1; if (l==r){ a[u].s=x[l]; a[u].c[0]=-1ll<<60; a[u].c[1]=p-x[l]; return ; }int mid=(l+r)>>1; build(l,mid,u<<1); build(mid+1,r,u<<1|1); up(u); } int wfl,wfr;ll ret; void qry(int l,int r,int u) { if (wfl<=l&&r<=wfr){ int t=upper_bound(a[u].c,a[u].c+a[u].len+1,ret)-a[u].c-1; ret+=a[u].s-1ll*t*p; return ; }int mid=(l+r)>>1; if (wfl<=mid)qry(l,mid,u<<1); if (mid<wfr)qry(mid+1,r,u<<1|1); } int n,m; int main() { scanf("%d%d%d",&n,&m,&p); for (int i=1;i<=n;i++)scanf("%d",&x[i]); build(1,n,1); for (int i=1;i<=m;i++){ scanf("%d%d",&wfl,&wfr); ret=0;qry(1,n,1); printf("%lld\n",ret); }return 0; } ``` - CF 重题 ： [CF1172F Nauuo and Bug](https://www.luogu.com.cn/problem/CF1172F)