I_love_Jiang's blog

By I_love_Jiang, history, 7 years ago, In English

Hi everybody !

I've learn to use Fenwick Tree for a long time but recently I perceive I didn't use it optimally.

So I have some question about Fenwick Tree, I need your help :

1, Can we use Fenwick Tree for min-max query for an inteval array;

2, Can we use it as a Dynamic Fenwick Tree with number of nodes not exeed 1e9 and how to.

3, Can we one Fenwick Tree for two usages: sum and min or sum and max.

They maybe fool questions, please help me if you can !!

Sorry because of my poor English !!

Full text and comments »

  • Vote: I like it
  • +9
  • Vote: I do not like it

By I_love_Jiang, history, 7 years ago, In English

Can somebody please explain how dynamic binary index trees work and give me an implementation, I would appreciate your help!

I meet some dificult in coding it !

Sorry about my pour English !

Thanks in advance! :)

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By I_love_Jiang, history, 8 years ago, In English

Link of the problem :http://www.spoj.com/problems/TOINCSEQ/

In short: You are given a sequence of non-negative integers a1, a2, …, an. You are allowed to perform some operators on the sequence. Each operator consists of 2 steps: choosing an arbitrary value, then increasing (or decreasing) all elements of the selected value in the current sequence by 1.

For example, the sequence 1 9 9 2 2 will become 1 9 9 3 3 if you decide to increase all elements of value 2.

What is the minimum number of operators does it take to make the given sequence a non-decreasing sequence?

Input

The first line consits of an integer N, the number of elements in the sequence. The second line consists of N elements of the sequence. Output

The mininum number of operators needed to make the sequence non-decreasing. Example

Input: 5

1 9 9 2 2

Output: 7 Constraints

1 ≤ N ≤ 10^5. Each element of the sequence is a non-negative integer not exceeding 10^9. ***************************************************************************

I think we can uses DP but I had no idea then.

Help me please !!!

Full text and comments »

  • Vote: I like it
  • -3
  • Vote: I do not like it