~~码风可能比较鬼畜~~
by 吾名有灵 @ 2021-09-14 23:05:29
其实这题李超线段树写法会爆空间，所以如果不是数据水李超树是过不了的（理论H要开成 `5e11` ,但是会炸空间，我开`1e9` 水过的）。
给一份代码供参考
```c++
#include <bits/stdc++.h>
#define int long long
#define R register int
#define scanf Ruusupuu = scanf
#define freopen rsp_5u = freopen
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
int Ruusupuu ;
FILE * rsp_5u ;
using namespace std ;
typedef long long L ;
typedef double D ;
const int H = 1e9 ;
const int Inf = 1e18 + 98 ;
const int N = 5e4 + 10 ;
inline int read(){
int w = 0 ; bool fg = 0 ; char ch = getchar() ;
while( ch < '0' || ch > '9' ) fg |= ( ch == '-' ) , ch = getchar() ;
while( ch >= '0' && ch <= '9' ) w = ( w << 1 ) + ( w << 3 ) + ( ch ^ 48 ) , ch = getchar() ;
return fg ? -w : w ;
}
int n , ll , root , znt , c [N] , k [N] , f [N] ;
void sc(){
n = read() , ll = read() ;
for( R i = 1 ; i <= n ; i ++ ) c [i] = read() + c [i - 1] , k [i] = c [i] + i ;
}
struct LINE{ int k , b ; inline int f( int x ){ return k * x + b ; } LINE(){} LINE( int _k , int _b ){ k = _k , b = _b ; } } ;
inline double met( LINE a , LINE b ){ return ( 1.0 * ( b.b - a.b ) ) / ( 1.0 * ( a.k - b.k ) ) ; }
struct T{ int ls , rs ; LINE data ; } t [N << 8] ;
void upd( int &x , int l , int r , LINE w ){
if( !x ) x = ++ znt ;
if( l == r ){
if( t [x].data.f( l ) > w.f( l ) ) t [x].data = w ;
return ;
} if( t [x].data.f( l ) >= w.f( l ) && t [x].data.f( r ) >= w.f( r ) ) return swap( t [x].data , w ) , void() ;
if( t [x].data.f( l ) <= w.f( l ) && t [x].data.f( r ) <= w.f( r ) ) return ;
double mid = ( l + r ) * 0.5 , meet = met( t [x].data , w ) ; int mmid = ( l + r ) >> 1 ;
assert( meet <= r && meet >= l ) ;
if( meet <= mid ){
if( t [x].data.f( r ) >= w.f( r ) ) swap( t [x].data , w ) ;
upd( t [x].ls , l , mmid , w ) ;
} else{
if( t [x].data.f( l ) >= w.f( l ) ) swap( t [x].data , w ) ;
upd( t [x].rs , mmid + 1 , r , w ) ;
}
}
int ask( int x , int l , int r , int pos ){
if( !x ) return 0 ;
if( l == r ) return t [x].data.f( pos ) ;
int mid = ( l + r ) >> 1 ;
if( pos <= mid ) return min( t [x].data.f( pos ) , ask( t [x].ls , l , mid , pos ) ) ;
else return min( t [x].data.f( pos ) , ask( t [x].rs , mid + 1 , r , pos ) ) ;
}
void work(){
for( R i = 1 ; i <= n ; i ++ ){
f [i] = ( ll + 1 ) * ( ll + 1 ) + k [i] * k [i] - 2 * k [i] * ( ll + 1 ) + ask( root , 1 , H , k [i] ) , assert( k [i] <= H ) ;
upd( root , 1 , H , LINE( -2 * k [i] , f [i] + 2 * k [i] * ( ll + 1 ) + k [i] * k [i] ) ) , assert( k [i] <= H ) ;
} printf( "%lld\n" , f [n] ) ;
}
signed main(){ // freopen("fake.in","r",stdin),freopen("fake.out","w",stdout);
sc() ;
work() ;
return 0 ;
}
```
by YksKuusiTAlv @ 2021-10-08 16:26:08
~~我马蜂和您一样鬼畜~~
by YksKuusiTAlv @ 2021-10-08 16:26:59
@[YksKuusiTAlv](/user/365246) 数据不水也行吧，这个可以以1~n为李超树区间，可以设一个$w[i]$表示$sum[i] + i - L + 1$然后计算每个区间的左右端点就不用带入l,r而代入$w[l],w[r]$就行了，而且就算$5e11$也爆不了吧，动态开点李超维护直线的时候空间是O(直线个数)的吧
by Fyrsta_ @ 2022-10-16 11:40:39