# BURARRAY - EDITORIAL

**URL:** <https://discuss.codechef.com/t/burarray-editorial/29301>\
**Category:** editorial\
**Tags:** binary-search, editorial, taran\_1407, treap, union-find, ltime73\
**Created:** [June 29, 2019, 2:05am UTC](https://discuss.codechef.com/t/burarray-editorial/29301 "2019-06-29T02:05:59Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![taran\_1407](https://discuss.codechef.com/user_avatar/discuss.codechef.com/taran_1407/32/299985_2.png) [@taran\_1407](https://discuss.codechef.com/u/taran_1407)\
**Post date:** [June 29, 2019, 2:05am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/1 "2019-06-29T02:05:59Z")

</div>

# PROBLEM LINK:

[Practice](https://www.codechef.com/problems/BURARRAY)

[Contest: Division 1](https://www.codechef.com/LTIME73A/problems/BURARRAY)

[Contest: Division 2](https://www.codechef.com/LTIME73B/problems/BURARRAY)

**Setter:** [Mladen Puzic](https://www.codechef.com/users/thesitzr)

**Tester:** [Michael Nematollahi](https://www.codechef.com/users/watcher)

**Editorialist:** [Taranpreet Singh](https://www.codechef.com/users/taran_1407)

# 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](https://discuss.codechef.com/t/match2-editorial/20252).

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](https://cp-algorithms.com/data_structures/disjoint_set_union.html), 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;
> }
> }
> }
> }
> 
> ```

[details = “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;
}

```

[/details]

[details = “Editorialist’s Solution”]  
import java.util._;  
import [java.io](http://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 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;
	    }
	}
}

```

[/details]

Feel free to Share your approach, if you want to. (even if its same 😛 ) . Suggestions are welcomed as always had been. 🙂

---

<div class="post-metadata">

**Author:** ![l\_returns](https://discuss.codechef.com/user_avatar/discuss.codechef.com/l_returns/32/233293_2.png) [@l\_returns](https://discuss.codechef.com/u/l_returns)\
**Post date:** [June 29, 2019, 5:13pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/3 "2019-06-29T17:13:58Z")

</div>

> [@taran\_1407](#):
>
> path compression

Is it mandatory ? I used DSU without path compression. (weighted union)  
[https://www.codechef.com/viewsolution/24995128](https://www.codechef.com/viewsolution/24995128)  
And I think complexity with path compression and weighted union is O(log ^\*N) according to this tutorial  
Here is a good tutorial on DSU :  
[Disjoint Set Union (Union Find) | HackerEarth](https://www.hackerearth.com/practice/notes/disjoint-set-union-union-find/)

---

<div class="post-metadata">

**Author:** ![shivam\_g1470](https://discuss.codechef.com/user_avatar/discuss.codechef.com/shivam_g1470/32/14942_2.png) [@shivam\_g1470](https://discuss.codechef.com/u/shivam_g1470)\
**Post date:** [June 29, 2019, 5:16pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/4 "2019-06-29T17:16:01Z")

</div>

just my opinion. I find path compression faster to code than union by rank. 🙂

---

<div class="post-metadata">

**Author:** ![hetp111](https://discuss.codechef.com/user_avatar/discuss.codechef.com/hetp111/32/241932_2.png) [@hetp111](https://discuss.codechef.com/u/hetp111)\
**Post date:** [June 29, 2019, 5:16pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/5 "2019-06-29T17:16:43Z")

</div>

I used Seg trees and it gave me 20 points 😕 Will it work if I use it with lazy propagation?

---

<div class="post-metadata">

**Author:** ![l\_returns](https://discuss.codechef.com/user_avatar/discuss.codechef.com/l_returns/32/233293_2.png) [@l\_returns](https://discuss.codechef.com/u/l_returns)\
**Post date:** [June 29, 2019, 5:17pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/6 "2019-06-29T17:17:05Z")

</div>

what !!  
Codes just differ by one line I think 🤔🤔

---

<div class="post-metadata">

**Author:** ![kshitij\_789](https://discuss.codechef.com/user_avatar/discuss.codechef.com/kshitij_789/32/208155_2.png) [@kshitij\_789](https://discuss.codechef.com/u/kshitij_789)\
**Post date:** [June 29, 2019, 5:17pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/7 "2019-06-29T17:17:10Z")

</div>

Sometimes round needs to be challenging also.Last time lunchtime was easy

---

<div class="post-metadata">

**Author:** ![shivam\_g1470](https://discuss.codechef.com/user_avatar/discuss.codechef.com/shivam_g1470/32/14942_2.png) [@shivam\_g1470](https://discuss.codechef.com/u/shivam_g1470)\
**Post date:** [June 29, 2019, 5:19pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/8 "2019-06-29T17:19:40Z")

</div>

yeah! save every second 😃 Also, Need extra rank array!

---

<div class="post-metadata">

**Author:** ![anon10768935](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon10768935](https://discuss.codechef.com/u/anon10768935)\
**Post date:** [June 29, 2019, 5:19pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/9 "2019-06-29T17:19:55Z")

</div>

[https://www.codechef.com/viewsolution/24998486](https://www.codechef.com/viewsolution/24998486)  
Answer using unordered map

---

<div class="post-metadata">

**Author:** ![taran\_1407](https://discuss.codechef.com/user_avatar/discuss.codechef.com/taran_1407/32/299985_2.png) [@taran\_1407](https://discuss.codechef.com/u/taran_1407)\
**Post date:** [June 29, 2019, 5:21pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/10 "2019-06-29T17:21:11Z")

</div>

In worst case, it might have lead to TLE, wasn’t sure though.

---

<div class="post-metadata">

**Author:** ![l\_returns](https://discuss.codechef.com/user_avatar/discuss.codechef.com/l_returns/32/233293_2.png) [@l\_returns](https://discuss.codechef.com/u/l_returns)\
**Post date:** [June 29, 2019, 5:21pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/11 "2019-06-29T17:21:22Z")

</div>

so you mean we avoid weighted union and do just path compression right ?

---

<div class="post-metadata">

**Author:** ![apower2](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@apower2](https://discuss.codechef.com/u/apower2)\
**Post date:** [June 29, 2019, 5:21pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/12 "2019-06-29T17:21:28Z")

</div>

Is this you call challenging, maximum of the majority struggling to even score a perfect score in any of the problems.

---

<div class="post-metadata">

**Author:** ![kshitij\_789](https://discuss.codechef.com/user_avatar/discuss.codechef.com/kshitij_789/32/208155_2.png) [@kshitij\_789](https://discuss.codechef.com/u/kshitij_789)\
**Post date:** [June 29, 2019, 5:21pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/13 "2019-06-29T17:21:37Z")

</div>

solution using path compression:-[CodeChef: Practical coding for everyone](https://www.codechef.com/viewsolution/24988479)

---

<div class="post-metadata">

**Author:** ![l\_returns](https://discuss.codechef.com/user_avatar/discuss.codechef.com/l_returns/32/233293_2.png) [@l\_returns](https://discuss.codechef.com/u/l_returns)\
**Post date:** [June 29, 2019, 5:22pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/14 "2019-06-29T17:22:19Z")

</div>

I used weighted union and its O(log(n)) in worst case I think 🤔

---

<div class="post-metadata">

**Author:** ![meiniak](https://discuss.codechef.com/user_avatar/discuss.codechef.com/meiniak/32/4024_2.png) [@meiniak](https://discuss.codechef.com/u/meiniak)\
**Post date:** [June 29, 2019, 5:22pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/15 "2019-06-29T17:22:35Z")

</div>

[CodeChef: Practical coding for everyone](https://www.codechef.com/viewsolution/24999166) what is going on this solution . Is he using pbds ?

---

<div class="post-metadata">

**Author:** ![shivam\_g1470](https://discuss.codechef.com/user_avatar/discuss.codechef.com/shivam_g1470/32/14942_2.png) [@shivam\_g1470](https://discuss.codechef.com/u/shivam_g1470)\
**Post date:** [June 29, 2019, 5:23pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/16 "2019-06-29T17:23:47Z")

</div>

You can do both do further reduce constant factor(Asymptotically, they all are same. independent or using both at once)

---

<div class="post-metadata">

**Author:** ![l\_returns](https://discuss.codechef.com/user_avatar/discuss.codechef.com/l_returns/32/233293_2.png) [@l\_returns](https://discuss.codechef.com/u/l_returns)\
**Post date:** [June 29, 2019, 5:25pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/18 "2019-06-29T17:25:05Z")

</div>

using both makes it O(log^\*(n)) its different

---

<div class="post-metadata">

**Author:** ![sajalagrawal14](https://discuss.codechef.com/user_avatar/discuss.codechef.com/sajalagrawal14/32/8536_2.png) [@sajalagrawal14](https://discuss.codechef.com/u/sajalagrawal14)\
**Post date:** [June 29, 2019, 5:26pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/19 "2019-06-29T17:26:01Z")

</div>

i think lazy is only be helpful if there is a range update !!!but there is a index update only

---

<div class="post-metadata">

**Author:** ![shivam\_g1470](https://discuss.codechef.com/user_avatar/discuss.codechef.com/shivam_g1470/32/14942_2.png) [@shivam\_g1470](https://discuss.codechef.com/u/shivam_g1470)\
**Post date:** [June 29, 2019, 5:27pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/20 "2019-06-29T17:27:19Z")

</div>

check [this](https://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/).  
here its mentioned using both effectively reduce to it constant though asymptotically its still log(n) for all cases.

---

<div class="post-metadata">

**Author:** ![loopfree](https://discuss.codechef.com/user_avatar/discuss.codechef.com/loopfree/32/219811_2.png) [@loopfree](https://discuss.codechef.com/u/loopfree)\
**Post date:** [June 29, 2019, 5:28pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/21 "2019-06-29T17:28:03Z")

</div>

I like this code, because I used three map and one set.

---

<div class="post-metadata">

**Author:** ![shardic](https://discuss.codechef.com/user_avatar/discuss.codechef.com/shardic/32/4034_2.png) [@shardic](https://discuss.codechef.com/u/shardic)\
**Post date:** [June 29, 2019, 5:29pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/22 "2019-06-29T17:29:57Z")

</div>

I think I’m gonna cry now.  
I used vectors as a hash to store indices which were set zero.  
[https://www.codechef.com/viewsolution/24998486](https://www.codechef.com/viewsolution/24998486)  
This guy, however, used unordered maps and got AC every test case, whereas I got TLE in all except the first.  
Kill me plij. I don’t wanna live anymore.

[Next page](https://discuss.codechef.com/t/burarray-editorial/29301.md?page=2)