Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### cjtoribio's blog

By cjtoribio, history, 4 years ago,

## Motivation & Problem

Recently saw this problem. For some this problem might seem like a segment tree problem and it is indeed one. However this problem and others where segment tree does not apply can be solved using another approach. I will rephrase the problem in a simpler way. We want a data structure capable of doing three main update-operations and some sort of query. The three modify operations are:

remove: Remove an element from the set.

updateAll: This one normally changes in this case subtract X from ALL the elements. For this technique it is completely required that the update is done to ALL the values in the set equally.

And also for this problem in particular we may need one query:

getMin: Give me the smallest number in the set.

Observing this operations we want to handle, SegmentTree seems legit except for the remove, but we can wave it around by assigning INF to the position we want to remove. However if we don't have the updateAll then we can just use a MULTISET. And in fact if the remove is only to the minimum element then we can use a HEAP. However the four operations without any "workaround" can only be managed by a DynamicSegmentTree which in fact exists but is like using a bazooka to kill a simple mosquito.

## Interface of the Data Structure

struct VeniceSet {
void remove(int);
void updateAll(int);
int getMin(); // custom for this problem
int size();
};


## Usage of this methods

So imaging we have this four operations, how can we tackle this problem with it. Well i will illustrate it with a simple code in C++ which i hope is self explanatory.

VeniceSet mySet;
for (int i = 0; i < N; ++i) {
mySet.updateAll(T[i]); // decrease all by T[i]
int total = T[i] * mySet.size(); // we subtracted T[i] from all elements

// in fact some elements were already less than T[i]. So we probbaly are counting
// more than what we really subtracted. So we look for all those elements
while (mySet.getMin() < 0) {
// get the negative number which we really did not subtracted T[i]
int toLow = mySet.getMin();

// remove from total the amount we over counted
total -= abs(toLow);

// remove it from the set since I will never be able to substract from it again
mySet.remove(toLow);
}
cout << total << endl;
}
cout << endl;


## Implementation of the Technique

As the title says I don't call it a data structure itself but this is a technique almost always backed up by a data structure. And now I am going to explain why I call it Venice technique. Imagine you have an empty land and the government can make queries of the following type: * Make a building with A floors. * Remove a building with B floors. * Remove C floors from all the buildings. (A lot of buildings can be vanished) * Which is the smallest standing building. (Obviously buildings which are already banished don't count)

The operations 1,2 and 4 seems very easy with a set, but the 3 is very cost effective probably O(N) so you might need a lot of workers. But what if instead of removing C floors we just fill the streets with enough water (as in venice) to cover up the first C floors of all the buildings :O. Well that seems like cheating but at least those floor are now vanished :). So in order to do that we apart from the SET we can maintain a global variable which is the water level. so in fact if we have an element and want to know the number of floors it has we can just do height - water_level and in fact after water level is for example 80. If we want to make a building of 3 floors we must make it of 83 floors so that it can tough the land. So the implementation of this technique might look like this.

struct VeniceSet {
multiset<int> S;
int water_level = 0;
S.insert(v + water_level);
}
void remove(int v) {
S.erase(S.find(v + water_level));
}
void updateAll(int v) {
water_level += v;
}
int getMin() {
return *S.begin() - water_level;
}
int size() {
return S.size();
}
};


## Variations

#### Trick With Trie

Probably you have seen a problem of having a set of numbers and handle queries such as what is the greatest XOR than can be achieved by using one number of the set and the given number. This can be handled with a BinaryTrie. However if we add the operation XOR all the numbers in the set this would be very heavy. But if we maintain a global water_level that would XOR any number in and any number out, then it would virtually be XORING all the numbers in the set. Don't have an example problem yet, but I know I have used it, so any is welcome.

So as my experience is, this technique is a lightweight modification that can be applied to all DataStructures that support (add, remove and query) and only need the operation (updateAll).

## Other Approaches For This Problem

Binary Search: This is very fast and simple, however is an offline solution. (Not apply for other operations such as sort)

Event Processing: Easy to code and fast but still offline and does not apply for other operations such as XOR.

Dynamic Segment Tree: A little slow in practice, same complexity in theory, and requires heavy code. This is online but requires heavy code. (Dynamic means can insert and delete nodes from the segment tree). Does not apply to other variations of the problem such as XOR.

Implicit Segment Tree: Relativly easy to code, but theoretical complexity of Nlog(MAXVAL) and still requires this technique to work. (Does not apply to other variations such as XOR)

## Example Problems

• +80

 » 4 years ago, # |   +73 Great article, but I usually use Pasha Technique.
•  » » 4 years ago, # ^ |   +3 Mmmh really good to know, could you describe it a little bit or point at some code using it? Is just to know all other approaches and point it out in the article. Thanks.
•  » » 4 years ago, # ^ |   +23 What's Pasha Technique?
•  » » » 4 years ago, # ^ |   0 its russian hero
•  » » 4 years ago, # ^ |   +9 Wish I could upvote twice
•  » » » 4 years ago, # ^ |   -24 this kid looks like trash
 » 4 years ago, # | ← Rev. 2 →   -40 Great article! Surely helps gray coders like me become better at problem solving. :pEDIT: I was being purely honest with the comment. No need to downvote.
 » 4 years ago, # | ← Rev. 3 →   +8 Shouldn't the correct code be like this? void remove(int v) { S.erase(S.find(v + waterlevel)); } int getMin() { return *S.begin() - waterlevel; } Otherwise you sometimes need to handle the water_level manually (min, remove), and sometimes not (add), which would be really strange.
•  » » 4 years ago, # ^ |   0 You are right, i am fixing it. thanks
 » 4 years ago, # |   0 Auto comment: topic has been updated by cjtoribio (previous revision, new revision, compare).
 » 4 years ago, # |   0 Nice analogy. It would be useful some links to problems using this technique or data structures using it too ... anybody ???
•  » » 4 years ago, # ^ |   +1 You may try the following: BDOI16E
•  » » » 4 years ago, # ^ |   0 Hmm the problem seems interesting. I'm still trying to find a solution applying the technique. Can you give some hint ?? Thanks for the link!!!
•  » » » » 4 years ago, # ^ |   +1 HintDSU on Tree (Small to large set merge trick)Not sure if I overkilled it though
•  » » » » » 4 years ago, # ^ |   0 That's what i was using to solve it, and not sure if i over-killed too. I was thinking in a simpler solution (like using the technique discussed here only or something). Thanks !!!
 » 4 years ago, # |   0 Cool. Trick
 » 4 years ago, # | ← Rev. 2 →   -29 Coulda simply used bitset LOL xD lulzUPD: Sorry, at first I thought this was a troll post. I didn't intend to offend anybody.
 » 4 years ago, # |   0 I also did a similar thing during the contest. I used a dynamic segment tree but instead of performing lazy propagation for update all I used similar technique of maintaining a level. Link to my submission : http://codeforces.com/contest/948/submission/36168355 In the code anss contains the current level.
 » 4 years ago, # |   0 But you can't remove buildings in civ, not even when playing Venice.
 » 4 years ago, # |   0 In the trie variation, what is the benefit of keeping the XOR of all numbers in the set???
•  » » 4 years ago, # ^ |   0 You dont have a XOR of all the numbers in the set you just have a lazy XOR that you want to apply to all the elements in the set. Instead of applying to the numbers you apply to each query you are asked, as we does with the ADD.
 » 4 years ago, # |   0 Nice tutorial! GOOD JOB!!!
 » 4 years ago, # |   +5 I've used this before but never knew it had a name.http://codeforces.com/problemset/problem/893/DVenice technique + prefix sums
•  » » 4 years ago, # ^ |   0 I made the name up. Definitely a lot of tricks have no name and that is why it is hard to find articles about it :(. That is why I wanted to come with one in case people want to adopt that name or at least put another one.
•  » » » 4 years ago, # ^ |   +69 What if some simple tricks, like "let's store one variable with global shift", don't need any names and articles, because it's very intuitive for specific task, and one sentence can fully describe this trick?
•  » » » » 4 years ago, # ^ |   +8 It adds an element of humor. E.g. the Trump technique would be related to tweeting
 » 4 years ago, # |   0 D. Vitya and Strange LessonAn example problem for Trie variation.
 » 4 years ago, # |   0 What is Event Processing? When I google it, I can't find any information related to competitive programming.
 » 4 years ago, # | ← Rev. 2 →   -13 .
 » 4 years ago, # |   0 Can you please share your codes for the example problems using this technique.
•  » » 4 years ago, # ^ |   +15 This is my code for the problem suggested by mahmud2690 BDOI16E. It combines two techniques as discussed above. codevoid dfs(int p, int u) { for(auto v : G[u]) { if(v != p) { dfs(u, v); } } // init F[u] = 0; // merge for(auto v : G[u]) { if(v != p) { // Sum joy gain to child set F[v] += jplus[v]; // Small-to-Large technique if(joys[u].size() < joys[v].size()) { swap(joys[u], joys[v]); swap(F[u], F[v]); } // Applying venice technique on merge for(auto val : joys[v]) { ll nval = val + F[v]; joys[u].insert(nval - F[u]); } } } // Insert root joys[u].insert(J[u] - F[u]); // ans ans[u] = joys[u].size(); }
•  » » » 4 years ago, # ^ |   0 Thanks :)
•  » » 4 years ago, # ^ |   +2 This is my code for the other problem suggested by Omar_Elawady. Although the hardest part is getting the mex. Solutionstruct MexTrie { struct Node { Node* child[2]; int cnt; Node(): cnt(0) { child[0] = child[1] = NULL; } }; Node *root; MexTrie() { root = new Node(); } void insert(int x) { if (exists(x)) return; Node *v = root; v->cnt++; for (int i = 30; i >= 0; --i) { int b = (x >> i) & 1; if (v->child[b] == NULL) v->child[b] = new Node(); v = v->child[b]; v->cnt++; } } bool exists(int x){ Node *v = root; for (int i = 30; i >= 0; --i) { int b = (x >> i) & 1; if (v->child[b] == NULL) return false; v = v->child[b]; } return true; } int mex(int x) const { Node *v = root; int m = 0; for (int i = 30; i >= 0; --i) { int b = (x >> i) & 1; if (v->child[b] == NULL) return m; if (v->child[b]->cnt == (1<child[b] == NULL) return m; v = v->child[b]; } // should never reach here assert(false); } }; struct VeniceSet { int globalX = 0; MexTrie T; void insert(int x) { T.insert(x); } void xorAll(int x) { globalX ^= x; } int getMex() { return T.mex(globalX); } }; `
•  » » » 4 years ago, # ^ |   0 Thanks :)