CFR 799 C. Fountains ( Segment Tree )

Problem - C - Codeforces

題意：
有 N 樣物品，用價格和價值描述。一樣物品可能是要用 C 類貨幣購買，也有可能是要用 D 類貨幣購買。選兩個相異的物品購買，使得價值總和最大。輸出價值總和。

制約：
The first line contains three integers n, c and d (2 ≤ n ≤ 100 000, 0 ≤ c, d ≤ 100 000) — the number of fountains, the number of coins and diamonds Arkady has.
The next n lines describe fountains. Each of these lines contain two integers bi and pi (1 ≤ bi, pi ≤ 100 000) — the beauty and the cost of the i-th fountain, and then a letter "C" or "D", describing in which type of money is the cost of fountain i: in coins or in diamonds, respectively.

解法：
分開討論 2C, 2D, 1C and 1D 的情況。考慮用 max 線段樹，下標是價格，更新的是價值。這時候先迴避兩個價格相同時的處理，在後面額外用優先佇列處理。

時間 / 空間複雜度：
O( N lg N )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = int( 1e5 );

int N, C, D;
int B[ MAXN ], P[ MAXN ];
string T[ MAXN ];

int cmaxv[ MAXN << 3 ];
int dmaxv[ MAXN << 3 ];

void modify( int *maxv, int k, int v, int lb = 0, int rb = MAXN + 1, int t = 1 ) {
  if( lb + 1 == rb ) {
    maxv[ t ] = max( maxv[ t ], v );
    return;
  }
  int mid = lb + rb >> 1;
  if( k < mid ) {
    modify( maxv, k, v, lb, mid, t << 1 );
  } else {
    modify( maxv, k, v, mid, rb, t << 1 | 1 );
  }
  maxv[ t ] = max( maxv[ t << 1 ], maxv[ t << 1 | 1 ] );
}

int query( int *maxv, int ql, int qr, int lb = 0, int rb = MAXN + 1, int t = 1 ) {
  if( qr <= lb or rb <= ql ) return 0;
  if( ql <= lb and rb <= qr ) return maxv[ t ];
  int mid = lb + rb >> 1;
  return max( query( maxv, ql, qr, lb, mid, t << 1 ), query( maxv, ql, qr, mid, rb, t << 1 | 1 ) );
}

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> C >> D;
  for( int i = 0; i < N; ++i ) {
    cin >> B[ i ] >> P[ i ] >> T[ i ];
  }
  for( int i = 0; i < N; ++i ) {
    if( T[ i ] == "C" ) {
      modify( cmaxv, P[ i ], B[ i ] );
    } else {
      modify( dmaxv, P[ i ], B[ i ] );
    }
  }
  int ans = 0;
  { // 1 c 1 d
    for( int i = 0; i < N; ++i ) {
      if( C < P[ i ] ) continue;
      if( T[ i ] == "C" ) {
        int maxd = query( dmaxv, 0, D + 1 );
        if( maxd > 0 ) {
          ans = max( ans, B[ i ] + maxd );
        }
      }
    }
  }
  { // 2 c
    map< int, priority_queue< int > > mpq;
    for( int i = 0; i < N; ++i ) {
      if( T[ i ] == "C" ) {
        mpq[ P[ i ] ].emplace( B[ i ] );
        int f = C - P[ i ];
        int r = 0;
        if( f < P[ i ] ) {
          r = query( cmaxv, 0, f + 1 );
        } else {
          r = max( query( cmaxv, 0, P[ i ] ), query( cmaxv, P[ i ] + 1, f + 1 ) );
        }
        if( r > 0 ) {
          ans = max( ans, B[ i ] + r );
        }
      }
    }
    for( int i = 1; i * 2 <= C; ++i ) {
      if( mpq[ i ].size() >= 2 ) {
        int a = mpq[ i ].top();
        mpq[ i ].pop();
        int b = mpq[ i ].top();
        mpq[ i ].pop();
        ans = max( ans, a + b );
      }
    }
  }
  { // 2 d
    map< int, priority_queue< int > > mpq;
    for( int i = 0; i < N; ++i ) {
      if( T[ i ] == "D" ) {
        mpq[ P[ i ] ].emplace( B[ i ] );
        int f = D - P[ i ];
        int r = 0;
        if( f < P[ i ] ) {
          r = query( dmaxv, 0, f + 1 );
        } else {
          r = max( query( dmaxv, 0, P[ i ] ), query( dmaxv, P[ i ] + 1, f + 1 ) );
        }
        if( r > 0 ) {
          ans = max( ans, B[ i ] + r );
        }
      }
    }
    for( int i = 1; i * 2 <= D; ++i ) {
      if( mpq[ i ].size() >= 2 ) {
        int a = mpq[ i ].top();
        mpq[ i ].pop();
        int b = mpq[ i ].top();
        mpq[ i ].pop();
        ans = max( ans, a + b );
      }
    }
  }
  cout << ans << endl;
  return 0;
}