PROBLEM LINK:
Setter: Mladen Puzic
Tester: Michael Nematollahi
Editorialist: Taranpreet Singh
DIFFICULTY:
PREREQUISITES:
Treap plus Binary Search, or Union-Disjoint Sets using maps with path compression.
PROBLEM:
There’s an array A of length N \leq 10^{18} such that A_i = i. We are required to handle updates A_p = 0 for some position p and answer queries finding the maximum value in range [L, R]. Queries are online, so we don’t get next update or query until we answer the current one.
EXPLANATION
For this problem, I shall describe two solutions, one used by the tester and one mine. Setter uses the third method similar to keeping intervals idea described here.
In all solutions, common observation is that maximum of range [L, R] for some query is the rightmost value in range [L, R] which is not yet updated to 0, or 0 if all positions in range [L, R] are assigned to 0. We all seek to find this value, in our own ways.
Tester’s Solution
Suppose you maintain N disjoint sets, one for each position, and for the update on position p, assign p-1 as the parent of set on position p.
By this, we always know that root of the disjoint set is always a position which is not yet updated to zero, and secondly, since each position is assigned parent the position to its immediate left, the root of the disjoint set containing position p shall be the rightmost position which is not updated to 0. Hence, if the root of the disjoint set containing R for a query [L, R] is less than L, all positions in the range are updated to zero and thus a maximum is zero. Otherwise, The root of the disjoint set containing R is the rightmost position not yet updated to zero, which is the required answer we are looking for.
Since N is way too large, we cannot store sets in the array, but we can use maps. See tester’s solution for implementation.
Editorialist’s Solution
Let us maintain a mysterious data structure which is capable of following operations in O(log(size)).
- Insert a value.
- Determine whether the value x is present.
- Count the number of values present in set smaller than or equal to x.
Suppose at each update, we insert the position into this DS, if not already present. Then, at each query [L, R], If all positions in [L, R] are assigned to zero, then the number of elements in range [L, R] in DS = Number of elements less than or equal to R less the number of elements smaller than or equal to L-1 which should be R-L+1. The answer, in this case, is zero.
Otherwise, Let us find the rightmost position p such that Number of elements in the range [p, R] is less than R-p+1. We can see that since all positions q > p satisfies the condition that the number of elements in the range [q, R] = R-q+1, p is the largest value \leq R which is not present in DS which is the required answer for our query.
This mysterious data structure can be any Balanced Binary Search Tree such as AVL-Tree, Treap, Red-black tree or so on. Editorialist solution is based on Treap which you may refer below.
Bonus: There are updates of the second kind updating A_p = p for position p.
TIME COMPLEXITY
For tester’s solution, the time complexity is O(Q*α(Q)) per test case. (Or O(Q*α(Q)*log(Q)) if we consider ordered maps.
For editorialist’s solution, the time complexity is O(Q*log(Q)*log(N)) per test case.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
#define STIZE(x) fprintf(stderr, "STIZE%d\n", x);
#define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x);
#define NL(x) printf("%c", " \n"[(x)]);
#define lld long long
#define pll pair<lld,lld>
#define pb push_back
#define fi first
#define se second
#define mid (l+r)/2
#define endl '\n'
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 2000000000000000000LL
#define INF 1000000000
#define EPS 1e-9
using namespace std;
set<pll> S;
set<pll>::iterator query(lld X) {
auto p = S.lower_bound({X, LINF}); p--; ///last interval with l smaller than X
return p;
}
void update(lld X) {
auto q = query(X);
auto p = q; q++;
pll in1 = *p, in2 = *q, rez;
if(X <= in1.se) return; ///if X is already in some interval
if(X > in1.se+1 && X < in2.fi-1) rez = {X, X}; ///if X doesn't touch any other interval
else if(X == in1.se+1 && X != in2.fi-1) rez = {in1.fi, X}, S.erase(p); ///if it touches only left interval
else if(X != in1.se+1 && X == in2.fi-1) rez = {X, in2.se}, S.erase(q); ///if it touches only right interval
else if(X == in1.se+1 && X == in2.fi-1) rez = {in1.fi, in2.se}, S.erase(p), S.erase(q); ///if it touches both intervals
S.insert(rez);
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cerr.tie(0);
int T; cin >> T;
while(T--) {
S.clear();
lld N, s = 0; int Q; cin >> N >> Q;
S.insert({0, 0}); S.insert({LINF, LINF}); /// so we can always decrement in query and increment in update
while(Q--) {
int type; cin >> type;
if(type == 1) {
lld x, t; cin >> t;
x = t + s;
update(x);
} else {
lld p, q, l, r, rez; cin >> p >> q;
l = p+s; r = q+s;
pll rezz = *query(r);
if(rezz.se < r) rez = r; /// if r is not 0
else if(rezz.fi > l) rez = rezz.fi-1; /// largest element not zero
else rez = 0; /// if whole subarray is 0
s += rez;
if(s >= N) s %= N;
cout << rez << endl;
}
}
}
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
map<ll, ll> par;
ll getPar(ll v){
if (!par.count(v))
par[v] = v;
return par[v]==v? v: par[v]=getPar(par[v]);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int te; cin >> te;
while (te--){
par.clear();
ll sm = 0;
ll n; int q; cin >> n >> q;
while (q--){
int type; cin >> type;
if (type == 1){
ll x; cin >> x; x += sm;
par[x] = x-1;
}
else{
ll l, r; cin >> l >> r; l += sm, r += sm;
ll p = getPar(r);
if (p < l)
cout << "0\n";
else {
cout << p << "\n";
sm = (sm + p)%n;
}
}
}
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class BURARRAY{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
Treap root = null;
long n = nl();
long ans = 0, s = 0;
for(int qc = 1, qq = ni(); qc <= qq; qc++){
int ty = ni();
if(ty == 1){
long x = nl()+s;
if(!contains(root, x))root = insert(root, x);
}else{
long l = nl()+s, r = nl()+s;
long small = smaller(root, l-1);
long last = smaller(root, r);
if(!contains(root, r))ans = r;
else if(r-l+1 == last-small)ans = 0;
else{
long lo = l, hi = r;
while(lo+1<hi){
long mid = lo+(hi-lo)/2;
if(last-smaller(root, mid-1) == r-mid+1)hi = mid;
else lo = mid;
}
ans = -1;
for(long i = hi; i>= lo && ans == -1; i--)
if(last-smaller(root, i-1) < r-i+1)
ans = i;
}
pn(ans);
s = (s+ans)%n;
}
}
}
TreeSet<Long> set = new TreeSet<>();
class Treap{
long val;long pr;
int count;
Treap left, right;
public Treap(long v){
val = v;
long x;
do x = new Random().nextLong();
while(set.contains(x));
pr = x;
set.add(x);
count = 1;
}
void update(){
this.count = 1+getCount(left)+getCount(right);
}
}
int getCount(Treap t){
return t==null?0:t.count;
}
class TreapPair{
Treap left, right;
TreapPair(Treap left, Treap right){
this.left = left;
this.right = right;
}
}
TreapPair split(Treap root, long minRight){
if(root == null)
return new TreapPair(null, null);
if(root.val >= minRight){
TreapPair leftSplit = split(root.left, minRight);
root.left = leftSplit.right;
root.update();
leftSplit.right = root;
return leftSplit;
}else{
TreapPair rightSplit = split(root.right, minRight);
root.right = rightSplit.left;
root.update();
rightSplit.left = root;
return rightSplit;
}
}
Treap merge(Treap left, Treap right){
if(left == null)return right;
if(right == null)return left;
if(left.pr > right.pr){
left.right = merge(left.right, right);
left.update();
return left;
}else{
right.left = merge(left, right.left);
right.update();
return right;
}
}
Treap insert(Treap root, long x){
TreapPair split = split(root, x);
return merge(merge(split.left, new Treap(x)), split.right);
}
int smaller(Treap root, long x){
if(root == null)return 0;
if(root.val <= x)return getCount(root.left)+1+smaller(root.right, x);
else return smaller(root.left, x);
}
boolean contains(Treap root, long x){
if(root == null)return false;
if(root.val == x)return true;
if(x < root.val)return contains(root.left, x);
else return contains(root.right, x);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.00000000000");
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new BURARRAY().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to Share your approach, if you want to. (even if its same 
) . Suggestions are welcomed as always had been. 
Will it work if I use it with lazy propagation?
Also, Need extra rank array!