When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Fype's blog

By Fype, 4 years ago, In English

I gathered up a lot of Segment problems :) -->

upd1 : more segment :D
upd2 : now there is e-olymp problems. thanks to dmkz.

codeforces :
Xenia and Bit Operations
Knight Tournament
Bash and a Tough Math Puzzle
Pashmak and Parmida's problem
Enemy is weak
Circular RMQ
REQ
Lucky Queries
XOR on Segment
Sereja and Brackets
Ant Colony
Babaei and Birthday Cake
A Simple Task
Frogs and mosquitoes
Copying Data
Lucky Array
Vika and Segments
Misha and Permutations Summation
Little Elephant and Inversions
One Occurrence
Optimize!
Yaroslav and Divisors
TorCoder
New Year Domino
Pillars
On Changing Tree
Infinite Inversions
Interesting Array
Alphabet Permutations
DZY Loves Fibonacci Numbers
Points
Function
Eyes Closed
Tree and Queries
Valera and Queries
Nikita and stack
Linear Kingdom Races
Camping Groups
Little Girl and Problem on Trees
Domino Principle
Water Tree
Propagating tree
Kefa and Watch
Jeff and Removing Periods
Drazil and Morning Exercise
Subsequences
SUM and REPLACE
Tree or not Tree
The Child and Sequence
Encryption (hard)
Hot is Cold
Developing Game
Drazil and Park
Board Game
The Untended Antiquity
Danil and a Part-time Job
More Queries to Array...
Cow Tennis Tournament
Coins Exhibition
Till I Collapse
Editor
Serge and Dining Room
Subarray Sorting
Physical Education Lessons
Alyona and towers
Sasha and Array
New Year and Old Subsequence
Timofey and our friends animals
Souvenirs
Yash And Trees
Legacy
Periodic RMQ Problem
Leha and security system
Vladik and Entertaining Flags
MEX Queries
The Bakery
Nauuo and Bug
Duff in the Army
Fools and Roads

codeforces gym :
Queries
Letter Array
Hacker Cups and Balls
Reflection
Rectangles
Colonial Mansions
Colors Overflow
Running a penitentiary
Subsequence Sum Queries

spoj :

BGSHOOT — Shoot and kill
HORRIBLE — Horrible Queries
GSS1 — Can you answer these queries I
GSS3 — Can you answer these queries IV
GSS5 — Can you answer these queries V
KGSS — Maximum Sum
POSTERS — Election Posters
BRCKTS — Brackets
LITE — Light Switching
KQUERYO — K-Query Online
CNTPRIME — Counting Primes
MULTQ3
IOPC1207 — GM plants
QUERYIT — SLIS
ADACABAA — Ada and Species
DQUERY — D-query
PATULJCI — Snow White and the N dwarfs
ADAGF — Ada and Greenflies
ADATREE — Ada and Trees
Mass Change Queries
PRMQUER — Prime queries
NAJ0001 — Divisible Number Sum
DCEPC11I — Impossible Boss
PERMPATT — Check 1324
THRBL — Catapult that ball
MON2012 — Monkey and apples
GOODE — Good Debugging SBO — MAXIMUM RARITY

lightoj :

1082 — Array Queries
1080 — Binary Simulation
1112 — Curious Robin Hood

e-olymp :
In the Country of Unlearned Lessons
In a country of Unlearned Lessons 2
The kid who learned to count
Investigation by koloboks
Цветик-Семицветик
Cheburashka and Crocodile Gena
Винни-Пух
Винни-Пух 2
Карлсон, который живет на крыше
Ну, погоди!
Three from Prostokvashino
Трое из Простоквашино 2
Трое из Простоквашино 3
Золотой ключик или приключения Буратино
Приключения кота Леопольда
Adventures of Dunno and His Friends
38 попугаев
Возвращение блудного попугая
Сказка о попе и работнике его Балде
Чипполино
you can use google translate for the problems written in russian.

any suggestion ? :D

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

| Write comment?
»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

any suggestion ? :D
Remove "advance data structures" tag.
Segment tree is way away from advance data structures.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
4 years ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

One more: 1172F - Nauuo и ошибка

BTW, I think it would be better if you sort these problems by difficulties, or classify them into different types, like this blog.

And do you choose all the problems which are solvable by segment tree, even if there are both faster and easier solutions? I've noticed that 516C - Drazil и парк only needs RMQ, and 516D - Drazil и утренняя зарядка's official solution doesn't need any advanced data structures (I don't think union-find-set is), however, I have a solution using segment tree with worse complexity ($$$O(qn\log^2 n)$$$) but less observation, does this make it a segment tree problem? Or there are faster segment tree solutions?

UPD: seems that these two problems are from this blog.

  • »
    »
    4 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Thanks, the problem added to the list.

    When you are unfamiliar with the segment tree it's better to solve the problem using the segment tree even if there is a better time-complexity because you will understand different usage of the segment tree. (At least that's what I believe)

    I never came across a faster solution for 516D.

»
4 years ago, # |
  Vote: I like it -11 Vote: I do not like it

+

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody help me with the SPOJ-PERMPATT problem? I saw people building segment trees for finding minimum element but there should be one more idea i cannot catch.

»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Other problems can be solved by Segment Tree: 1070C - Cloud Computing, 900C - Уберите лишнего. Bonus: 1795E - Взрывы? (this problem can be solved with other shorter solutions, but we can use Segment Tree as a practice)