E-maxx training part - 04

Minimum stack / Minimum queue

Implementation 

Sparse Table

RMQSQ - Range Minimum Query   SOLUTION

THRBL - Catapult that ball

Matchsticks

Sereja and D

D. CGCDSSQ

D. R2D2 and Droid Army

B. Maximum of Maximums of Minimums

TNVFC1M - Miraculous

DCP-19: Multiplication Interval

D. Animals and Puzzle

E. Trains and Statistic

POSTERIN - Postering

RPLN - Negative Score

CITY2 - A Famous City

DIFERENC - DIFERENCIJA

E. Turn Off The TV

D. Map

E. Awards For Contestants

C. Longest Regular Bracket Sequence

Disjoint Set Union

1671. Anansi's Cobweb 

D. Roads not only in Berland 

1003. Parity 

CHAIN - Strange Food Chain 

CLFLARR - COLORFUL ARRAY 

Fenwick Tree

12086 - Potentiometers

1112 - Curious Robin Hood

1266 - Points in Rectangle

Gravel

CTRICK - Card Trick

MATSUM - Matrix Summation

DQUERY - D-query

NKTEAM - Team Selection

YODANESS - Yodaness Level

SRM 310 - FloatingMedian

ADABEHIVE - Ada and Behives

Counting In Byteland

DCP-300: Shan and String

E. Little Artem and Time Machine

E. Hanoi Factory

TULIPNUM - Tulip And Numbers

SUMSUM - Enjoy Sum with Operations

SGIFT - Sabbir and gifts

TPGA - The Permutation Game Again

ZIGZAG2 - Zig when you zag

CRAYON - Crayon

DCEPC705 - Weird Points

DCEPC206 - Its a Murder!

KOPC12G - K12-Bored of Suffixes and Prefixes

TRIPINV - Mega Inversions

C. Subsequences

D. Ball

J. The Kamphaeng Phet's Chedis

E. Garlands

E. Inversions After Shuffle

D. Cairo Market

E. Goodbye Souvenir

ADACABAA - Ada and Species

A. Thor

F - Fundraising

Sqrt Decomposition

UVA - 12003 - Array Transformer    SOLUTION

UVA - 11990 Dynamic Inversion   SOLUTION

GIVEAWAY 

C. Till I Collapse 

D. Destiny 

E. Holes 

E. XOR and Favorite Number 

D. Powerful array      SOLUTION

DQUERY 

Segment Tree

Treap (Cartesian tree)

ADAAPHID 

ADACROP 

E. Radio stations 

COUNT1IT 

IITWPC4D 

ALLIN1 

D. Dog Show 

D. Yet Another Array Queries Problem   SOLUTION

MEANARR 

TWIST 

KOILINE 

PRESTIGE 

Sqrt Tree

Product on the segment by modulo 

Editorial: 1 2 3

 

Deleting from a data structure in O(T(n)logn) 

A. Connect and Disconnect 

E. Addition on Segments 

F. Extending Set of Points        SOLUTION

 

 

 

 

 

Share:

Read More

Sparse Table

Note: Sparse Table is a data structure, that allows answering range queries. It can answer most range queries in O(logn), but its true power is answering range minimum queries (or equivalent range maximum queries). For those queries it can compute the answer in O(1) time.

The only drawback of this data structure is, that it can only be used on immutable arrays. This means, that the array cannot be changed between two queries. If any element in the array changes, the complete data structure has to be recomputed.

Rsources:

Tanvir's Blog

E-maxx 

 GeeksForGeeks

HackerEarth 

Tushar Roy Video 

 Topcoder

Codechef

adilet.org_blog_sparse-table 

Implementation: according to (This )  problem 

 

Share:

Read More