editorial of Bangladesh 2.0 contest.

solution 1: (using priority queue)

make a priority queue(min heap) of pairs {value,index}. So the top element of the priority queue will always contain the minimum. In each query we have to pop the top element and print the index, then replace the value with X and push it again into the priority queue.

Time complexity : O(Q*LogN)
code :

	
#include <bits/stdc++.h>
using namespace std;
#define SC scanf
#define PF printf
#define ull unsigned long long
#define ld long double
#define F first
#define S second
#define pb push_back
#define sort_a(a) sort(a.begin(),a.end());
#define sort_d(a) sort(a.rbegin(),a.rend());
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define rev(s) reverse(s.begin(),s.end())
#define P(ok) cout << (ok ? "YES\n": "NO\n")
#define Heart ios_base :: sync_with_stdio(false); cin.tie(NULL);
#define ll long long
typedef pair< ll , ll> PII;
void solve()
{
int n , a , q , val; cin >> n ;
priority_queue < pair < int , int > , vector < pair < int , int> > , greater < pair < int , int > > > pq ;
for(int i = 1 ; i <= n ; i++){
cin >> a ;
pq.push({a , i}) ;
}
cin >> q ;
while(q--){
cin >> val ;
auto Ans = pq.top() ;
cout << Ans.S << endl ;
pq.pop() ;
pq.push({val , Ans.S}) ;
}
}
int main()
{
Heart
// READ("input.txt") ;
// WRITE("output.txt") ;
int t ; t = 1 ; while(t--) solve() ;
}

solution 2: (using segment tree)

Build a segment tree with each node containing a pair of {value,index}. In each query we have to check the range (0,N-1) to find the minimum and update the index of that minimum with value X.

time complexity : O(Q*LogN)
code :

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

pair<int,int> sg[400005];
int a[100005];

void build(int node,int start,int end)
{
    if(start == end)
    {
        sg[node] = {a[start],start};
        return;
    }
    int mid = (start + end) / 2;
    build(node*2,start,mid);
    build(node*2+1,mid+1,end);
    if(sg[node*2] <sg[node*2+1]) sg[node] = sg[node*2];
    else sg[node] = sg[node*2+1];
}

void update(int node,int start,int end,int ind,int val)
{
    if(start == end)
    {
        sg[node] = {val,start};
        return;
    }
    int mid = (start + end)/2;
    if(ind <= mid) update(node*2,start,mid,ind,val);
    else update(node*2+1,mid+1,end,ind,val);
    if(sg[node*2] <sg[node*2+1]) sg[node] = sg[node*2];
    else sg[node] = sg[node*2+1];
}


int main()
{
    int n; cin >> n;
    for(int i=0;i<n;i++) cin >> a[i];
    build(1,0,n-1);
    int q; cin >>q;
    while(q--)
    {
        int x ; cin >> x;
        pair<int,int> p = sg[1];
        cout << p.second+1 << endl;
        update(1,0,n-1,p.second,x);
    }
}

#include <bits/stdc++.h>
using namespace std;
#define SC scanf
#define PF printf
#define ull unsigned long long
#define ld long double
#define F first
#define S second
#define pb push_back
#define sort_a(a) sort(a.begin(),a.end());
#define sort_d(a) sort(a.rbegin(),a.rend());
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define rev(s) reverse(s.begin(),s.end())
#define P(ok) cout << (ok ? "YES\n": "NO\n")
#define Heart ios_base :: sync_with_stdio(false); cin.tie(NULL);
#define ll long long
typedef pair< ll , ll> PII;
void solve()
{
int n , a , q , val; cin >> n ;
priority_queue < pair < int , int > , vector < pair < int , int> > , greater < pair < int , int > > > pq ;
for(int i = 1 ; i <= n ; i++){
cin >> a ;
pq.push({a , i}) ;
}
cin >> q ;
while(q--){
cin >> val ;
auto Ans = pq.top() ;
cout << Ans.S << endl ;
pq.pop() ;
pq.push({val , Ans.S}) ;
}
}
int main()
{
Heart
// READ("input.txt") ;
// WRITE("output.txt") ;
int t ; t = 1 ; while(t--) solve() ;
}