PROBLEM LINK:
Author: valiant_vidit
Tester: hellb0y_suru
Editorialist: valiant_vidit
DIFFICULTY:
EASY-MEDIUM
PROBLEM:
Given an array arr consisting of not necessarily distinct numbers and 2 types of queries:
- to update an element at a given index
- to find greater element nearest to given index in its right such that it has not been appeared in the left of given index( i ).
Prerequisites:
- knowledge of segment tree and its applications.
- A little amount of brain to be applied while solving or understanding the editorial
Hint:
1 Point
A simple brute force logic will satisfy the given constraints.
99 Points
Try to construct a logic by using segment tree and with the help of some basic container like set.
QUICK EXPLANATION:
It is a kind of a good implementation of segment tree in a given range to find next greater element where the range will from [i , n-1], where we can construct a segment tree of max values and can traverse through the left branch of segment tree to find the greater element and if not present we can check for right branch at that time and then continue to explore rest of the left branches. To take care that next greater element should not repeat before i , we have to make a record of those index and then to build segment tree after these records to ensure correct answer.
EXPLANATION:
First of all I would like to share an approach for finding greater element nearest to given index in right direction (here for some time lets ignore the condition that our answer should not repeat before i).
Now , lets say the array on which we are doing segment tree operations be Arr (initial array)for this we should construct a binary tree of max numbers on this array.For finding next greater element we should start exploring left branches of tree (as they are nearest to Arr[i]) by checking the condition that the respective max element is greater than Arr[i] or not, if not at that time we will check our right branch of tree and as soon as our condition ( the respective max element is greater than given element or not) satisfies we will continue to explore our rest of the left branches till the leaf node occurs.
By this approach we can easily get the greater element(>Arr[i]) nearest to i in [i , n-1] , but now we are not ensured that our answer is correct or not ( for this we have to ensure that it should be not occur in [0 , i]).
For this lets make a new array crr where crr[j]=arr[j] if arr[j] != arr[k] where k is in the range [0,j-1] for every j in the range [0,i-1] ( because only unique elements will contribute in crr to avoid duplicacy of elements).
By doing this ,we should replace crr with arr and perform the rest same segment operations to find obtain our correct answer.
Now all concern is about update query. We have to manage update query in such a way that crr should be updated and then by this we can perform some update operations on segment tree.
For this we have to maintain a record of indexes of all same type of elements (which I have done by a map<long,set<ll> in my solution in cpp). where mp[arr[j]] will contain all indexes h such that arr[h]=arr[j] for h in the range [0,n-1].
You will be wondering why am I doing this ,this will help us in our update query.
Now see during an update ( lets say for arr[b] =c) here we have to first find arr[b] and to check whether b was the first index where arr[b] was appeared ,if it is then crr[b]=-1 and to find next occurence of arr[b] (lets say b'), then crr[b]=arr[b].
After this we will update arr[b] to c and insert b to mp[arr[b]] and now again check whether b was the first index where arr[b] was appeared ,if it is then crr[b]=arr[b] and to find next occurence of arr[b] (lets say b'), then crr[b]=-1.
By this we can see that at max 4 updations are to be done crr so,for this we can call our update function of segment tree at max 4 times in a single query .
Hence by all this we can ensure that our answer will always be correct.As the complexity of our code is O(nlogn+4logn+logn) = O(nlogn) approximately, which will satisfy the required constraints.
Sorry for the long editorial,but I hope the solution had cleared your doubts , but if there is any confusion or query regarding the editorial or approach feel free to ping me 
!!
SOLUTIONS:
Setter's Solution
/*author : vidit shukla
(valiant_vidit)*/
#include <bits/stdc++.h>
#define ll long long int
#define bhaago ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define loop(a, b, i) for (ll i = a; i < b; i++)
#define loop1(a, b, i) for (ll i = a; i > b; i--)
#define endl '\n'
using namespace std;
void build(ll tree[], ll brr[], ll left, ll right, ll index)
{
if (left == right)
{
tree[index] = brr[left];
return;
}
ll mid = (left + right) / 2;
build(tree, brr, left, mid, 2 * index + 1);
build(tree, brr, mid + 1, right, 2 * index + 2);
tree[index] = max(tree[2 * index + 1], tree[2 * index + 2]);
return;
}
////////////
ll update(ll tree[], ll left, ll right, ll rtindex, ll index, ll value)
{
if (index < left || index > right)
return tree[rtindex];
if (left == right)
{
tree[rtindex] = value;
return tree[rtindex];
}
ll mid = (left + right) / 2;
return tree[rtindex] = max(update(tree, left, mid, 2 * rtindex + 1, index, value),
update(tree, mid + 1, right, 2 * rtindex + 2, index, value));
}
ll ans(ll tree[], ll brr[], ll qleft, ll qright, ll left, ll right, ll index, ll value)
{
if (left >= qleft && right <= qright)
{
if (tree[index] > value)
{
if (left == right)
return tree[index];
ll mid = (left + right) / 2;
ll a1 = ans(tree, brr, qleft, qright, left, mid, 2 * index + 1, value);
if (a1 == -1)
return ans(tree, brr, qleft, qright, mid + 1, right, 2 * index + 2, value);
else
return a1;
}
else
return -1;
}
if (qright < left || qleft > right)
return -1;
ll mid = (left + right) / 2;
ll a1 = ans(tree, brr, qleft, qright, left, mid, 2 * index + 1, value);
if (a1 == -1)
return ans(tree, brr, qleft, qright, mid + 1, right, 2 * index + 2, value);
else
return a1;
}
//////////////////////////////////////////////////////////////
int main()
{
bhaago;
// freopen("@input.txt", "r", stdin);
// freopen("@outtt.txt", "w", stdout);
ll tc = 1;
cin >> tc;
while (tc--)
{
ll n, q;
cin >> n >> q;
ll arr[n];
map<ll, set<ll>> mp;
loop(0, n, i)
{
cin >> arr[i];
mp[arr[i]].insert(i);
}
ll brr[n], crr[n];
loop(0, n, i) brr[i] = -1;
loop(0, n, i)
{
auto it = mp[arr[i]].find(i);
if (it == mp[arr[i]].begin())
{
crr[i] = arr[(*it)];
}
else
crr[i] = -1;
}
ll sz = (ll)powl(2, (ll)((ceil)(log2(n))));
sz = 2 * sz - 1;
ll tree[sz];
loop(0, sz, i) tree[i] = -1;
build(tree, crr, 0, n - 1, 0);
loop(0, q, i)
{
ll a, b, c;
cin >> a;
if (a == 0)
{
cin >> b >> c; //to update arr[b]=c.
auto itx11 = mp[arr[b]].find(b);
auto itxu = itx11;
auto itxl = itx11;
if (itx11 == mp[arr[b]].begin())
{
crr[b] = -1;
update(tree, 0, n - 1, 0, b, crr[b]);
if ((++itx11) != mp[arr[b]].end())
{
crr[*(itx11)] = arr[*(itx11)];
update(tree, 0, n - 1, 0, *(itx11), crr[*(itx11)]);
}
}
mp[arr[b]].erase(mp[arr[b]].find(b)); //erase
arr[b] = c;
mp[arr[b]].insert(b); //insert
itx11 = mp[arr[b]].find(b);
if (itx11 == mp[arr[b]].begin())
{
crr[*(itx11)] = arr[*(itx11)];
update(tree, 0, n - 1, 0, *(itx11), crr[*(itx11)]);
if ((++itx11) != mp[arr[b]].end())
{
crr[*(itx11)] = -1;
update(tree, 0, n - 1, 0, *(itx11), crr[*(itx11)]);
}
}
} //update....
else
{
cin >> b; //index of number after which next greater to be find.
cout << ans(tree, crr, b, n - 1, 0, n - 1, 0, arr[b]) << endl;
}
}
}
// your code goes here
return 0;
}
Tester's Solution
// Suryansh Kumar
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long int
#define MOD 1000000007
#define oo 1000000000000000000
#define forr(i, n) for (ll i = 0; i < n; i++)
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
#define all(x) x.begin(), x.end()
#define eb emplace_back
#define mem(a, v) memset(a, v, sizeof(a))
#define pb push_back
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
ll valueOfIndex(ordered_set &s, ll i) { return *(s.find_by_order(i)); }
ll indexOfValue(ordered_set &s, ll x) { return s.order_of_key(x); }
ll add(ll a, ll b, ll p = MOD)
{
a %= p;
b %= p;
return (a + b + p) % p;
}
ll mul(ll a, ll b, ll p = MOD)
{
a %= p;
b %= p;
return (a * b + p) % p;
} // __int128
ll power(ll x, ll n, ll p = MOD)
{
if (x == 0)
return 0;
if (n == 0 || x == 1)
return 1LL;
ll r = (power(x, n / 2, p)) % p;
if (n & 1)
return mul(mul(r, r, p), x, p);
else
return mul(r, r, p);
}
ll inv(ll x) { return power(x, MOD - 2); }
struct SegTree
{
vector<int> v;
int sz;
SegTree(int n)
{
sz = n;
v.resize(4 * n + 20);
}
void update(int id, int s, int e, int pos, int val)
{
if (s > e)
return;
else if (s == e)
{
v[id] = val;
return;
}
else
{
int m = (s + e) / 2;
if (pos <= m)
update(2 * id, s, m, pos, val);
else
update(2 * id + 1, m + 1, e, pos, val);
v[id] = max(v[2 * id], v[2 * id + 1]);
return;
}
}
int query(int id, int s, int e, int l, int r, int val)
{
if (s > e || r < s || l > e)
return -1;
else if (s == e)
{
if (v[id] <= val)
return -1;
else
return v[id];
}
else if (l <= s && e <= r)
{
if (v[id] <= val)
return -1;
else
{
while (s != e)
{
int mid = (s + e) / 2;
if (v[2 * id] > val)
{
e = mid;
id = 2 * id;
}
else
{
s = mid + 1;
id = 2 * id + 1;
}
}
return v[id];
}
}
int m = (s + e) / 2;
int left = query(2 * id, s, m, l, r, val);
if (left > val)
return left;
else
return query(2 * id + 1, m + 1, e, l, r, val);
}
void update(int pos, int val)
{
update(1, 1, sz, pos, val);
return;
}
int query(int i, int val)
{
return query(1, 1, sz, i + 1, sz, val);
}
};
void __sol()
{
int n, q;
cin >> n >> q;
int a[n + 10];
map<int, set<int>> m;
forr(i, n) cin >> a[i + 1], m[a[i + 1]].insert(i + 1);
SegTree t(n);
for (auto &i : m)
t.update(*(i.second.begin()), i.first);
while (q--)
{
int type;
cin >> type;
if (type)
{
int i;
cin >> i;
i++;
cout << t.query(i, a[i]) << "\n";
}
else
{
int i, val;
cin >> i >> val;
i++;
if (a[i] == val)
continue;
int last = a[i];
if (*(m[last].begin()) == i)
{
m[last].erase(m[last].begin());
if (m[last].size() > 0)
t.update(*(m[last].begin()), last);
else
m.erase(last);
}
else
m[last].erase(i);
if (m.count(val) == 0)
t.update(i, val);
else
{
if (*(m[val].begin()) > i)
{
t.update(*(m[val].begin()), -1);
t.update(i, val);
}
else
t.update(i, -1);
}
m[val].insert(i);
a[i] = val;
}
}
return;
}
int main()
{
fastio
ll tc = 1;
cin >> tc;
while (tc--)
__sol();
return 0;
}
