比赛链接

A sequence

首先，和谐的数列可以仅由前两个数递推得到。然后可以证明，如果第一个数确定，答案关于第二个数凸，如果第二个数永远取最优，答案关于第一个数凸。所以可以直接三分套三分来做。但是这样是 $O(n\log^2 v)$ 的，很可能会被卡 T 。

考虑和谐的序列的循环节一定是 $6$ ，所以可以对于 $\bmod 6$ 的所有值分别整个 vector 再做个前缀和，查询可以直接从每个 vector 二分。复杂度 $O(n\log n + \log^3 v)$

当然，也可以暴力整凸包复杂度是 $O(n\log n)$ 的，可以见 zjk 的实现。

#define P 1000000007
int n , m , k;
int A[MAXN] , B[MAXN];
vi a[6]; vector<ll> s[6];

#define abs( x ) ( (x) > 0 ? (x) : -(x) )

ll check( int x , int y ) {
    ll ret = 0;
    B[0] = x , B[1] = y , B[2] = y - x , B[3] = -x , B[4] = -y , B[5] = x - y;
    rep( i , 0 , 5 ) {
        if( s[i].empty() ) continue;
        int ps = upper_bound( all( a[i] ) , B[i] ) - a[i].begin() - 1;
        ret += ( ps + 1 - ( a[i].size() - ps - 1 ) ) * B[i] + s[i].back();
        if( ps != -1 ) ret -= s[i][ps] + s[i][ps];
    }
    return ret;
}

ll check( int x ) {
    int l = -1e9 , r = 1e9 , mid; ll t;
    while( l <= r ) {
        mid = l + r >> 1;
        ll a = check( x , mid ) , b = check( x , mid + 1 );
        t = min( a , b );
        if( a < b ) r = mid - 1;
        else l = mid + 1;
    }
    return t;
}

void solve() {
    cin >> n;
    rep( i , 0 , n - 1 ) scanf("%d",A + i) , a[i % 6].pb( A[i] );
    rep( i , 0 , 5 ) {
        sort( all( a[i] ) );
        for( int x : a[i] ) {
            if( s[i].empty() ) s[i].pb( 0 );
            else s[i].pb( s[i].back() );
            s[i].back() += x;
        }
    }
    int l = -1e9 , r = 1e9 , mid;
    ll ans = 0x3f3f3f3f;
    while( l <= r ) {
        mid = l + r >> 1;
        ll a = check( mid ) , b = check( mid + 1 );
        ans = min( a , b );
        if( a < b ) r = mid - 1;
        else l = mid + 1;
    }
    cout << ans << endl;
}

signed main() {
//    freopen("lsj.txt","r",stdin);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}

B antimatter

空间复杂度很离谱啊。。

考虑 $dp[i]$ 表示剩下 $i$ 克反物质，然后我们可以枚举哪个实验转移。

可以对于每种实验单独开一个单调队列来优化。

空间复杂度看起来很炸，实际上能跑。。

int n , m;
const ll C = 1e9;
int l[MAXN] , r[MAXN] , c[MAXN] , ps[110]; deque<int> que[110];
ll dp[MAXN];

ll calc( int p ) {
	return dp[p] - p * C;
}

void solve() {
	cin >> n >> m;
	rep( i , 1 , n ) scanf("%d%d%d",l + i,r + i,c + i);
	rep( i , 1 , m ) rep( j , 1 , n ) if( r[j] <= i ) {
		while( ps[j] <= i - l[j] ) {
			while( !que[j].empty( ) && calc( que[j].back( ) ) >= calc( ps[j] ) ) que[j].pop_back();
			que[j].push_back( ps[j] ) , ++ ps[j];
		}
		while( !que[j].empty() && que[j].front() < i - r[j] ) que[j].pop_front();
		if( que[j].size() )
				dp[i] = max( dp[i] , calc( que[j].front() ) - c[j] + i * C );
	}
	printf("%lld\n",dp[m]);
}

signed main() {
//    freopen("input","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
	solve();
}

C 游走

基本类似 P5155 。

神仙结论：最后停止位置一定在凸包上。

所以答案就是某个点在凸包上的值。

证明可以取看 5155 题解。

#define P 998244353
int n , m , k;
ll A[MAXN];

struct poi {
    ll x , y;
} p[MAXN] ; int top = 0;
int ans[MAXN];
double getk( poi& a , poi& b ) {
    return ( 1.0 * a.y - b.y ) / ( a.x - b.x );
}

int Pow( int x , int a ) {
    int ret = 1;
    while( a ) {
        if( a & 1 ) ret = ret * 1ll * x % P;
        x = x * 1ll * x % P , a >>= 1;
    }
    return ret;
}
int s( int x ) {
    return x * 1ll * ( x + 1 ) / 2 % P;
}

void add( int x , int y ) {
    poi cur = (poi) {x , y};
    y %= P;
    while( top >= 2 && getk( cur , p[top] ) > getk( p[top] , p[top - 1] ) ) -- top;
    int k = ( y - p[top].y % P + P ) * 1ll * Pow( x - p[top].x , P - 2 ) % P , b = ( y + P - x * 1ll * k % P ) % P;
    ans[x] = ( ans[p[top].x] + k * 1ll * ( s( x ) - s( p[top].x ) + P ) % P + b * 1ll * ( x - p[top].x ) ) % P;
    p[++ top] = cur;
}

void solve() {
    cin >> n;
    rep( i , 1 , n ) {
        scanf("%lld",A + i);
        add( i , A[i] );
    }
    rep( i , 1 , n ) printf("%lld ",ans[i] * 1ll * Pow( i , P - 2 ) % P);
}

signed main() {
//    freopen("lsj.txt","r",stdin);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}