thanks for the link. It was helpful.

thank you for this. I was looking for a simpler problem on segment tree.

Umm... right now it can't be seen in english, which I believe most of us need, it would be great to show it like this: [problem code] [english name] / [russian name]

A little bit late ;-) Yes, it is possible to solve it with a segment tree. But instead of updating a single value and querying for ranges, you have to invert it so that you can modify an interval and get access to each element. Additionally you have to make sure that you insert the fights in the reversed order, otherwise some fights will overwrite others. Here is my implementation: 23198751

Thank YOU :)

That's overkill. There exists an easier and faster solution for that problem.

Thanx it was really helpful.

No hints there :'(

I solved it using Lazy Propagation, I couldn't find a way without it, I join the request for a non-lazy-propagation solution.

1 Let's use coordinate compression on a[i]. Then we have all the a[i] in the range (0, N].

2 Let's create new array b[MAXN].

b[i] — amount of j what a [j] > a [i] and j < i.

It can be done with Fenwick or Segment tree.

for (int i = 1; i <= n; i++){
  b [i] = get (a[i] + 1, n);
  upd(a [i], 1); 
}

3 Answer will be sum of d [i].

d[i] — sum of all b [j] what j < i and a [j] > a [i].

for (int i = 1; i <= n; i++){
  d[i] = get (a[i] + 1, n);
  upd(a [i], b [i]);
}

Sorry For My English

Use BufferedReader and PrintWriter

Do you need lazy propagation? That was my idea in-contest but couldn't implement it right.

Combi don't comment it.The person who comment it is Flying_Dragon_02

sorry everyone!! I forget to log out so Flying_Dragon_02 can say something.... it's not good. We're just student. This topic's very good for me because I need to improve my skill in IT

I solved it using merge sort tree. Needed a little bit of optimization though.

For every query of type 1, calculate the amount of shift needed towards right (this will be x-y). Example: 1 5 12 16. Shift needed towards right is 5-12 = -7. So here our query starts at y-1(index is 0-based) and ends at y+k-1. For a query range shift is same for all the indices. Imagine here indices 11 to 26 are shifted towards right by -7(therefore towards left by 7).

Our segment tree will contain two variables in every node:

1. The shift of the segment

2. -1 or 0 denoting the segment has been overwritten by array 'a', 0 if not.

Query will be of two types:

1. Update a range[qs, qe]

2. Answer what is b[x]

Lazy propagation works here. At the start of both the queries if the second value of the node is -1 pass the first value to both its children(if they are present) and set both the values of the node equal to 0. Query type 2 returns two variables: the shift; and, the second value of the node(-1 or 0). If it's -1 ans is a[shift+x] else b[shift+x], x should be adjusted to 0-based index. Note: If the second value of a node is 0, first value(the shift of the segment) is always 0.

Link to the code: http://codeforces.com/contest/292/submission/39273711

https://codeforces.com/blog/entry/325