P5609 [Ynoi2013]对数据结构的爱 / CF1172F [* hard]
题意见 link
Solution
查询的答案其实就是区间和减去 (k imes p)，(k) 表示被减 (p) 的次数。
考虑线段树，我们考虑做完一个区间后肯定会剩余和 (S)，然后我们将 (S) 输入给一个区间后肯定会减去若干个 (p)
假设区间长度为 (r-l+1)，那么我们至多减去 (r-l+1) 个 (p)，同时，我们减去的 (p) 的数量关乎于初始输入的参数，这样会形成一个分段函数，我们假设进行了预处理，那么就可以直接通过二分来进行查询。
所以我们的处理思路就是将这些分段函数预处理出来，然后查询就直接二分 (log n) 个区间即可，复杂度 (mathcal O(qlog^2 n))
考虑预处理，我们将小区间合并为大区间。
设 (c_i) 表示最小的 (S) 使得输入进来后被减去了 (i) 个 (p)
我们知道了 (c_{[ m l,mid]},c_{[ m mid+1,r]})，我们希望得到 (c_{[l,r]})
对于一组 (x,y)，我们可以合并得到 (c_{x+y})，假设此时以 (S) 作为初值输入进来，我们有 (S-x imes p+sum_{l}ge c_y,Sge c_x) 那么就可以更新一次答案。
于是有 (c_{x+y}=min(c_{x+y},max(c_y+x imes p-sum_l,c_x)))
然后显然我们这样不一定会得到到最优解，但是这个限制比最优解要求的限制更松，同时一定能够得到最优解。
基于这样的考量，我们希望计算 (x+y) 相同的对子中最小的 (max(c_x,c_y+x imes p-sum_l))
事实上，(c_x) 是单调的，(c_y) 是单调的，我们的决策必然是扫到一个 (x) 使得 (c_y+x imes p-sum_l) 小于他，以及严格大于他，更新两次答案。
这样，当 (c_x) 增大的过程，我们只需要证明相应的 (y) 会单调，即 (c_{y}-c_{y-1}ge p)（感性上看着挺对的）
这样就可以通过双指针来合并 (c) 数组了，复杂度 (mathcal O(qlog^2 n+nlog n))
- 可以考虑 (x+y=k) 合并了一次答案，此时 ((x+1)+(y-1)) 如何无法对答案产生贡献。
(Code:)
#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define vi vector<int>
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define pb push_back
#define int long long
int gi() {
char cc = getchar() ; int cn = 0, flus = 1 ;
while( cc < '0' || cc > '9' ) { if( cc == '-' ) flus = - flus ; cc = getchar() ; }
while( cc >= '0' && cc <= '9' ) cn = cn * 10 + cc - '0', cc = getchar() ;
return cn * flus ;
}
const int N = 1e6 + 5 ;
const int inf = 1e18 + 7 ;
int n, m, p, a[N], S ;
struct Tr {
int sum, len ; vi f ;
} tr[N << 2] ;
void pushup(int x) {
vi l = tr[ls(x)].f, r = tr[rs(x)].f ;
vi c ; c.resize(tr[x].len + 1) ;
rep( i, 0, tr[x].len ) c[i] = inf ; int j = 0 ;
for(int i = 0; i < l.size(); ++ i) {
int d = i * p - tr[ls(x)].sum ; if(j) -- j ;
for(; j < r.size(); ++ j) {
int res = max( l[i], r[j] + d ) ;
c[i + j] = min( c[i + j], res ) ;
if( i != (l.size() - 1) ) {
int mx = l[i + 1] - d ;
if( mx <= r[j] ) { if(j) -- j ; break ; }
}
}
} tr[x].f = c, tr[x].sum = tr[ls(x)].sum + tr[rs(x)].sum ;
}
void build(int x, int l, int r) {
tr[x].len = r - l + 1 ;
if( l == r ) { tr[x].sum = a[l], tr[x].f.pb(-inf), tr[x].f.pb(p - a[l]) ; return ; }
int mid = (l + r) >> 1 ;
build(ls(x), l, mid), build(rs(x), mid + 1, r), pushup(x) ;
}
void query(int x, int l, int r, int ql, int qr) {
if( ql <= l && r <= qr ) {
int res = upper_bound(tr[x].f.begin(), tr[x].f.end(), S) - tr[x].f.begin() - 1 ;
S = S + tr[x].sum - res * p ; return ;
}
if( qr < l || ql > r ) return ;
int mid = (l + r) >> 1 ;
query(ls(x), l, mid, ql, qr), query(rs(x), mid + 1, r, ql, qr) ;
}
void Q(int l, int r) {
S = 0, query(1, 1, n, l, r), printf("%lld
", S ) ;
}
signed main()
{
n = gi(), m = gi(), p = gi() ;
rep( i, 1, n ) a[i] = gi() ;
build(1, 1, n) ; int l, r ;
while( m -- ) l = gi(), r = gi(), Q(l, r) ;
return 0 ;
}