CF500F New Year Shopping

双栈维护插入删除：

1. 右加右删。维护一个栈。

2. 右加左删。

维护两个栈，左边栈删除，右边的栈加入，左边栈为空时将右边栈中的数从顶至底加入，均摊进行 \(\mathcal O(n)\) 次操作。

3. 双端加、删

维护两个栈，用于左边插入/删除，右边插入/删除。

其中一个栈为空时将另一个栈的元素对半分到两个栈，均摊进行 \(\mathcal O(n)\) 次操作。

维护栈的前缀答案，查询时将两个栈栈顶的答案合并即可

优势在于可以在线维护信息，且比线段树分治少一个 \(\log\)。

此题即为情况 2,直接做就好了。

#include <bits/stdc++.h>
using namespace std;
#define pii pair< int , int >
#define fi first
#define sc second
#define mp make_pair
 
const int MAXN = 4e3 , MAXT = 2e4;
int n , p , q; vector< pii > b[ MAXT + 5 ] , qry[ MAXT + 5 ];
int ans[ MAXT + 5 ];
 
int top1 , top2; pii stk1[ MAXN + 5 ] , stk2[ MAXN + 5 ];
int f1[ MAXN + 5 ][ MAXN + 5 ] , f2[ MAXN + 5 ][ MAXN + 5 ];
/*
左端删除,右端插入
*/
inline void Insert2( pii v ) {
    stk2[ ++ top2 ] = v;
    for( int i = 0 ; i <= MAXN ; i ++ ) {
        f2[ top2 ][ i ] = f2[ top2 - 1 ][ i ];
        if( i >= v.fi ) f2[ top2 ][ i ] = max( f2[ top2 ][ i ] , f2[ top2 - 1 ][ i - v.fi ] + v.sc );
    }
}
inline void Insert1( pii v ) {
    stk1[ ++ top1 ] = v;
    for( int i = 0 ; i <= MAXN ; i ++ ) {
        f1[ top1 ][ i ] = f1[ top1 - 1 ][ i ];
        if( i >= v.fi ) f1[ top1 ][ i ] = max( f1[ top1 ][ i ] , f1[ top1 - 1 ][ i - v.fi ] + v.sc );
    }
}
inline void Delete( ) {
    if( !top1 ) {
        while( top2 ) Insert1( stk2[ top2 -- ] );
    } top1 --;
}
inline int Query( int v ) {
    int ans = 0;
    for( int i = 0 ; i <= v ; i ++ ) ans = max( ans , f1[ top1 ][ i ] + f2[ top2 ][ v - i ] );
    return ans;
}
 
int cnt[ MAXT + 5 ];
int main( ) {
    scanf("%d %d",&n,&p);
    for( int i = 1 , v , w , t ; i <= n ; i ++ ) scanf("%d %d %d",&v,&w,&t) , b[ t ].push_back( mp( v , w ) );
    scanf("%d",&q);
    for( int i = 1 , a , b ; i <= q ; i ++ ) scanf("%d %d",&a,&b) , qry[ a ].push_back( mp( b , i ) );
    
    for( int i = 1 ; i <= MAXT ; i ++ ) {
        for( pii v : b[ i ] ) Insert2( v ) , cnt[ i + p ] ++;
        for( int j = 1 ; j <= cnt[ i ] ; j ++ ) Delete();
        for( pii v : qry[ i ] ) ans[ v.sc ] = Query( v.fi );
    }
    for( int i = 1 ; i <= q ; i ++ ) printf("%d\n", ans[ i ] );
    return 0;
}