| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 160 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | Dominater069 | 154 |
| 8 | awoo | 154 |
| 10 | luogu_official | 151 |
Greetings.
I was trying to solve one problem, but couldn't. It's like the RMQ problem but with add at position operation.
There are 2 operations:
ADD i X ---- ads X after ith element.
QUERY l r ---- RMQ of [l; r].
Can someone help me, please? Thanks in advance.
(Sorry bad English)
EDIT: Thanks everybody for help! Got accepted :)
Can you solve this problem?
Couldn't :(
Can you explain your approach.
Use a segment tree, and in addition to storing the RMQ, store the size of the un-deleted nodes.
Then you can answer those queries by walking the tree. To remove an element, set its value to 0 (or ∞) and decrease its size by 1.
Do you see how to reduce the original problem to this problem?
Got the task for deleting, but how to reduce the original problem?
Do all "Add" queries, go in reversed order, if the current query is adding set the val of i + 1th element to INF, increase all numbers of of array d from 1 to i + 1 by 1, if the query is rmq, then get the rmq between l and r + d_r
Say, the original array is A[] . Find the total number of elements that would be added between every two original A[] elements . Make an array B[] of size total elements of final array such that B[0] = A[0], B[0 + AddedBetween(0, 1)] = A[1] and so on and fill the values in between according to the queries which is easy to do... Now make a RMQ segment tree that also stores the number of deleted elements in the interval (L,R) . So While querying for RMQ you would actually do RMQ(L, R + deleted(L, R)) to get the answer.
This was for reduction to the solution mentioned in the comments.
Sorry, I think your solution is wrong. You said RMQ ( L, R + deleted (L, R )), you don't know whether exist more deleted numbers between (R, R +deleted (L,R)).
I hope you understand what I told you :)
Thanks! How to reduce it using segtree as zxqfl mentioned then ?
I wrote down my solution, you can see it. I use binary search and BIT, maybe exist something smarter :)
I can modify my method by finding smallest X using binary search such that undeleted(R,R+X) = deleted(L,R) and then do query(L,R+X) . Maybe this would work.
You can know the position of every added element by using seg tree and greedy sol somehow.
So you have the whole array with nrelem+nr added full of 1,and for the last add you surely know that the (i+1)th elem is the position for the last added.Ok ,we make 0 at that position,and we have 1 in seg tree just for the remaining elements.(we do this in reverse order)
Now the position of the next added element is the position of the (i+1)th 1 in seg tree,and this can be found easy,just a normal query function.We make 0 at that position and so on.You see?
Now that we know all positions, we can answer easily to queries with another seg tree.
I don't know if seg tree works for all possible use of rmq(like gcd), because you don't know what to put at positions which are not occupied at the moment so that it doesn't change the answer.
There is also an sqrt-deomposition solution that our good friend MirceaFF didn't mention. We can divide into sqrt segments. When an element comes, you see the bucket where he belongs and put it there, for this of course we will use sqrt Queues. And from sqrt to sqrt Updates we kind balance the buckets because some of them will become too big. When [l,r] comes, we take the maximmum from the whole buckets and the rests from the other possible 2 buckets. o(m * sqrt(n+m)). But of course FF's solution is good and quite intuitive too, you just solve the queryes and updates backwards.
Auto comment: topic has been updated by arbcrt040 (previous revision, new revision, compare).
Could you please give me the link of this problem?
It can be solved using treaps or using SQRT decomposition
Could you please explain how is it the solution using treaps?
http://threads-iiith.quora.com/Treaps-One-Tree-to-Rule-em-all-Part-2
Wow, that's an amazing tutorial. Thank you very much.
I also would like to know the solution using sqrt decomposition. Could someone please explain me?
We will build sqrt decomposition on our array;
Then after insert operation we will just insert in needed block new element;
After every sqrt inserting operations we will rebuild our decomposition;
RMQ is same as in simple sqrt decomposition;
Here is my code
I don't understand solution wtih seg. tree ( I don't get up, how we can find interval [L,R] in O(1)...
I'll write my solution, I think that is correct:
We can solve it with BIT + binary search + seg. tree. At first we find how many numbers we will add between any two number in starting array. After that we put everything in BIT ( if we haven't added some element yet we write 0, else we write 1). For the first query we update seg. tree and BIT ( in bit for updated position in array we write 1, in seg. tree we change node value for that position from inf to x). For the second query we find needed interval with binary search in BIT, after that we use RMQ in segment tree and find answer :)
Can you tell me, how I can solve it without BIT ?
You can use another segment tree insead of BIT, then binsearch won't be needed. Just traverse tree from the root. Then you can find interval [L,R] in O(log) instead of O(log^2).
But in practice BIT+binsearch is really fast, even can be faster than segment-tree.