結果
問題 | No.2065 Sum of Min |
ユーザー |
👑 |
提出日時 | 2022-08-30 18:41:07 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 128 ms / 2,000 ms |
コード長 | 5,036 bytes |
コンパイル時間 | 1,908 ms |
コンパイル使用メモリ | 197,028 KB |
最終ジャッジ日時 | 2025-02-06 23:59:51 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;#define CIN( LL , A ) LL A; cin >> A#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( int VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )#define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; return 0class Pair{public:ll m_a;int m_i;inline Pair( const ll& a = 0 , const int& i = 0 ) : m_a( a ) , m_i( i ) {}};class Order_a{public:inline bool operator()( const Pair& p0 , const Pair& p1 ) { return p0.m_a < p1.m_a; };};// 以下自分のライブラリ(https://github.com/p-adic/cpp)よりソースコードをコピーして編集している。// InitialSegmentSumで負の入力を扱うためにintをテンプレート引数にする。template <typename T , int N>class HybridBIT{private:T m_a[N];T m_fenwick[N + 1];public:inline HybridBIT();inline HybridBIT( const T ( & a )[N] );inline const T& operator[]( const int& i ) const;inline HybridBIT<T,N>& operator+=( const T ( & a )[N] );void Add( const int& i , const T& n );T InitialSegmentSum( const int& i_final );inline T IntervalSum( const int& i_start , const int& i_final );};template <typename T , int N> inline HybridBIT<T,N>::HybridBIT() : m_a() , m_fenwick() {}template <typename T , int N> inline HybridBIT<T,N>::HybridBIT( const T ( & a )[N] ) : m_a() , m_fenwick() { operator+=( a ); }template <typename T , int N> inline const T& HybridBIT<T,N>::operator[]( const int& i ) const { return m_a[i]; }template <typename T , int N> inline HybridBIT<T,N>& HybridBIT<T,N>::operator+=( const T ( & a )[N] ) { for( int i = 0 ; i < N ; i++ ){ Add( i , a[i]); } return *this; }template <typename T , int N>void HybridBIT<T,N>::Add( const int& i , const T& n ){m_a[i] += n;int j = i + 1;while( j <= N ){m_fenwick[j] += n;j += ( j & -j );}return;}template <typename T , int N>T HybridBIT<T,N>::InitialSegmentSum( const int& i_final ){T sum = 0;int j = i_final + 1;while( j > 0 ){sum += m_fenwick[j];j -= j & -j;}return sum;}template <typename T , int N> inline T HybridBIT<T,N>::IntervalSum( const int& i_start , const int& i_final ) { return InitialSegmentSum( i_final ) -InitialSegmentSum( i_start - 1 ); }#define SET_MIN_SUM( I , PREV ) \Pair& LR_sorted_i = LR_sorted[ I ]; \if( LR_sorted_prev != LR_sorted_i.m_a ){ \LR_sorted_comp_length_minus++; \FOR( j , PREV , LR_sorted_i.m_a ){ \int& A_comp_j = A_comp[j]; \InvA_comp.Add( A_comp_j , 1 ); \InvA_comp_A.Add( A_comp_j , AX_sorted_comp[A_comp_j] ); \if( A_comp_max < A_comp_j ){ \A_comp_max = A_comp_j; \} \} \LR_sorted_prev = LR_sorted_i.m_a; \} \i_half = LR_sorted_i.m_i / 2; \if( LR_sorted_i.m_i % 2 == 0 ){ \L_num[i_half] = I; \} else { \R_num[i_half] = I; \} \int& X_comp_i = X_comp[i_half]; \min_sum[ I ] += InvA_comp_A.InitialSegmentSum( X_comp_i ) + InvA_comp.IntervalSum( X_comp_i + 1 , A_comp_max ) * AX_sorted_comp[X_comp_i]; \\int main(){ios_base::sync_with_stdio( false );cin.tie( nullptr );constexpr const int N_lim = 100002;constexpr const int N_lim2 = N_lim * 2;CIN( int , N );CIN( int , Q );Pair AX[N_lim2];FOR( i , 0 , N ){Pair& Ai = AX[i];cin >> Ai.m_a;Ai.m_i = i;}Pair LR[N_lim2];int i2;int i2_plus;int Ni;FOR( i , 0 , Q ){i2 = i * 2;i2_plus = i2 + 1;Pair& Li = LR[i2];Pair& Ri = LR[i2_plus];cin >> Li.m_a;Li.m_a--;Li.m_i = i2;cin >> Ri.m_a;Ri.m_i = i2_plus;Ni = N + i;Pair& Xi = AX[Ni];cin >> Xi.m_a;Xi.m_i = Ni;}Order_a ord{};ll NQ = N + Q;sort( AX , AX + NQ , ord );Pair ( &AX_sorted )[N_lim2] = AX;int A_comp[N_lim];int X_comp[N_lim];ll AX_sorted_comp[N_lim2];ll AX_sorted_comp_prev = -1;int AX_sorted_comp_length_minus = -1;FOR( i , 0 , NQ ){Pair& AX_sorted_i = AX_sorted[i];if( AX_sorted_comp_prev != AX_sorted_i.m_a ){AX_sorted_comp_length_minus++;AX_sorted_comp[AX_sorted_comp_length_minus] = AX_sorted_i.m_a;AX_sorted_comp_prev = AX_sorted_i.m_a;}if( AX_sorted_i.m_i < N ){A_comp[AX_sorted_i.m_i] = AX_sorted_comp_length_minus;} else {X_comp[AX_sorted_i.m_i - N] = AX_sorted_comp_length_minus;}}ll Q2 = Q * 2;sort( LR , LR + Q2 , ord );Pair ( &LR_sorted )[N_lim2] = LR;int L_num[N_lim];int R_num[N_lim];int LR_sorted_prev = -1;int LR_sorted_comp_length_minus = -1;int i_half;HybridBIT<ll,N_lim2> InvA_comp{};HybridBIT<ll,N_lim2> InvA_comp_A{};ll min_sum[N_lim2] = {};int A_comp_max = -1;{SET_MIN_SUM( 0 , 0 );}FOR( i , 1 , Q2 ){SET_MIN_SUM( i , LR_sorted_prev );}FOR( i , 0 , Q ){cout << min_sum[R_num[i]] - min_sum[L_num[i]] << "\n";}return 0;}