双栈维护插入删除:
-
右加右删。维护每个前缀的答案即可
-
右加左删。
维护两个栈,左边栈删除,右边的栈加入,左边栈为空时将右边栈中的数从顶至底加入。维护栈的前缀答案。
查询时将两个栈的答案合并即可
- 双端加、删
维护两个栈,用于左边插入/删除,右边插入/删除。
其中一个栈为空时将另一个栈的元素对半分到两个栈,均摊进行 \(\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;
}
原文地址:http://www.cnblogs.com/chihik/p/CF500F.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性