#include<bits/stdc++.h> using namespace std; #define mod 10000000009; int baza; long long pot[1<<20]; struct Node { long long war; int id; Node *left, *right; Node() : war(0), left(nullptr), right(nullptr) {} void add( int where, int ile, int pocz=0, int kon=baza ) { if( pocz == kon-1 ) { war = ile; return; } int sr = (pocz+kon)/2; if( where < sr ) { Node * pom = new Node; if( left != nullptr ) { *pom = *left; } left = pom; left->add( where, ile, pocz, sr ); } else { Node * pom = new Node; if( right != nullptr ) { *pom = *right; } right = pom; right->add( where, ile, sr, kon ); } war = left->war*pot[sr-pocz]%mod; if( right != nullptr ) { war = (war+right->war)%mod; } } bool operator < ( Node other ) const { const Node *a = this, *b = &other; int x = baza; while( x>1 ) { x/=2; if( a->left->war == b->left->war ) { a = a->right; b = b->right; } else { a = a->left; b = b->left; } } return a->war < b->war; } }; int32_t main() { ios_base::sync_with_stdio( 0 ); cin.tie( 0 ); int n, m; cin >> n >> m; baza = 1; while( baza <= n ) baza*=2; pot[0] = 1; for( int i=1; i<=baza; i++ ) { pot[i] = pot[i-1]*1000000007%mod; } vector<Node> v; v.push_back( {} ); for( int a, i=0; i<n; i++ ) { cin >> a; v.back().add( i, a ); } v.back().add( n, 1 ); v.back().id = 1; for( int a, b, i=2; i<=m; i++ ) { cin >> a >> b; v.push_back( v.back() ); v.back().add( n, i ); v.back().add( a-1, b ); v.back().id = i; } sort( v.begin(), v.end() ); for( auto & i : v ) { cout << i.id << " "; } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | #include<bits/stdc++.h> using namespace std; #define mod 10000000009; int baza; long long pot[1<<20]; struct Node { long long war; int id; Node *left, *right; Node() : war(0), left(nullptr), right(nullptr) {} void add( int where, int ile, int pocz=0, int kon=baza ) { if( pocz == kon-1 ) { war = ile; return; } int sr = (pocz+kon)/2; if( where < sr ) { Node * pom = new Node; if( left != nullptr ) { *pom = *left; } left = pom; left->add( where, ile, pocz, sr ); } else { Node * pom = new Node; if( right != nullptr ) { *pom = *right; } right = pom; right->add( where, ile, sr, kon ); } war = left->war*pot[sr-pocz]%mod; if( right != nullptr ) { war = (war+right->war)%mod; } } bool operator < ( Node other ) const { const Node *a = this, *b = &other; int x = baza; while( x>1 ) { x/=2; if( a->left->war == b->left->war ) { a = a->right; b = b->right; } else { a = a->left; b = b->left; } } return a->war < b->war; } }; int32_t main() { ios_base::sync_with_stdio( 0 ); cin.tie( 0 ); int n, m; cin >> n >> m; baza = 1; while( baza <= n ) baza*=2; pot[0] = 1; for( int i=1; i<=baza; i++ ) { pot[i] = pot[i-1]*1000000007%mod; } vector<Node> v; v.push_back( {} ); for( int a, i=0; i<n; i++ ) { cin >> a; v.back().add( i, a ); } v.back().add( n, 1 ); v.back().id = 1; for( int a, b, i=2; i<=m; i++ ) { cin >> a >> b; v.push_back( v.back() ); v.back().add( n, i ); v.back().add( a-1, b ); v.back().id = i; } sort( v.begin(), v.end() ); for( auto & i : v ) { cout << i.id << " "; } return 0; } |