题解：P5609 [Ynoi2013] 对数据结构的爱
dyc2022
·
·
题解
更好的阅读体验
我爱数据结构 /qq
观察到题目名存在一个前缀对数，因此我们需要一个对数时间做法。
首先发现我们要求出这个序列经历若干次 -P 的和，也就是要求出区间和，以及某个数经历了这个区间后，-P 的次数。
我们发现对于序列 a 的一个区间，使 -P 次数相等的初始值 x，应该也是连续的一个区间。所以我们考虑对于一个区间，对于每个 i，我们维护出进行恰好 i 次 -P 操作的最小初始值 c_i。我们用线段树维护这个东西，那么一个区间的 -P 次数不大于区间长度。容易分析线段树上所有区间长度之和为 O(n \log n)。
那么我们考虑如何合并线段树上两个节点。假设我们目前希望得到节点 p 的 c 数组，它的左右儿子分别是 l, r。节点 u 对应的区间和是 s_u。
那么假设我们现在希望把 c_{l, i} 和 c_{r, j} 合并到 c_{p, i+j}，需要思考什么情况下可以进行合并。
在这种情况下，进入 l 节点时最大的初始值是 c_{l, i+1} - 1，在此情况下走出 l 节点时的值是 c_{l, i+1} - 1 + s_l - iP，进入 r 节点时最小的初始值是 c_{r, j}。因此需要满足
c_{l, i+1} - 1 + s_l - iP \le c_{r, j}
接下来考虑转移。c_{p, i+j} 的下界，应该是左儿子可以接受的下界，以及右儿子可以接受的下界的较大者。
左儿子的下界显然是 c_{l, i}。右儿子可以接受的下界就是可以看作，把 c_{r, j} 放到左儿子里倒着跑一次，所以就是 c_{r, j} + iP - s_l。所以
c_{p, i+j} \leftarrow \max(c_{l, i}, c_{r, j} + iP - s_l)
这样单个节点的转移是 $O(len^2)$ 的，不可接受。
接下来要说明几个事实：
1. $c_{p, i+1} - c_{p, i} \ge P$。
> 当初始值取到 $c_{p, i}$ 或 $c_{p, i+1}$ 的时候，跑完之后的值应该是 $0$，否则可以经过调整使最后值为 $0$ 而 $-P$ 次数不变。
>
> 由此，我们初始值至少上调 $P$ 才能使经过区间后的值 $\ge P$ 来再支持一次 $-P$ 操作。
2. 对于合法的 $(i, j)$ 和 $(i+1, j-1)$，有
$$\max(c_{l, i}, c_{r, j} + iP - s_l) < \max(c_{l, i+1}, c_{r, j-1} + (i+1)P - s_l)$$
> $c_{l, i} < c_{l, i+1}$ 显然。对于 $c_{r, j} + iP - s_l$ 一项，有
> $$
> \begin{gather}
> c_{l, i+1} - 1 + s_l - iP \le c_{r, j} \nonumber \\
> c_{l, i+1} + s_l - iP < c_{r, j} \nonumber \\
> c_{r, j} + iP - s_l < c_{l, i+1} \nonumber
> \end{gather}
> $$
>
> 因此 $\max(c_{l, i}, c_{r, j} + iP - s_l) < c_{l, i+1} \le \max(c_{l, i+1}, c_{r, j-1} + (i+1)P - s_l)$。
3. 假设对于 $i$，合法的最大的 $j$ 为 $rb_i$。则 $rb$ 数组具有单调性，即 $rb_{i+1} \ge rb_i$。
> 要证明最大的 $j$ 有单调性，即证明 $c_{r, j}$ 有单调性。作差即可。
> $$ (c_{l, i+2} - 1 + s_l - (i+1))P) - (c_{l, i+1} - 1 + s_l - iP) = c_{l, i+2} - c_{l,i+1} - P \ge 0$$
> 因此 $c_{r, rb_{i+1}} - c_{r, rb_i} \ge 0$，故 $rb_{i+1} \ge rb_{i}$。
基于以上三个事实，我们可以使用双指针优化转移。
具体地，我们在双指针的过程中，对于一个 $i$，将 $j$ 尽可能往右扩展。由于事实 3，$j$ 在此过程中只增不减。
再由于事实 2，对于一个固定的 $i+j$，$c_{p, i+j}$ 的最小值一定在 $i$ 最小的时候取得。因此我们对于一个 $i$，只要用在 $[0, i-1]$ 没有扩展到的 $j$ 更新答案就可以了，也就是说，只需要用我们新扩展的 $j$ 更新答案。
综上，我们得以在 $O(n \log n)$ 的时间内预处理出线段树上每个节点的 $c$ 数组。
***
接下来考虑查询。查询非常简单，要想知道一个初始值 $x$ 进入一个区间后会发生多少次 $-P$，由于 $c$ 是单调不降的，因此只需要在该区间所对应节点的 $c$ 数组上二分就可以了。
由于一个区间对应 $O(\log n)$ 个线段树节点，因此单词查询的复杂度为 $O(\log^2 n)$。
那么这道题就做完了，复杂度 $O(n \log n + q \log^2 n)$，需要小力卡常。
代码非常小清新，使用了内存池优化。
```cpp
using i64=long long;
constexpr i64 INF=2e18;
int n,q;
i64 MOD,a[N],lastans;
struct Segtree {
i64 sum[N<<2],c[N<<5];
int now,st[N<<2],ed[N<<2];
inline void build(int p,int l,int r)
{
st[p]=now,now+=r-l+3,ed[p]=now,c[st[p]]=-INF;
for(int i=1;i<=r-l+2;i++)c[st[p]+i]=INF;
if(l==r)
return sum[p]=a[l],c[st[p]+1]=MOD-a[l],(void)0;
int mid=l+r>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
int ls=p<<1,rs=p<<1|1,l_len=mid-l+1,r_len=r-mid;
int sp=st[p],sl=st[ls],sr=st[rs];
i64 l_sum=sum[ls];
for(int i=0,j=0;i<=l_len;i++)
{
j=min(j,r_len),j=max(0,j);
for(;j<=r_len;j++)
{
if(c[sl+i+1]-1-MOD*i+l_sum<c[sr+j]) {j--; break;}
c[sp+i+j]=min(c[sp+i+j],max(c[sl+i],c[sr+j]+MOD*i-l_sum));
}
}
sum[p]=sum[ls]+sum[rs];
}
inline i64 query(int p,int l,int r,int L,int R,i64 x)
{
if(L<=l&&r<=R)
return x+sum[p]-(upper_bound(c+st[p],c+ed[p],x)-c-st[p]-1)*MOD;
int mid=l+r>>1;
if(R<=mid)return query(p<<1,l,mid,L,R,x);
if(L>mid)return query(p<<1|1,mid+1,r,L,R,x);
return query(p<<1|1,mid+1,r,L,R,
query(p<<1,l,mid,L,R,x));
}
} T;
main()
{
n=io.read(),q=io.read(),MOD=io.read<i64>();
for(int i=1;i<=n;i++)a[i]=io.read<i64>();
T.build(1,1,n);
while(q--)
{
int l=io.read()^lastans,r=io.read()^lastans;
i64 x=io.read<i64>()^lastans;
io.writeln(lastans=T.query(1,1,n,l,r,x));
lastans=(lastans%n+n)%n;
}
return 0;
}
```