Prelude

题目链接：萌萌哒传送门

---

Solution

如果完全离线的话，可以直接用时间线段树分治来做，复杂度\(O(qv \log q)\)。

现在在线了怎么办呢？

这其实是个假在线，因为每个物品的删除时间已经给你了，所以还是直接用时间线段树分治来做。

其实我是重点想谈一下复杂度的，\(O(n^{2} \log n)\)的复杂度居然都可以出到\(15000\)，而且居然还跑的飞快？

---

Code

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;typedef unsigned int uint;typedef unsigned long long ull;typedef long double ldouble;typedef pair
         
           pii;typedef vector
          
           ::iterator viter;const int MAXN = 15010;const int LOGN = 17;const int INF = 0x3f3f3f3f;int _w;inline void bmin( int &a, int b ) { a = b < a ? b : a;}inline void bmax( int &a, int b ) { a = b > a ? b : a;}int q, maxv, T, lastans;struct Knapsack { int f[MAXN]; void init() { for( int i = 0; i <= maxv; ++i ) f[i] = -INF; f[0] = 0; } void insert( int v, int w ) { for( int i = maxv-v; i >= 0; --i ) bmax( f[i+v], f[i]+w ); } const int &operator[]( int i ) const { return f[i]; } int &operator[]( int i ) { return f[i]; }};vector
           
             item[MAXN<<2];Knapsack f[LOGN];int qv[MAXN];pii ins;int ql, qr;void insert( int o, int L, int R ) { if( L >= ql && R <= qr ) { item[o].push_back(ins); } else { int M = (L+R)>>1, lc = o<<1, rc = lc|1; if( ql <= M ) insert(lc, L, M); if( qr > M ) insert(rc, M+1, R); }}void query( int i, int d ) { if( qv[i] != -1 ) { int v = qv[i]; if( f[d][v] < 0 ) { puts("0 0"); lastans = 0; } else { printf( "1 %d\n", f[d][v] ); lastans = T * (f[d][v] ^ 1); } } if( i == q ) return; int op; _w = scanf( "%d", &op ); if( op == 1 ) { int v, w, e; _w = scanf( "%d%d%d", &v, &w, &e ); v -= lastans, w -= lastans, e -= lastans; ins = pii(v, w), ql = i+1, qr = e; insert(1, 0, q); } else { _w = scanf( "%d", qv+i+1 ); qv[i+1] -= lastans; }}void solve( int o, int L, int R, int d ) { for( viter it = item[o].begin(); it != item[o].end(); ++it ) f[d].insert(it->first, it->second); if( L == R ) { query(L, d); } else { int M = (L+R)>>1, lc = o<<1, rc = lc|1; f[d+1] = f[d]; solve(lc, L, M, d+1); f[d+1] = f[d]; solve(rc, M+1, R, d+1); }}int main() { _w = scanf( "%d%d%d", &q, &maxv, &T ); f[0].init(); memset(qv, -1, sizeof qv); solve(1, 0, q, 0); return 0;}