### kartik8800's blog

By kartik8800, 2 years ago, Hello Codeforces, In this blog I will try to write a well detailed editorial for the CSES Range Queries section. The motivation for this editorial comes from https://codeforces.com/blog/entry/70018.

Quoting icecuber "I think CSES is a nice collection of important CP problems, and would like it to have editorials. Without editorials users will get stuck on problems, and give up without learning the solution. I think this slows down learning significantly compared to solving problems with editorials. Therefore, I encourage others who want to contribute, to write editorials for other sections of CSES."

So here I am writing an editorial for the range queries section.

If you find any error or maybe have a better solution to some problem please do share.

# Range Sum Queries I

Given array is A[1..N], for each query of form (L,R) we need to output A[L] + A[L+1] + ... + A[R].
Define an array Prefix such that Prefix[i] = A + A + .. + A[i].
Prefix[R] = A + A + ... + A[R] and Prefix[L-1] = A + A + ... + A[L-1].
Consider Prefix[R] — Prefix[L-1] = (A + A + ... + A[R]) — (A + A + ... + A[L-1]) = (A[L] + A[L+1] + ... + A[R]).

So for every query simply output Prefix[R] — Prefix[L-1].

How Do I build the prefix Array.

Time complexity : O(N) to build prefix array and O(1) per query.

# Range Minimum Queries I

Two possible ways are as follows :
1. Build a Range minimum query segment tree in O(N) time and answer each query in O(logN).
2. Build a sparse table in O(NlogN) time and answer each query in O(1).

Code for approach 1

Refer https://codeforces.com/blog/entry/71101 for my segment tree template.

# Range Sum Queries II

So this one is a direct use of segment tree with point updates and I shall use my segtree template to answer this problem.

Code

Both of these queries can be performed in logN time.
Overall time complexity is O(N) for building segtree and QlogN for Q queries.

# Range Minimum Queries II

Again a straightforward segment tree problem and I will use a similar code as I used for the previous problem. This is the same as RMQ1 except that here we also have point updates. Segment tree solution for RMQ1 and RMQ2 will be identical.

Code

Both of these queries can be performed in logN time.
Overall time complexity is O(N) for building segtree and QlogN for Q queries.

# Range Xor Queries

For this problem we can maintain a segment tree where each node of the tree will store the xor-sum of the range of elements for which it is responsible.
So root of the tree stores : A^A^....^A[N].

To calculate the answer for a particular interior node of the tree we do :
NODE_VAL = LEFT_CHILD_VAL ^ RIGHT_CHILD_VAL
For leaf nodes :
NODE_VAL = A[x], where [x,x] is the range this leaf node is responsible for and if x > N then NODE_VAL = 0 as 0 is the identity for xor_sum.

Again with these observations we can use the same segtree template as follows :

Code

AC code : https://ideone.com/mPhqas

# Range Update Queries

Nice question which can be directly solved with a segment tree with lazy propagation but that is an overkill plus my segtree library does not support lazy propagation as of now.

Let's define a few terms:
SUM[i] = overall update done on the ith element till now
Initially SUM[i] = 0 for all i as no updates have yet been performed, now we would like to track the updates happening so that our answer to a query 2 k can easily be v[k] + SUM[k] where v is the initial array.

How to efficiently maintain the SUM array? Let us build a range sum query segment tree on some array X which has all elements initialized to 0.

DEFINE : RSQ[i] = X + X + .. + X[i] = rangeSumQuery(1,i)

Now say we have a query which tells us to add u to all elements in the range [l,r] then if I perform a point update and make X[l] = X[l] + u think what happens to RSQ[i] for different values of i.

RSQ[i] is unaffected for all i where i < l
and RSQ[i] = RSQ[i] + u for all i >= l.

Effectively we just did a range update on the abstract array RSQ and the range update is equivalent to adding u to all elements of array RSQ from l to N.

But we wanted the range update to be only for the range [l,r], so we should now do a range update in which we subtract u from [r+1,N] and this is the same as doing a point update to X[r+1] such that:

X[r+1] = X[r+1] — u

it must be easy to see the abstract array RSQ is nothing but the required SUM array.

So here is the algorithm :

 For every range update query (l,r,u):   point_update(l,current_val + u)   point_update(r+1,current_val — u) For every query -> value at pos idx:   print SUM[idx] + V[idx]

AC code : https://ideone.com/vBZpYx
Time complexity per query is logN.

# Forest Queries

For every query of the form (x1,y1,x2,y2) we need to answer the number of trees inside the rectangle described by the top left cell of rectangle (x1,y1) and the bottom right cell of rectangle (x2,y2).

Define : DP[i][j] as the number of trees in the rectangle described by (1,1) and (i,j).

Can we use DP matrix to evaluate answers for every query?

Spoiler

Ok, but how?

Spoiler

How to build DP matrix?
Let tree[i][j] = 1, if there is a tree at cell (i,j) else tree[i][j] = 0.

 DP = DP[-1] = DP[-1] = 0 for i from 1 to N:    for j from 1 to N:     DP[i][j] = DP[i-1][j] + DP[i][j-1] — DP[i-1][j-1] + tree[i][j]

Time complexity for build O(N*N) and time complexity per query is O(1).
AC code : https://ideone.com/5dGTfY

# Hotel Queries

Observation : For each group, we need to find the 1st hotel with enough vacancies and book rooms for the group in that hotel.

Brute force : Start checking every hotel from left to right for the number of rooms it has. As soon as you find a hotel with enough rooms use required number of rooms in this hotel. Repeatedly do this till all groups have been assigned a hotel.

How to optimize?

How do I know if there is any hotel in the first x hotels which can be assigned to the current group?

Spoiler

Algorithm :

 For each group gi with size si:   Find the 1st hotel x such that vacancy(x) >= si.    Do point update : vacancy(x) = vacancy(x) — si.    Print x.   If no valid x exists print 0.

Time complexity is O(Mlog^2N), logN steps for the binarySearch and each step of the binary search uses the Range max query segment tree which works in logN time.

# List Removals

Brute force is quite simple if you simply simulate what is mentioned in the problem.
Let us try to optimize. So whenever we are asked to delete some xth element of the list we need to first locate the xth element, print it and then delete it.

How can we make the above processes faster?
Let us keep a boolean array PRESENT of size N and PRESENT[i] = 1 if the ith element of the list has not yet been deleted, 0 otherwise.

Now let us say we have the query : delete the xth element of the list, then this means we are going to delete the element at the jth index of the initial list such that :

1. PRESENT[j] = 1.
2. sum of PRESENT[i] for all i from 1 to j = x.

Why above conditions are necessary and sufficient to locate the correct element?
If are we deleting the element it has to be present in the list currently and so PRESENT[j] should be 1.
If this element at index j(of the initial list) is the xth element of the list(current state of the list) then there are exactly x elements present in the list in range [1,j](of the initial list) and remaining j — x elements got deleted in some previous queries.

How do I find this j?

Spoiler

Ok, elaborate.

Spoiler

How do I find number of elements not yet deleted in the range [1,j]?

Hint : problem comes from range query section

Once you have found the correct j, you need to print it and also mark PRESENT[j] = 0 and make the required point update in the segment tree.

Time complexity analysis is similar to previous problem.

AC code : https://ideone.com/anpuXy

# Salary Queries

Okay so, this seems a bit hard. Maybe if the max possible salary of the employees was limited to some smaller amount(instead of a billion) we might be able to solve it.

So try solving the problem under the constraint that p,a,b <= 10^7.
Now the problem is much easier if I maintain the number of people with a given salary, let us define
freq[i] : number of employees with the salary i
We may now build a range sum query segment tree on this array and to answer a query we simply calculate the sum of the range [a,b].

For updating the salary of some employee from x to y, we do the point updates freq[x] -= 1 and freq[x] += 1 because now 1 less employee has salary x and 1 more employee has the salary y.

But the problem is not solved, since we needed to do this for max possible salary = 1billion, but now we know how to do it for 10^7.

observation

So lets group the salaries into 10^7 buckets and each bucket represent a range of 100 different contiguous salary values. The 0th bucket represents salaries from 1 to 100 and ith bucket represents the salaries from (i)*100 + 1 to (i+1)*100.

These buckets will store aggregated number of employees that have salaries in the given range represented by the bucket.

Now for query [a,b] : all the buckets that are entirely in the range [a,b] their aggregate values should be taken and summed up and for the 2 partial buckets(or 1) not entirely included in the range [a,b] we shall do a brute force.

So build a segment tree over the buckets and calculate the sum over all completely included buckets in the range [a,b]. For remaining partially included buckets do a brute force(actually iterate over approx 100 possible values and choose to include those which are required by a particular query, refer code).

A code will make this explanation much more clear.

AC code : https://ideone.com/zg97c8

Time Complexity?

other way to do it is using a dynamic segment tree in which you only build a node of the tree when it is needed.

# Distinct Values Queries

This is a direct application of the MO's Algorithm. You may read more about MO's algorithm on https://blog.anudeep2011.com/mos-algorithm/

The brute force can be done by simply iterating from index a to b and maintaining number of distinct elements seen till now and a frequency array to indicate which elements and how many occurrences of those elements is present.

Frequency[i] = count of occurences of i in the current range.

Next we try to build the required ADD and REMOVE functions which help MO's algorithm to function properly.
To ADD a new element in the current range simply check if this element is already present(frequency > 0) and if it is present just increase its frequency else if its frequency was 0 then make it 1 and also increase the number of unique elements in the range.
To REMOVE an element from the current range, decrement its frequency by 1, if its frequency reaches 0 then decrease the number of distinct elements in the current range.

After this sort the queries as described by MO's algorithm and you are done.

Twist : We cannot use frequency array as value of individual element can go upto 10^9. So what I'll simply use an unordered_map?

No, unordered_map solution will time out due to high constant factor involved.

How to continue using the frequency array?

Time complexity : O((N+Q)root(N))

AC code : https://ideone.com/RkC547

# Subarray Sum Queries

Let us try to keep track of the max sum subarray in a particular range [L,R]. If we were to build a segment tree in which each node of the tree stores max sum subarray of the range that the node is responsible for then the root keeps track of max sum subarray in the range [1,N].
However for segment trees to be efficient we need to generate the answer of interior nodes of the tree using the answers/information provided by the child nodes.

Now let's try to generate the answer for some interior node P of the segment tree assuming that we already have the answers for the children of the node P.

Node P is responsible for the range [l,r], its left child is responsible for the range [l,mid] and its right child is responsible for the range [mid+1,r].

Now we need to find the sum of max sum subarray in the range [l,r].
Assume you have all necessary information about the child nodes but if you have some information about a child node you also need to generate that piece of information for the parent node as well(since this node also has a parent which will use information given by P to generate it's answer).

How to relate the answer for parent to the answers about children?
Agreed, now what info to keep for every node?

So to summarize, for every node which represents the range [l,r] we should store :
1. sum of max sum subarray in the range [l,r].
2. maximum possible sum of some prefix [l,x] (such value of x is chosen, such that l <= x <= r and sum of elements in range [l,x] is maximum possible.)
3. maximum possible sum of some suffix [x,r].

We now know how to calculate sum of max sum subarray for some node using the above mentioned information about children nodes but as discussed we should also calculate prefix and suffix info for the parent also.

How to calculate prefix and suffix for parent node

Refer the combine function in the code for more clarity.
AC code : https://ideone.com/MhVmBs

Time complexity : logN per update.

# Forest Queries II

Problem is almost the same as Forest Queries but we also have point updates.
I will discuss two approaches, one of them is quite efficient while the other one struggles to run in the time limit(passes if constant factor is low).

Approach 1

Let us do build the same DP matrix which we had built for the problem Forest Queries. If somehow we are able to keep our DP matrix consistent with the updates then our answer will be the same as before.

ANSWER TO QUERY (x1,y1,x2,y2) : DP[x2][y2] — DP[x1-1][y2] — DP[x2][y1-1] + DP[x1-1][y1-1]

How to efficiently track the updates that happen on some entry DP[i][j]?

Which entries of the DP matrix change if cell (i,j) is updated?

Alright, so now I need to efficiently add or subtract 1 from all the matrix entries (x,y) where that x >= i and y >= j.

So how do we track these updates?

Time complexity O(Q*N*logN)
AC code : https://ideone.com/mcAdwL
Code for fenwick tree is taken from : https://cp-algorithms.com/data_structures/fenwick.html

Approach 2
This approach is more efficient and some might also find it easier to understand.
It uses a 2D Binary Indexed tree to achieve an overall time complexity of O(N^2 + Q*log^2(N)).

You can read more about it here : TopCoder-2DBIT

# Range Updates and Sums

No surprises here. My solution will use the data structure and the technique related to that data structure which most would have already guessed after reading the problem statement. The important thing would be a thorough understanding of the concept and a neat implementation(I have tried to make it readable).

what data structure, what technique?

Alright so our segment tree needs to support the following operations :
1. increase values in range [l,r] by x.
2. set values in range [l,r] = x.
3. return sum of values in range [l,r].

Think about what information should we store per node of the tree, so that we are able to lazily update our nodes when a new update comes in and we are able to propagate the updates downward when needed.

To better understand lazy propagation, I recommend reading this : Super amazing theory in 1 comment (My implementation uses applyAggr and compose functions mentioned here).

What info to store per node?
How do I find the actual Sum using these variables?
How do i propagate these updates downward?

Time Complexity is logN per query.
If something is not explained or if something isn't clear feel free to ask but I recommend understanding lazy prop well before attempting the problem or reading the editorial.
AC code : https://ideone.com/8HQxMk

Please feel free to point out mistakes, suggest better/alternate solutions and to contribute.
I'd be glad to know if this helps :)

P.S. Will add remaining problems in a few days.

UPD : Editorial is almost complete with 2 problems left. 2nd last uses segment tree with lazy prop and I am guessing the last one uses some kind of persistent data structure, will add soon. Comments (138)
 » nice one thanks.if possible , can you please provide all the other links for cses editorials like these 2 by you and icecuber
•  » » I am unaware of any other editorial for CSES sections, if you or anyone knows about some section which is available share it and I'll add the link to them in this blog.
•  » » » CSES Dynamic Programming Editorial :) (https://codeforces.com/blog/entry/70018)
•  » » » » Already mentioned in the blog
•  » » For the last problem, Range Queries and Copies, Kai29 has written this nice blog on problems based on the similar idea.
 » Nice, I'll come back here when I solve those problems.
 » can you provide editorials for the graph section as well
•  » » I'll see to it, however there are a lot of problems in the graph section. Maybe sometime in the future I'll write an editorial on some of the selected problems from that section.
 » 2 years ago, # | ← Rev. 9 →   Distinct values queries can also be done using segment tree (with sorted vector in each node) in $\mathcal{O}(N\log^2N)$.Let's say your original array is $A$. For each index $i$, you store the smallest index $j$ such that $A[i] = A[j]$ but $i < j$. Let the array of $j$ values be $B$. Build segment tree over $B$. For each query $[L,R]$, you just need to check how many values in each of the $\mathcal{O}(\log N)$ segments have value $> R$ via binary search.Of course, this only works if there are no updates. Also, MO's algorithm can be adapted to solve more difficult range query problems (e.g. range query for most frequent element can be done in $\mathcal{O}(Q\sqrt{N}$)).Upd: Here is my implementation of this solution.
•  » » Nice approach, I am guessing this should work. Do contribute the code if you get the time for that.
•  » » » 2 years ago, # ^ | ← Rev. 9 →   Sure. I will implement it when I have time.I think I have one more approach. This time it has time complexity of $\mathcal{O}(N\log N)$. Sort the queries by left endpoint. For each index $i$, you store the smallest index $j$ such that $A[i]=A[j]$ But $i •  » » 2 years ago, # ^ | ← Rev. 2 → We can also solve Distinct Value Queries using Persistent Segment Tree (Online) in O(NlogN). Code — https://pastebin.com/WhkF5cCp •  » » » 2 years ago, # ^ | ← Rev. 8 → Ah yes we can. I think the approach is very similar to my first segment tree solution but we sort the values in$B$in ascending order and set the$i^{th}$index to$1$in the$j^{th}$version of the persistent segment tree for each$B[i]=j$. Thereafter, we just need to take the difference between sum of elements in$[L,R]$in the$(n+1)^{th}$and$R^{th}$version of the segment tree for query$[L,R]$.Even though this works, persistence is unnecessary. •  » » It can also be done using a persistent segment tree in$O(N log N + Q log N)$, here's how:Build a persistent segment tree like this: Traverse the array from left to right. For the element with index N, update its value in the ST to 1 and save its position using a bucket (you can use a map or coordinate compression, whichever you prefer). For the remaining elements, if it is the first appearance of the element, update its value in the ST to a 1. Otherwise, first update the value of the position where it last appeared to 0 and then update its value in the ST to a 1. Save the position of this element using a bucket. Example: For the array$[2, 3, 1, 3, 2]$, we will get the following STs:Element 5:$[0, 0, 0, 0, 1]$Element 4:$[0, 0, 0, 1, 1]$Element 3:$[0, 0, 1, 1, 1]$Element 2:$[0, 1, 1, 0, 1]$Element 1:$[1, 1, 1, 0, 0]$Note that since this is a persistent segment tree, you will have all different versions stored in memory.Now, to answer a query in the form$[a, b]$, we just have to do a "sum" query from$a$to$b$on the ST of element$a$. This works because, by construction, only one element for every value will have a 1, and this will be the leftmost one. If we have one or more elements in the range$[a, b]$with a certain value, the "sum" query will count only one of them. If we don't have any elements with a certain value, the "sum" query will not count them.Total time complexity:$O(N log N + Q log N)$, for the construction of the persistent ST and for every query.Total memory complexity:$O(N log N)$, because we are using a persistent segment tree. Implementation#include #include #include #include using namespace std; typedef long long ll; typedef pair pii; typedef vector vi; struct Node { int val; Node *lchild, *rchild; Node() { val = 0; lchild = nullptr; rchild = nullptr; } Node(int x) { val = x; lchild = nullptr; rchild = nullptr; } }; int N, Q; vi a; Node* build ( Node* node, int l = 1, int r = N ) { if ( node == nullptr ) node = new Node(); if ( l == r ) { node -> val = 0; return node; } int mid = (l + r) / 2; node -> lchild = build ( node -> lchild, l, mid ); node -> rchild = build ( node -> rchild, mid + 1, r ); node -> val = node -> lchild -> val + node -> rchild -> val; return node; } Node* upd ( int pos, int x, Node* node, int l = 1, int r = N ) { if ( pos < l || r < pos ) return node; if ( l == r ) { Node* tmp = new Node(x); return tmp; } int mid = (l + r) / 2; Node* tmp = new Node(); tmp -> lchild = upd ( pos, x, node -> lchild, l, mid ); tmp -> rchild = upd ( pos, x, node -> rchild, mid + 1, r ); tmp -> val = tmp -> lchild -> val + tmp -> rchild -> val; return tmp; } int qry ( int L, int R, Node* node, int l = 1, int r = N ) { if ( R < l || r < L ) return 0; if ( L <= l && r <= R ) return node -> val; int mid = (l + r) / 2; return qry ( L, R, node -> lchild, l, mid ) + qry ( L, R, node -> rchild, mid + 1, r ); } int main () { ios_base::sync_with_stdio ( 0 ); cin.tie ( 0 ); cin >> N >> Q; a.resize ( N + 1 ); for ( int i = 1; i <= N; i++ ) cin >> a[i]; map < int, int > freq; Node* roots[N + 1]; roots[N] = new Node(); roots[N] = build ( roots[N] ); roots[N] = upd ( N, 1, roots[N] ); freq[a[N]] = N; for ( int i = N - 1; i >= 1; i-- ) { roots[i] = roots[i + 1]; if ( freq[a[i]] != 0 ) roots[i] = upd ( freq[a[i]], 0, roots[i] ); roots[i] = upd ( i, 1, roots[i] ); freq[a[i]] = i; } int l, r; for ( int i = 0; i < Q; i++ ) { cin >> l >> r; cout << qry ( l, r, roots[l] ) << "\n"; } return 0; }  •  » » » Ok. This is the online version of my fenwick tree solution. •  » » Hey LanceTheDragonTrainer, can you explain this line: For each query [L, R], you just need to check how many values in each of the O(logN) segments have value > R via binary search.. Why do so? How does that will give us the correct answer for a query [L, R]? •  » » » Firstly, do you understand what are the values in the segment tree? •  » » » » Yes, that segment tree is also called merge sort tree and it stores sorted vector at each node. Sorted values for each segment. •  » » » » » 2 years ago, # ^ | ← Rev. 2 → Ok. What are the values in the array from which you would use to build the segment tree? Hint: You do not use the input array. You need to transform it. •  » » » » » » Hey I read your original comment, I'm repeating again. For each query [L,R], you just need to check how many values in each of the O(logN) segments have value >R. Why counting this value will ensure the correct answer. See I'm not getting this logic. •  » » » » » » » 2 years ago, # ^ | ← Rev. 3 → Ok. I think you didn't get my intention.In order to answer your question, you need to understand what is the array we used to build the segment tree.Say, our input array is: [2, 1, 4, 3, 3, 1, 2, 2].Our transformed array would be: [6, 5, 8, 4, 8, 8, 7, 8] assuming zero-based indexing. To understand how I got this array, read my original comment.Now build segment tree over the transformed array. •  » » » » » » » » Thanks, finally got it. I was not getting why a query on the B array will ensure the correct result for each [L, R]. Now I got it, all those numbers in [L, R] whose B[i] is greater than R is unique in this range. Pardon my stupidity. Thanks again.  » loved it thanks a lot for your time •  » » glad to know you find this helpful.  » Thank you so much kartik8800 You did a Greatjob! I Bookmarked this page!! •  » » I'm glad you liked it. thanks for the appreciation :)  » for List Removals life can be easier with this data structure https://codeforces.com/blog/entry/10355 •  » » have you implemented it using that? can you please share the code? •  » » » Spoiler#include #include #include #include using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx; #define mod 1000000007 /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ *** Debugging Start *** \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ */ void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '\"' << x << '\"';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template void __print(const pair &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifndef ONLINE_JUDGE #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ *** Debugging Ends *** \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ */ using namespace __gnu_pbds; template using ordered_set = tree, rb_tree_tag, tree_order_statistics_node_update>; /// Some frequent usable functions #define int long long void add(int &a,int b){a+=b;if(a>mod)a-=mod;} void sub(int &a,int b){a-=b;if(a<0)a+=mod;} void mul(int &a, int b) {a=1ll * a * b % mod;} template T pow(T a,T b, long long m){T ans=1; while(b>0){ if(b%2==1) ans=(ans*a)%m; b/=2; a=(a*a)%m; } return ans%m; } int powmod(int a,int b) {int res = 1;while(b){if(b&1){res = (res * a)%mod;}b= b/2;a = (a*a)%mod;}return res;} int _ceil(int, int); int _floor(int a, int b) { return b < 0 ? _floor(-a, -b) : a < 0 ? -_ceil(-a, b) : a / b; } int _ceil(int a, int b) { return b < 0 ? _ceil(-a, -b) : a < 0 ? -_floor(-a, b) : (a + b - 1) / b; } // int gcd(int a, int b, int &x, int &y) {if (a == 0) {x = 0; y = 1;return b; // }int x1, y1;int d = gcd(b%a, a, x1, y1); x = y1 - (b / a) * x1;y = x1;return d;} // int find(int v){return v==parent[v]?v:parent[v] = find(parent[v]);} // void merge(int i,int j) // {i = find(i);j = find(j);if(i == j)return;parent[parent[i]] = parent[j];cmp--;} /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ *** Directions in grids *** \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ */ // int dy = {0,0,1,-1}, dx = {1,-1,0,0}; // 4 Direction // int dx[] = {1,-1,0,0,1,1,-1,-1} , dy[] = {0,0,1,-1,1,-1,1,-1}; // 8 Direction // int dx[] = {1,-1,1,-1,2,2,-2,-2} , dy[] = {2,2,-2,-2,1,-1,1,-1}; // Knight moves // int dx[] = {2,-2,1,1,-1,-1} , dy[] = {0,0,1,-1,1,-1}; // Hexagonal Direction #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) #define sp(a , x) cout << fixed << setprecision(a) << x << endl; #define endl "\n" #define pb push_back #define pf push_front #define ub upper_bound #define lb lower_bound #define F first #define S second #define mset(a, b) memset(a, b, sizeof a) #define sz(x) ((int)(x.size())) #define sqr(x) ((x) * (x)) #define graph vector #define vi vector #define vvi vector> #define pi pair #define all(c) c.begin() , c.end() #define rep(i,a) for(int i=0;i=b;i--) #define iter(it,a) for(auto it=a.begin();it!=a.end();it++) #define PQP priority_queue, greater> #define PQI priority_queue, greater> #define dbg debug #define inf (int)1e16 const long double EPS = 0.0000000001; const long double PI = (acos(-1)); /// define some data....... const int N = (int)3e6+6; void solve() { ropev; int n; cin >> n; rep(i,n){ int x; cin >> x; v.pb(x); } rep(i,n) { int id; cin >> id; cout<> test; int tc=1; while(test--) { //cout<<"Case "< •  » » » » thanks a lot can you just explain me this data structure? i tried studying from the editorial but got nothing. it would be really nice of you •  » » » » » have you went through https://en.wikipedia.org/wiki/Rope_(data_structure) let me know if I can further clarify •  » » » » » » yes still couldn't understand •  » » » » » » and also why are you not using inserting  » Hello just a doubt that how do i build my segment tree for this question : Range Update Queries like i will be using lazy propagation for the range updates, ADDEND to increase value in the range and getValue to get the value at the kth index. Can you please help. https://ideone.com/h2Mo9u this is my segment tree template •  » » 2 years ago, # ^ | ← Rev. 2 → You don't need lazy prop for range sum updates and point queries. Instead of storing the array directly, store the differences between consecutive elements. Then each update can be expressed as two point updates at the ends of the interval, and each query is just a prefix sum query on the new array, which is easily solvable with a BIT or segment tree without lazy prop. •  » » » thank you for replying yeah i have solved this question using segment tree already similar to author one, but i wanted to see if range increment(addend in case of lazzy prop can be used) to solve this question however i am unable to do it. here is the link to my template can you please guide me on solving this using lazy prop ( i somehow want to use that addend function in my template) https://ideone.com/h2Mo9u •  » » » » Yeah, of course you can solve it with range updates and point queries on a segment tree using lazy prop. If you are learning how to do this for the first time, I suggest reading this starting from page 245. Go through the implementation carefully and test your code along the way. It's also ok to look at other people's implementations of segment trees to get an idea of how it should work. •  » » » can you please provide the code of this implementation please? •  » » This is possibly the best theory about lazy propagation that I have read till now : https://codeforces.com/blog/entry/44478?#comment-290116 Give it a read, you might find implementing lazy propagation easier.  » 2 years ago, # | ← Rev. 3 → You can solve Salary Queries offline with binary search and bit. here's my code https://pastebin.com/VG6JZaZt . •  » » Can u explain your approach, like if you are using binary search on answer then how are u managing to check for this value whether it can be answer or not? •  » » » 2 years ago, # ^ | ← Rev. 3 → We can add all the salaries that appear in the initial salaries array & in the queries to a vector ve. Updates: Let x be the salary of an employee we will get the index k of x in ve and add one to k in the BIT, we'll do the same thing to subtract the old salary of this employee from the BIT.Queries: we will get the indices of l and r in ve using bs and answer the queries from bit.time complexity : O(nlogn+qlogn) •  » » » » hi your solution works but i have no clue how. i mean why are there so many continue; ? and also why are you using visited every time? please help i really want learn from your solution •  » » » » » Upd: understood  » Salary Queries can be solved for arbitrarily large values in the array using coord compression to get all values in the range$[1..N]$, then just use a BIT, segment tree, or whatever your favorite data structure is to solve it. The implementation is very messy, so I wouldn't recommend coding it, but it ends up taking$O(n\log n+q\log n)$. •  » » Seems reasonable but can you explain what happens when the salary of an employee gets updated?Let's say I did the coordinate compression on the salaries [2,6,8] and got [1,2,3]. Now the query says change 6 to 3, and 6 is mapped to 2, what do you change the compressed_number(2) to?Little confused on how you will work with updates. •  » » » 2 years ago, # ^ | ← Rev. 2 → You have to take into account future updates when running the coord compression. For instance, append all future values to the array, compress it, and then remove them again. You would also do the same thing for both endpoints of all queries.So I guess the complexity is actually$O((n+q)\log(n+q))$, this is basically the same thing though given the constraints. •  » » » » Ah, got it!Makes complete sense, thanks for sharing. •  » » » » That was my approach and it led me to TLE, I'm using a set and a map to compress, and a FenwickTree to perform queries later on. I haven't tried compressing with vectors + binary search, but I don't think it would make a difference, any help will be appreciated •  » » » » » Well apparently compressing with vectors + binary search is allowed to pass meanwhile set + maps isn't, since my code is AC now after that modification •  » » » » » I got AC while using a map for compression. Here's what I used: Codetemplate void compress(it start, it end) { typedef typename remove_reference::type T; map> m; for (it i = start; i != end; i++) m[*i].push_back(i); int t = 0; for (auto& [x, v] : m) { for (auto& i : v) *i = t; t++; } }  •  » » » » » » Thanks  » Anyone has any idea where to find editorial of String Algorithm section of CSES problemset?  » please anyone give me HOTEL QUERIES problem solution.  » xor queries can also be solved using$xor(l,r) = xor(xor(1,r), xor(1, l-1))$right? •  » » sure it will work perfectly and in O(n) time. here is the AC code : https://ideone.com/MuIx1L thanks for mentioning.  » Range Sum Queries I//prefix sum array #include #define int long long #define endl '\n' #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int32_t main(){ IOS int n,m;cin>>n>>m; vectora(n+2); for(int i=1;i<=n;i++){ cin>>a[i];a[i]+=a[i-1]; } for(int i=1;i<=m;i++){ int l,r;cin>>l>>r; cout << a[r] - a[l-1] << endl; } }  Range Minimum Queries I// sparse table #include #define int long long #define endl '\n' #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const int maxn = 2e5+10; vector>st(maxn,vector(21)); vectorlg(maxn); int32_t main(){ IOS lg=0; for(int i=2;i>1]+1; } int n,m;cin>>n>>m; for(int i=1;i<=n;i++){ cin>>st[i]; } for(int i=n;i>=1;i--){ for(int j=1;i+(1<>l>>r; cout< #define int long long #define endl '\n' #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const int maxn = 2e5+10; vectort(maxn<<2),a(maxn); int n,m; void build(int rt,int l,int r){ if( l == r ){t[rt]=a[l];return;} int m=(l+r)>>1; build(rt<<1,l,m); build((rt<<1)+1,m+1,r); t[rt]=t[(rt<<1)]+t[(rt<<1)+1]; } void update(int rt,int l,int r,int pos,int new_val){ if(l==r){t[rt]=new_val;return;} int m=(l+r)>>1; if(pos<=m)update(rt<<1,l,m,pos,new_val); else update((rt<<1)+1,m+1,r,pos,new_val); t[rt]=t[(rt<<1)]+t[(rt<<1)+1]; } int query(int rt,int tl,int tr,int l,int r){ if( l > r )return 0; if( l == tl && r == tr )return t[rt]; int m=(tl+tr)>>1; return query(rt<<1,tl,m,l,min(r,m))+query((rt<<1)+1,m+1,tr,max(m+1,l),r); } int32_t main(){ IOS cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } build(1,1,n); for(int i=1;i<=m;i++){ int x,y,z;cin>>x>>y>>z; if(x==1)update(1,1,n,y,z); else cout< #define int long long #define endl '\n' #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const int maxn = 2e5+10; vectort(maxn<<2),a(maxn); int n,m; void build(int rt,int l,int r){ if( l == r ){t[rt]=a[l];return;} int m=(l+r)>>1; build(rt<<1,l,m); build((rt<<1)+1,m+1,r); t[rt]=min(t[(rt<<1)],t[(rt<<1)+1]); } void update(int rt,int l,int r,int pos,int new_val){ if(l==r){t[rt]=new_val;return;} int m=(l+r)>>1; if(pos<=m)update(rt<<1,l,m,pos,new_val); else update((rt<<1)+1,m+1,r,pos,new_val); t[rt]=min(t[(rt<<1)],t[(rt<<1)+1]); } int query(int rt,int tl,int tr,int l,int r){ if( l > r )return 1e15; if( l == tl && r == tr )return t[rt]; int m=(tl+tr)>>1; return min(query(rt<<1,tl,m,l,min(r,m)),query((rt<<1)+1,m+1,tr,max(m+1,l),r)); } int32_t main(){ IOS cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } build(1,1,n); for(int i=1;i<=m;i++){ int x,y,z;cin>>x>>y>>z; if(x==1)update(1,1,n,y,z); else cout< #define int long long #define endl '\n' #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const int maxn = 2e5+10; vectora(maxn); int n,m; int32_t main(){ IOS cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i];a[i]^=a[i-1]; } for(int i=1;i<=m;i++){ int l,r;cin>>l>>r; cout<<(a[r]^a[l-1])< #define int long long #define endl '\n' #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const int maxn = 2e5+10; vectorlazy(maxn<<2),a(maxn); int n,m; void push(int r){ lazy[r<<1]+=lazy[r]; lazy[(r<<1)+1]+=lazy[r]; lazy[r]=0; } void update(int rt,int tl,int tr,int l,int r,int addend){ if(l>r)return; if(l==tl&&r==tr){lazy[rt]+=addend;return;} push(rt); update((rt<<1),tl,(tl+tr)>>1,l,min(r,(tl+tr)>>1),addend); update((rt<<1)+1,((tl+tr)>>1)+1,tr,max(l,((tl+tr)>>1)+1),r,addend); } int query(int rt,int tl,int tr,int pos){ if(tl==tr)return lazy[rt]; push(rt); if(pos<=((tl+tr)>>1))return query(rt<<1,tl,(tl+tr)>>1,pos); return query((rt<<1)+1,((tl+tr)>>1)+1,tr,pos); } int32_t main(){ IOS cin>>n>>m; for(int i=1;i<=n;i++){ int x;cin>>x;update(1,1,n,i,i,x); } for(int i=1;i<=m;i++){ int x;cin>>x; if(x==1){ int l,r,dx;cin>>l>>r>>dx; update(1,1,n,l,r,dx); }else{ int pos;cin>>pos; cout< #define int long long #define endl '\n' #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const int maxn = 1000+5; vector>dp(maxn,vector(maxn)); int32_t main(){ IOS int n,m;cin>>n>>m; for(int i=1;i<=n;i++){ string s;cin>>s; for(int j=1;j<=n;j++){ dp[i][j]=(s[j-1]=='*')+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]; } } auto query=[&](int x1,int y1,int x2,int y2){ return dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1]; }; for(int i=1;i<=m;i++){ int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2; cout< #define int long long #define endl '\n' #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const int maxn = 2e5+10; vectort(maxn<<2); int n,m; void update(int rt,int l,int r,int pos,int new_val){ if(l==r){t[rt]=new_val;return;} if(pos<=((l+r)>>1))update(rt<<1,l,(l+r)>>1,pos,new_val); else update((rt<<1)+1,((l+r)>>1)+1,r,pos,new_val); t[rt]=max(t[rt<<1],t[(rt<<1)+1]); } int query(int rt,int tl,int tr,int l,int r){ if(l>r)return -1e15; if(l==tl&&r==tr)return t[rt]; return max(query(rt<<1,tl,(tl+tr)>>1,l,min(r,(tl+tr)>>1)),query((rt<<1)+1,((tl+tr)>>1)+1,tr,max(l,((tl+tr)>>1)+1),r)); } int32_t main(){ IOS cin>>n>>m; for(int i=1;i<=n;i++){ int x;cin>>x;update(1,1,n,i,x); } for(int i=1;i<=m;i++){ int x;cin>>x; int l=1,r=n,pos=n+1; while(l<=r){ int m=(l+r)>>1; if( query(1,1,n,1,m) >= x ){ pos=min(pos,m); r=m-1; }else{ l=m+1; } } if(pos<=n){ cout< #define int long long #define endl '\n' #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const int maxn = 2e5+10; vectort(maxn<<2),a(maxn); int n; void update(int rt,int l,int r,int pos,int new_val){ if(l==r){t[rt]=new_val;return;} if(pos<=((l+r)>>1))update(rt<<1,l,(l+r)>>1,pos,new_val); else update((rt<<1)+1,((l+r)>>1)+1,r,pos,new_val); t[rt]=t[rt<<1]+t[(rt<<1)+1]; } int query(int rt,int tl,int tr,int l,int r){ if(l>r)return 0; if(l==tl&&r==tr)return t[rt]; return query(rt<<1,tl,(tl+tr)>>1,l,min(r,(tl+tr)>>1))+query((rt<<1)+1,((tl+tr)>>1)+1,tr,max(l,((tl+tr)>>1)+1),r); } int32_t main(){ IOS cin>>n; for(int i=1;i<=n;i++){ cin>>a[i];update(1,1,n,i,1); } for(int i=1;i<=n;i++){ int x;cin>>x; int l=1,r=n,pos=n; while(l<=r){ int m=(l+r)>>1; if(query(1,1,n,1,m)>=x){ pos=min(pos,m); r=m-1; }else{ l=m+1; } } cout< //#define int long long #define endl '\n' #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int maxn = 1e6+10; vectorB(maxn); vectora(maxn); vectort(maxn),X(maxn),Y(maxn); vectormp; int n,m; void update(int i,int x){ i = lower_bound(mp.begin(),mp.end(),i)-mp.begin()+1; while( i <= maxn ){ B[i]+=x; i+=i&-i; } } int query(int i){ i = lower_bound(mp.begin(),mp.end(),i)-mp.begin()+1; int x=0; while( i > 0 ){ x+=B[i]; i-=i&-i; } return x; } int32_t main(){ IOS cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i];mp.push_back(a[i]); } for(int i=1;i<=m;i++){ char c;cin>>c>>X[i]>>Y[i]; t[i]= c == '?' ? 1 : 0 ; mp.push_back(X[i]-1); mp.push_back(X[i]); mp.push_back(Y[i]); } sort(mp.begin(),mp.end()); mp.erase(unique(mp.begin(),mp.end()),mp.end()); maxn = mp.size()+1; for(int i=1;i<=n;i++){ update(a[i],1); } for(int i=1;i<=m;i++){ if(t[i]){ cout< #define int long long #define endl '\n' #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const int maxn = 2e5+10; vectora(maxn),t(maxn<<2),ts(maxn<<2),ls(maxn<<2),rs(maxn<<2); int n,m; void merge(int rt,int l,int r){ t[rt]=max({t[rt<<1],t[(rt<<1)+1],ts[rt<<1],ts[(rt<<1)+1],ts[rt<<1]+ts[(rt<<1)+1],ls[rt<<1],ls[(rt<<1)+1],rs[rt<<1],rs[(rt<<1)+1],ts[rt<<1]+ls[(rt<<1)+1],ts[(rt<<1)+1]+rs[rt<<1],rs[rt<<1]+ls[(rt<<1)+1]}); ls[rt]=max({ls[rt<<1],ts[rt<<1],ts[rt<<1]+ls[(rt<<1)+1],ts[rt<<1]+ts[(rt<<1)+1]}); rs[rt]=max({rs[(rt<<1)+1],ts[(rt<<1)+1],ts[(rt<<1)+1]+rs[(rt<<1)],ts[(rt<<1)]+ts[(rt<<1)+1]}); ts[rt]=ts[rt<<1]+ts[(rt<<1)+1]; } void build(int rt,int l,int r){ if(l==r){t[rt]=ts[rt]=ls[rt]=rs[rt]=a[l];return;} build(rt<<1,l,(l+r)>>1); build((rt<<1)+1,((l+r)>>1)+1,r); merge(rt,l,r); } void update(int rt,int l,int r,int pos,int val){ if(l==r){t[rt]=ts[rt]=ls[rt]=rs[rt]=val;return;} if(pos<=(l+r)>>1)update(rt<<1,l,(l+r)>>1,pos,val); else update((rt<<1)+1,((l+r)>>1)+1,r,pos,val); merge(rt,l,r); } int query(){ return t; } int32_t main(){ IOS cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } build(1,1,n); for(int i=1;i<=m;i++){ int pos,val;cin>>pos>>val; update(1,1,n,pos,val); cout< //#define int long long #define endl '\n' #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const int S = 448 , maxn = 2e5+5; struct box{ int l,r,i; bool operator <(const box other){ if( l/S != other.l/S )return l/S < other.l/S; return r < other.r; } }; vectora(maxn),ans(maxn),cnt(maxn); vectorq(maxn); vectormp; int n,m,tot=0; void insert(int x){ if( !cnt[x] )tot++; cnt[x]++; } void remove(int x){ cnt[x]--; if( !cnt[x] ){ tot--; } } int32_t main(){ IOS cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i];mp.push_back(a[i]); } for(int i=1;i<=m;i++){ cin>>q[i].l>>q[i].r;q[i].i=i; } sort(q.begin()+1,q.begin()+m+1); sort(mp.begin(),mp.end()); mp.erase(unique(mp.begin(),mp.end()),mp.end()); for(int i=1;i<=n;i++){ a[i]=lower_bound(mp.begin(),mp.end(),a[i])-mp.begin()+1; } int l = 1 , r = 1; for(int i=1;i<=m;i++){ while( r <= q[i].r ){ insert(a[r++]); } while( l < q[i].l ){ remove(a[l++]); } while( l > q[i].l ){ insert(a[--l]); } while( r > q[i].r + 1){ remove(a[--r]); } ans[q[i].i]=tot; } for(int i=1;i<=m;i++){ cout< //#define int long long #define endl '\n' #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const int maxn = 1000+5; vector>B(maxn,vector(maxn)); int n,m; void update(int x,int y,int val){ while( x <= n ){ int _y = y; while( _y <= n ){ B[x][_y]+=val; _y+=_y&-_y; } x+=x&-x; } } int query(int x,int y){ int s=0; while( x > 0 ){ int _y = y; while( _y > 0 ){ s+=B[x][_y]; _y-=_y&-_y; } x-=x&-x; } return s; } int32_t main(){ IOS cin>>n>>m; for(int i=1;i<=n;i++){ string s;cin>>s; for(int j=1;j<=n;j++){ if( s[j-1] =='*'){ update(i,j,1); } } } for(int i=1;i<=m;i++){ int t;cin>>t; if(t==1){ int x,y;cin>>x>>y; int q = query(x,y)-query(x-1,y)-query(x,y-1)+query(x-1,y-1); if( q )update(x,y,-1); else update(x,y,+1); }else{ int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2; cout< #define int long long #define endl '\n' #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const int maxn = 2e5+10; vectort(maxn<<2),lazy(maxn<<2),type(maxn<<2,2),a(maxn); int n,m; void push(int rt,int l,int r){ if( type[rt] == 2 )return; int m = (l+r)>>1; if( type[rt] ){ t[rt<<1]+=lazy[rt]*(m-l+1); lazy[rt<<1]+=lazy[rt]; t[(rt<<1)+1]+=lazy[rt]*(r-m); lazy[(rt<<1)+1]+=lazy[rt]; } else{ t[rt<<1]=lazy[rt]*(m-l+1); lazy[rt<<1]=lazy[rt]; t[(rt<<1)+1]=lazy[rt]*(r-m); lazy[(rt<<1)+1]=lazy[rt]; } type[rt<<1]=min(type[rt<<1],type[rt]); type[(rt<<1)+1]=min(type[(rt<<1)+1],type[rt]); lazy[rt]=0; type[rt]=2; } void build(int rt,int l,int r){ if(l==r){t[rt]=a[l];return;} build(rt<<1,l,(l+r)>>1); build((rt<<1)+1,((l+r)>>1)+1,r); t[rt]=t[rt<<1]+t[(rt<<1)+1]; } void update(int rt,int tl,int tr,int l,int r,int qt,int val){ if(l>r)return; if(tl==l&&tr==r){ if(qt){ t[rt]+=val*(tr-tl+1); lazy[rt]+=val; }else{ t[rt]=val*(tr-tl+1); lazy[rt]=val; } type[rt]=min(type[rt],qt); return; } push(rt,tl,tr); update(rt<<1,tl,(tl+tr)>>1,l,min(r,(tl+tr)>>1),qt,val); update((rt<<1)+1,((tl+tr)>>1)+1,tr,max(l,((tl+tr)>>1)+1),r,qt,val); t[rt]=t[rt<<1]+t[(rt<<1)+1]; } int query(int rt,int tl,int tr,int l,int r){ if(l>r)return 0; if(tl==l&&tr==r)return t[rt]; push(rt,tl,tr); int ans = query(rt<<1,tl,(tl+tr)>>1,l,min(r,(tl+tr)>>1))+query((rt<<1)+1,((tl+tr)>>1)+1,tr,max(((tl+tr)>>1)+1,l),r); t[rt]=t[rt<<1]+t[(rt<<1)+1]; return ans; } int32_t main(){ IOS cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } build(1,1,n); for(int i=1;i<=m;i++){ int qt;cin>>qt; if( qt == 1){ int l,r,dx;cin>>l>>r>>dx; update(1,1,n,l,r,1,dx); }else if(qt==2){ int l,r,x;cin>>l>>r>>x; update(1,1,n,l,r,0,x); }else{ int l,r;cin>>l>>r; cout< •  » » 2 years ago, # ^ | ← Rev. 3 → nvm got it •  » » Can you explain to me Range Xor Queries. Here a is not initialized to anything. How is this working? •  » » » Check this article.. It will clear all your doubts. •  » » Thank you for your comment.  » 2 years ago, # | ← Rev. 3 → Just mention that "Distinct Values Queries" problem have segment tree solution code#include #include #include #include using namespace std; #define N (1<<18) int tree[2*N]; void update(int k, int x) { k += N; tree[k] = x; for (k /= 2; k >= 1; k /= 2) { tree[k] = tree[2*k]+tree[2*k+1]; } } int getSum(int a, int b) { a += N; b += N; int s = 0; while (a <= b) { if (a%2 == 1) s += tree[a++]; if (b%2 == 0) s += tree[b--]; a /= 2; b /= 2; } return s; } int n, q; int x; map pos; int pred; int a; int b; vector> queries; int result; int main() { cin >> n >> q; for (int i = 1; i <= n; i++) { cin >> x[i]; pred[i] = pos[x[i]]; pos[x[i]] = i; } for (int i = 1; i <= q; i++) { cin >> a[i] >> b[i]; queries.push_back({b[i],i}); } sort(queries.begin(),queries.end()); int k = 0; for (int i = 0; i < q; i++) { while (k < queries[i].first) { k++; update(pred[k],1); } int u = queries[i].second; result[u] = b[u]-a[u]+1-getSum(a[u],b[u]); } for (int i = 1; i <= q; i++) { cout << result[i] << "\n"; } }  •  » » Can you please explain a bit? •  » » » a bit is a binary indexed tree : ) •  » » » » Ohh lol. Sorry I mean how can you count distinct values using segment tree?  » I tried solving the problem Salary Queries by the way that you have suggested. I used Fenwick Tree instead of a Segment Tree. I am getting TLE in it. However, when I tried running the inputs, the answers are coming out to be correct. Any suggestions on optimizing it? Here is the link to my code: https://ideone.com/dtWevB •  » » on first look, I would say it is possible that your helper function is causing the TLE.Accessing an element of a map is O(logN) operation. so inside your helper you will access it 100 times -> 100*log(N), in my implementation I have eliminated this logN factor. and my helper takes 100 + logN.So might be the reason for TLE, try optimizing and let me know if it passes. •  » » » So, do you mean to say that instead of creating a map of I should create a map of so that I can first access the map element in logN and then traverse the vector in 100 operations? •  » » » » Read the calc() method of my Implementation. I do one map access to get iterator corresponding to value lo. From there onwards I increment the iterator till the key being pointed by iterator is less than hi.Iterator increment is O(1) operation. •  » » » » » I was also stuck with the same problem thought I might find something useful in the comments. I was stuck at it since yesterday 2 hours earlier I found my mistake but wasn't able to resolve it. So thanks a lot for your contribution. •  » » » » Doing this worked out for me. Thanks a lot for your help. This question really taught me a lot. Thanks again. •  » » » » » Glad to know, You're welcome :) •  » » » » » » 2 years ago, # ^ | ← Rev. 5 → nvm got it •  » » » » » » can u explain me why i am getting tle at second last test case my sol is this https://ideone.com/STb2hw  » 2 years ago, # | ← Rev. 3 → nvm got it  » Can somebody help me optimize my code for the problem Distinct Queries. I am using Mo's algorithm to solve it. The time complexity of which is O(n*sqrt(n)). However, I am getting TLE in it. The test cases provided by them are taking more than 20 seconds to run on my code. I have recently learned Mo's algorithm which is why I am unaware of various optimizations that can be done in it. Here is my link: TLE SOLUTION Thanks in advance. •  » » Not sure if it is NrootN, what about the map you are using? •  » » » Sorry, I forgot to include the complexity for the map. So, the overall complexity is O(N*(Sqrt(N))*Log(N)). Can you suggest me a way to remove the map to store the frequencies of the elements. I am using map as the range of elements is 10^9. I would have used an array otherwise. But for the overall code, I am pretty sure that if there is no map then the complexity would be NrootN •  » » » » try reading the blog solution, defines exactly how to get rid of the map. •  » » » » » Thanks again. It worked by coordinate compression. The time changed from 20 seconds to 0.8 seconds as soon as I did that. Really appreciate your effort in helping others. •  » » 8 months ago, # ^ | ← Rev. 2 → please help in problem distinct querries .can u explain me why i am getting tle at second last test case my sol is this https://ideone.com/STb2hw  » Hotel queries can be done in O(mlogn).Instead of using binary search, we will descend the Segment Tree, starting at the root vertex, and moving each time to either the left or the right child, depending on which segment contains the vacancy greater than the required rooms. Codell get(ll val,ll v=1,ll tl=0,ll tr=n-1) { if(val>tree[v]) return -1; if(tl==tr) return tl; ll tm=(tl+tr)/2; if(tree[2*v]>=val) return get(val,2*v,tl,tm); else return get(val,2*v+1,tm+1,tr); }  •  » » please help in problem distinct querries .can u explain me why i am getting tle at second last test case my sol is this https://ideone.com/STb2hw  » 2 years ago, # | ← Rev. 3 → pdbs can solve few of the problems in the section. Btw, can anyone explain this solution by rainboy  » First of all thanks for the editorial. Really appreciate this. Hey if it's okay could you check out this code for the Polynomial Queries problem. I am using lazy propagation and the AP sum concept, but seems to be getting RE on the second sub task. Code#include #define int long long using namespace std; class SegTree { public: int sum, lb, rb, len; vector op; SegTree *left, *right; SegTree(int l, int r, int a[]) { lb = l, rb = r; if (l == r) { sum = a[l]; len = 1; } else { int mid = (l + r) / 2; left = new SegTree(l, mid, a); right = new SegTree(mid + 1, r, a); len = rb - lb + 1; refresh(); } } void refresh() { sum = left->sum + right->sum; } void propagate() { if (!op.empty()) { for (auto &i : op) { int last = (i + len - 1); sum += (len * (i + last)) / 2; if (lb != rb) { left->op.emplace_back(i); right->op.emplace_back(i + left->len); } } op.clear(); } } void update(int l, int r, int val) { propagate(); if (lb != rb) { left->propagate(), right->propagate(); refresh(); } if (l > rb || r < lb) return; else if (lb >= l and rb <= r) { op.emplace_back(val); propagate(); if (lb != rb) { left->propagate(), right->propagate(); refresh(); } } else { left->update(l, r, val); if (left->rb >= l) { int nVal = val + (left->rb - max(l, left->lb) + 1); right->update(l, r, nVal); } else right->update(l, r, val); refresh(); } } int query(int l, int r) { propagate(); if (lb != rb) { left->propagate(), right->propagate(); refresh(); } if (l > rb || r < lb) { return 0; } else if (lb >= l and rb <= r) { return sum; } else { return left->query(l, r) + right->query(l, r); } } }; int a; void solve() { int n, m; cin >> n >> m; for (int i = 0; i < n; i++) cin >> a[i]; auto tr = SegTree(0, n - 1, a); int t, l, r; while (m--) { cin >> t >> l >> r; if (t == 1) { tr.update(l - 1, r - 1, 1); } else { cout << tr.query(l - 1, r - 1) << '\n'; } } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); solve(); return 0; }   » Thanks for sharing  » If somebody's interested in how to solve the last problem (Range Queries and Copies), this article was very helpful: https://www.geeksforgeeks.org/persistent-segment-tree-set-1-introduction/ •  » » I solved it using a regular segment tree. But I will learn to use persistent one. •  » » please help in problem distinct querries .can u explain me why i am getting tle at second last test case my sol is this https://ideone.com/STb2hw  » for salary queries if i maintain a node with two values min and max then also i can do same thing. I checked this it is giving right answer for short inputs but on submission it is giving rte. code is here:   ll n,tsize; ll arr; ll minsegtree; ll maxsegtree;ll minimum(ll a, ll b){ return (ab)?a:b; }void update(ll ith, ll val, ll low, ll high, ll index) { if(low == high){ minsegtree[index] = maxsegtree[index]= val; return; } ll mid = (low + high)/2; if(ith <= mid){ update(ith, val, low, mid, 2*index + 1); }else{ update(ith, val, mid+1, high, 2*index+ 2); } minsegtree[index] = minimum(minsegtree[2*index + 1], minsegtree[2*index + 2]); maxsegtree[index] = maximum(maxsegtree[2*index +1], maxsegtree[2*index + 2]); }ll countemps(ll lrange, ll hrange, ll low , ll high, ll index) { if(lrange > maxsegtree[index] || hrange < minsegtree[index]) return 0; if(minsegtree[index] >= lrange && maxsegtree[index] <= hrange){ if(high <= n-1) return (high - low + 1); else{ return (n-low); } } ll mid = (low + high)/2; return countemps(lrange, hrange, low , mid , 2*index + 1) + countemps(lrange, hrange, mid + 1, high, 2*index + 2);}int main() { fastio; ll q; cin>>n>>q; for(int i=0;i>arr[i]; } tsize=1; while(tsize>ch; if(ch == '?'){ ll a,b; cin>>a>>b; cout<>k>>x; update(k-1,x, 0,temp-1,0); } } return 0; }  can anyone check please? for sample test case it is giving right output.  » 23 months ago, # | ← Rev. 3 → im trying to use the fenwick tree for the third problem, range sum queries 2, im getting WA for some reason in the second test case. please help #include using namespace std; #define ll long long void add(vector &b, int i, int x) { while(i &b, int i) { ll res=0; while(i>0) { res+=b[i]; i-=(i&-i); } return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector v(n+1, 0); vector bit(n+1, 0); for(int i=1; i<=n; i++) { cin >> v[i]; add(bit, i, v[i]); } for(int i=0; i> c >> a >> b; if(c==2) cout << sum(bit, b)-sum(bit, a-1) << endl; else add(bit, a, b-v[a]); } }  •  » » ok i solved it, i wasnt updating the original vector after the add method call in the queries loop  » 22 months ago, # | ← Rev. 2 → I believe List Removals can be solved more efficiently using a balanced BST (order statistic tree to be exact)? When delete index x, insert x to the BST.The "real" index of index j = j — BST.countLessThan(j)Time complexity: O(nlogn)EDIT: THIS IS WRONG.  » For Forest Queries II, I tried Approach 1 with Segment tree and got 1/4 TLE. Then I somehow managed to code 2D segment tree, but got 3/4 TLE. FML.Is BIT way better than segment tree or it's my code that's the problem?kartik8800 •  » » BIT has a much smaller constant factor  » Your segment Tree template is so unbelievable. Thanks for sharing :)  » Jan update introduced new range query problems. Any hints for solving Increasing Array Queries? •  » » Hello !I advise you to observe what happens when we have a = 0 for all requests. •  » » » 21 month(s) ago, # ^ | ← Rev. 2 → If the queries are of type [0, r], then we can sort them increasingly based on r, and use maximum so far to calculate differences.If we know the answers to all prefixes upto to a certain r, can we answer any [l, r] queries by inclusion-exclusion principle? •  » » » » Hmm, clearly, it is not possible to solve by doing ans [r] — ans [l] (eg with 2 1 3); I should have been more specific in my comment, sorry.If you set l = 0, you will have to "move up" a number of values ​​with indices> 0 to make the subarray increasing. What properties check the indices of these values ​​to be reassembled? Then, look against l, the properties of the indices that you will have to move up to x_l to make the subarray increasing.From this, you can find out what values ​​will take the elements of your sub-array and the number of occurrences of these, which will be used to determine the response to each request (this gives an online solution; I don't know if there is a simpler solution in offline since I found this one directly).I apologize if it's not clear, I'm not really used to giving advice / speaking in English. •  » » » » » We build a new array$B$, where$B[i]$stores$j$, the index of nearest element$A[j]>A[i]$and$j < i$.For query$[L, R]$, we need to update all indices in that range, which have$B[i] <= L$If we build a segment tree over$B$in which each node contains a sorted list of elements represented in the range, we can find the number of indices to update using binary search in$O(Log^2 n)$. But how to get the total increment in the range faster than iterating through the indices we need to update? •  » » » » » » store the prefix sum •  » » One of the approach is that: you find an answer to this question: can you build the segment tree that for each original subarray a[l..r], the corresponding segment in the segment tree contains elements b[l..r] that 1) b[i]>=a[i],i=l..r; 2) b is an increasing array; 3) the minimum cost of obtainting such b. •  » » » I believe that would be not correct. You cannot combine nodes to answer queries that way. •  » » » » Each node includes two vectors that contain "b[i]" values and its prefix sum; it will help to find the answer. Complexity: O(n(logn)^2). •  » » » » » Say$A = [100, 1, 2, 3]$.Then$B = [100, 100, 100, 100]$(increasing array)For query$[3, 4]$, the prefix sum answer would be$(100+100) - (2+3) = 195 $However, correct answer is$0$Please correct me if this is not what you meant in your solution. •  » » » » » » 20 months ago, # ^ | ← Rev. 5 → The prefix sum is to quickly calculate how to merge two non-decreasing subarrays b[l..m] and b[m+1..r] into another non-decreasing subaray c[l..r]; and the cost is$\sum_{m+1\leq m \leq r|b(m)>b(i)} b(m)-b(i)$. And this sum is calculated in O(logn) with prefix sum. Suppose you have the array 10,1,2,20so you will create subarrays like ,,,; and you have four prefix sums 10, 1,2,20 for each subarrays; merging costs are 0. Next, merging them to create subarrays like [10,10] [2,20]; you have other prefix sums [10,20] [2,22] and corresponding min merging cost of each subarray is 0+0+(10-1) and 0+0+0. When merging [10,10] and [2,20], it will create a subarray [10,10,10,20] with cost 9(left child) +0(right child) +8(merging cost) = 17.For your example, if we have only 4 elements; query(3,4)=0 (and it is a node in the segment tree) ; query(2.3) leads to query(2,2)+query(3,3)+merge(2,3)=0+0+0.  » Can I get the link to study your segment tree implementation , I have studied segment tree from CP algorithm site (till Lazy propogation ) •  » » sure. blogPost: https://codeforces.com/blog/entry/71101 incase you are interested in video: https://youtu.be/K-86mKNAsmU •  » » » Thanks , :) •  » » Codeforces do have segment tree tutorial(EDU section), which is really good in my opinion. •  » » » Ohh Okay , I didn't knew about that. •  » » » » Yes.first 6 problems are already discussed in edu section  » Salary Queries could also be solved using C++ PBDS ( It is way more than simple ) Link to my solution , I think it is self explanatory https://ideone.com/HNyjS5  » For Range Xor Queries, you don't need to use a segtree, all you need is a prefix sum array, because just like you use subtraction with range sum queries (because subtraction is the inverse operation of addition), you do xor for range xor queries (because xor is its own inverse operation). •  » » nice observation i had done it using prefix array but lot complex than yours.This one is nice •  » » 16 months ago, # ^ | ← Rev. 2 → HiI did not understand this sentence: you do xor for range xor queries (because xor is its own inverse operation)....Say I have created the prefix sum array for some array [1,2,3,4,5] as [1,3,6,10,15]. Let the query be 2 4. Do you mean to say that I should XOR the elements (3,6,10) of the prefix sum array?By the way, here is my code in Python which gave TLE on CSES site. from functools import reduce n, q = map(int, input().split()) arr = [int(i) for i in input().split()] while q: q -= 1 a, b = map(int, input().split()) print(str(reduce(lambda x,y: x^y, arr[a-1:b]))) #XORing all elements in query range  •  » » » Prefix Xors are basically exactly the same as prefix sums.Instead of psum[i] = psum[i-1]+arr[i-1], do psum[i] = psum[i-1]^arr[i-1] for precalculationInstead of psum[r] - psum[l-1], do psum[r] ^ psum[l-1] for queries.This is because$x \veebar x = 0$, just like$x - x = 0$($\veebar\$ = xor )
•  » » » » Hey thanks a lot for your inputs. I was racking my brains over this for quite some time :)Solution got AC for this code: n, query_count = map(int, input().split()) arr = [int(i) for i in input().split()] #PREFIX XOR ARRAY PRECALC. prefix_XOR_arr = *n for i in range(n): prefix_XOR_arr[i] = prefix_XOR_arr[i-1] ^ arr[i] #QUERY PROCESSING while query_count: query_count -= 1 L, R = map(int, input().split()) if L==1: print(prefix_XOR_arr[R - 1]) else: print(prefix_XOR_arr[R-1] ^ prefix_XOR_arr[L-2]) Had a great time learning about the range queries.
•  » » » » » You got a bit lucky with the fact that Python indices wrap around (so ar[-1] = ar[len(ar)-1]) for the precalculation. It's best to use 1-based indexing for prefix sums (as well as xors) for exactly that reason. Then you don't need the if L==1 case.
•  » » » » » » You're right. I was indeed stuck for some time to think a workaround for a[-1] for I wanted to make it cleaner.Modified it as you suggested (it only increased the prefix array size by 1, that's all). #PRECALC. prefix_XOR_arr = *(n+1) for i in range(1,n+1):prefix_XOR_arr[i] = prefix_XOR_arr[i-1] ^ arr[i-1] #QUERYING print(prefix_XOR_arr[R] ^ prefix_XOR_arr[L-1]) Neater now.
 » 18 months ago, # | ← Rev. 4 →   #include using namespace std; typedef long long ll; ll n; ll rangeXorQuery(vectortree,ll l,ll r) { --l; --r; l+=n; r+=n; ll ans =0; while(l<=r) { if(l&1) { ans = (ans^tree[l]); ++l; } if(r%2==0) { ans = (ans^tree[r]); r--; } l/=2; r/=2; } return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int q; cin>>n>>q; ll a[n]; vectortree(2*n); int i; for(i=0;i>a[i]; tree[i+n] = a[i]; } for(i=n-1;i>=1;i--) { tree[i] = (tree[2*i]^tree[2*i + 1]); } while(q--) { ll l,r; cin>>l>>r; cout<
•  » » done by in o(n) time by implementing the fact that only odd number of one's count will contribute to the ans making a 2d arry for frequency of bits starting to end and check for(i=0;i<32;i++) if different btw prefix[r][i] — prefix[l-1][i] is odd then i th bit will contribute to the ans
•  » » Please format the code better, use triple backticks to surround the code, and put 'cpp' right after the beginning backticks.
•  » » » done,thanks for telling me i don't actually know how that works
•  » » » » No like this: cpp Your code here...  
•  » » » » » now done
 » For Distinct Value Queries, there's no need to overcomplicate the problem by using Mo's Algorithm. Since there's no update operations, you can simply sort the queries by endpoint, and use a sweepline by activating the most recent processed index. AC Code#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #pragma GCC optimize ("Ofast") #pragma GCC target ("avx2") using namespace std; #include #include using namespace __gnu_pbds; // data types typedef long long ll; typedef pair pii; typedef pair piii; typedef pair pll; typedef pair plll; #define fixfloat(d) fixed << setprecision(d) template using ordered_map = tree, rb_tree_tag, tree_order_statistics_node_update>; template using ordered_set = ordered_map; // constants const int inf = 2000000011; const ll llinf = 9223372036854775800; const int MOD = 1e9 + 7; const double PI = acos(-1); // macros #define PB push_back #define MP make_pair #define FF first #define SS second // hash struct chash { const uint64_t C = ll(2e18*PI)+71; const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count(); ll operator()(ll x) const { // https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html return __builtin_bswap64((x ^ RANDOM) * C); } ll operator()(pii p) const { return __builtin_bswap64((p.FF ^ RANDOM) * C) + p.SS; } }; template using fast_map = gp_hash_table; template using fast_set = gp_hash_table; // helper functions inline ll ceil0(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } inline ll floor0(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); } ll pow0(ll a,ll b) { ll res = 1; for (a %= MOD; b; b >>= 1) { if(b & 1) res = res * a % MOD; a = a * a % MOD; } return res; } void printl() {} template void printl(T a, Tail... b) { cout << a; printl(b...); } bool comp(piii a, piii b) { return a.FF.SS < b.FF.SS; } int N, Q, A, T, ans; piii R; fast_map M; void update(int u, int v) { for (T[u += N] = v; u > 1; u >>= 1) T[u >> 1] = T[u] + T[u ^ 1]; } int query(int l, int r) { int res = 0; for (l += N, r += N; l < r; l >>= 1, r >>= 1) { if (l & 1) res += T[l++]; if (r & 1) res += T[--r]; } return res; } int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); // freopen(FILE_NAME, "r",stdin); // freopen(FILE_NAME, "w",stdout); cin >> N >> Q; for (int i = 0; i < N; i++) cin >> A[i]; for (int i = 0, l, r; i < Q; i++) { cin >> l >> r; R[i] = MP(MP(l - 1, r - 1), i); } sort(R, R + Q, comp); for (int i = 0, j = 0; i < N; i++) { if (M.find(A[i]) != M.end()) update(M[A[i]], 0); M[A[i]] = i; update(i, 1); while (R[j].FF.SS == i) { ans[R[j].SS] = query(R[j].FF.FF, R[j].FF.SS + 1); j++; } } for (int i = 0; i < Q; i++) cout << ans[i] << '\n'; } 
 » 16 months ago, # | ← Rev. 2 →   I tried solving the "Salary Queries" problem using segment tree + coordinate compression as mentioned in the editorial. Not sure why it is giving TLE (output is correct). I tried to run with those inputs locally and I got around 1.15s (max) with the g++-11 compiler. Link to my code: https://cses.fi/paste/b1847e301c31fc16238359/ Any idea where am I going wrong?
 » I am getting TLE for this problem CSES Prefix Sum QueryMy SolutionDo I need to use Lazy Propagation for update query?
 » For Range Xor Queries, we can solve it using a prefix array too, just like we did in the case of Range Sum Queries I.
 » you save my day!!
 » For Range Xor Queries you do not need a segment tree. You can implement it directly y prefix array technique. This is only because values of array are not going to change. So here we have important property of xor that (a xor a) = 0 so by prefix technique find prefix xor for whole array by prefix[i] = prefix[i-1]^arr[i] Then for queries simply print (prefix[l-1]^prefix[r]) as your answer cause xor of all numbers in range l to r when we xor prefix[r] and prefix[l-1] the first l-1 numbers automatically are twice xor cause prefix[r] = xor of numbers from(l to r) ^ prefix[l-1] so thats how it can be done in O(n).
 » PROBLEM : Salary Queries After updating any X to Y shouldn't the update be like this : Freq[X] -= 1,Freq[Y] += 1
 » in salary queries problem, you also can compress all values in n*log(n) time;
 » kartik where are the last two problems editorial please add it
 » Need help with Task: Salary Queries [TLE + WA]My code : https://ideone.com/SDqjOP ApproachPoint compression on all distinct values of salaries; including initial salaries, updates and query ranges. Maintain a segment tree to store the frequency of each salary. Updates and queries work in O(log(N)), where N is the nearest power of 2 equal to or greater than (n + 2q).
 » 2 months ago, # | ← Rev. 3 →   Code#pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef long double ld; typedef pair p32; typedef pair p64; typedef pair pdd; typedef vector v64; typedef vector v32; typedef vector > vv32; typedef vector > vv64; typedef vector > vvp64; typedef vector vp64; typedef vector vp32; double eps = 1e-12; #define forn(i,e) for(ll i = 0; i < e; i++) #define forsn(i,s,e) for(ll i = s; i < e; i++) #define rforn(i,s) for(ll i = s; i >= 0; i--) #define rforsn(i,s,e) for(ll i = s; i >= e; i--) #define ln "\n" #define dbg(x) cout<<#x<<" = "< void swp(T&a,T&b) { T temp=a; a=b; b=temp; } // Useful Funcs // smallest prime divisor // int smp={0}; // void calcPrimes(){ // forn(i,100001){ // smp[i]=i; // } // ll ct=2; // while(ct*ct<100001){ // if(smp[ct]==ct){ // for(ll j=ct*ct;j<100001;j+=ct){smp[j]=ct;}} // ct+=1; // } // } ll ceil_div(ll a, ll b) {return a % b == 0 ? a / b : a / b + 1;} // Recursive function to calculate gcd long long gcd(long long a, long long b){ if(b==0) return a; return gcd(b,a%b); } /* Iterative Function to calculate (x^y)%p in O(log y) */ long long modex(long long x, unsigned int y, long long p) { long long res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p if (x == 0) return 0; // In case x is divisible by p; while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res*x) % p; // y must be even now y = y>>1; // y = y/2 x = (x*x) % p; } return res; } int binarySearch(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r — l) / 2; // If the element is present at the middle // itself if (arr[mid] == x) return mid; // If element is smaller than mid, then // it can only be present in left subarray if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); // Else the element can only be present // in right subarray return binarySearch(arr, mid + 1, r, x); } // We reach here when element is not // present in array return -1; } // STL binary search functions // binary_search(start_ptr, end_ptr, num) // returns true if element present, // otherwise returns false. // upper_bound(start_ptr, end_ptr, num) // returns the first index having value // greater than num. // If there is no such index, then returns // length of array. // lower_bound(start_ptr, end_ptr, num) // returns the fiirst index having value // not less than num // Subtract v.begin() or a(in case of array) to get index. // Pointers // for array-> a, a+x // for vector-> v.begin(), v.begin()+x, v.end() const ll MOD = 998244353; const ll mod = 1e9+7; ll create(v64 & v, v64 &st, ll ss, ll se, ll si){ if(ss==se){ st[si]=v[ss]; return st[si]; } ll mid = ss+(se-ss)/2; st[si]=create(v,st,ss,mid,2*si+1)+create(v,st,mid+1,se,2*si+2); return st[si]; } void update(v64 &v, v64 &st, ll ss, ll se, ll si, ll dif, ll x){ if(se>n>>q; v64 v(n); forn(i,n) cin>>v[i]; vector>> qr; set pts; forn(i,q){ char x; ll a, b; cin>>x>>a>>b; qr.pb({x,{a,b}}); if(x=='?'){ pts.insert(a); pts.insert(a-1); pts.insert(b); } } pts.insert(1000000000); v64 mn; for(auto x:pts){ mn.pb(x); } ll h=(int)(ceil(log2(mn.size()))); ll m = 2*pow(2,h)-1; v64 st(m,0); v64 cum(mn.size()); forn(i,n){ ll a = lower_bound(mn.begin(),mn.end(),v[i])-mn.begin(); cum[a]+=1; } // // for(auto i:cum){ // // cout<