[BZOJ1122][POI2008]账本BBB 单调队列+后缀和

Description

一个长度为n的记账单，+表示存￥1，-表示取￥1。现在发现记账单有问题。一开始本来已经存了￥p，并且知道最后账户上还有￥q。你要把记账单修改正确，使得 1：账户永远不会出现负数； 2：最后账户上还有￥q。你有2种操作： 1：对某一位取反，耗时x； 2：把最后一位移到第一位，耗时y。

Input

The first line contains 5 integers n, p, q, x and y (1  n  1000000, 0  p;q  1000000, 1  x;y  1000), separated by single spaces and denoting respectively: the number of transactions done by Byteasar, initial and final account balance and the number of seconds needed to perform a single turn (change of sign) and move of transaction to the beginning. The second line contains a sequence of n signs (each a plus or a minus), with no spaces in-between. 1 ≤ n ≤ 1000000, 0 ≤ p ,q ≤ 1000000, 1 ≤x,y ≤ 1000)

Output

修改消耗的时间

Sample Input

9 2 3 2 1
---++++++

Sample Output

3

Solution

做法：单调队列+后缀和

好难啊这题...

两种操作，我们可以枚举第二种操作的次数，然后算出第一种操作的情况

枚举操作2的话其实就是断链成环，然后枚举起点

对于操作1的求解，我们可以搞个单调队列来弄一下

首先维护一个后缀和，然后用单调队列处理出对于每个起点账本最高能达到多少

然后就分类讨论一下就可以了

如果序列和再加上$p$大于$q$的话就对$+$取反

否则就对后面的$-$取反

#include <bits/stdc++.h>

using namespace std ;

#define ll long long
const int N = 2e6 + 10 ;

ll n , p , q , x , y ;
char s[ N ] ;
ll a[ N ] , b[ N ]; 
ll sum[ N ] ;
deque <int> Q ; 

int main() {
    scanf( "%lld%lld%lld%lld%lld" , &n , &p , &q , &x , &y ) ;
    scanf( "%s" , s + 1 ) ;
    for( int i = 1 ; i <= n ; i ++ ) {
        a[ i ] = s[ i ] == '+' ? 1 : -1 ;
        a[ i + n ] = a[ i ] ;
    }
    for( int i = n * 2 ; i ; i -- ) {
        sum[ i ] = sum[ i + 1 ] + a[ i ] ;
    }
    for( int i = n * 2 ; i ; i -- ) {
        if( i <= n ) b[ i ] = sum[ i ] - sum[ Q.back() ] ;
        while( !Q.empty() && sum[ Q.front() ] <= sum[ i ] ) Q.pop_front() ;
        Q.push_front( i ) ;
        while( Q.back() >= i + n ) Q.pop_back() ;
    }
    ll ans = 0x7fffffff ;
    for( int i = 1 ; i <= n ; i ++ ) {
        ll now =  y * ( ( n - i + 1 ) % n ) ;
        if( p + sum[ n + 1 ] >= q ) now += ( p + sum[ n + 1 ] - q ) / 2 * x ;
        else {
            now += ( q- p - sum[ n + 1 ] ) / 2 * x ;
            b[ i ] += ( q - p - sum[ n + 1 ] ) ;
        }
        if( p + b[ i ] < 0 ) now -= ( p + b[ i ] - 1 ) / 2 * 2  * x ;
        ans = min( ans , now ) ;
    }
    printf( "%lld
" , ans ) ;
}