A data structure problem ?
Difference between en8 and en9, changed 0 character(s)
Given a constant $s$, an array of $n$ non-negative integers and you have to process $q$ queries of following types : ↵
↵
1. $l \ r \ b$ : for each $i$ in range $[l, r]$, if $a[i] < b$ let $a[i] = s - a[i]$↵
2. $l \ r \ b$ : for each $i$ in range $[l, r]$, if $a[i] > b$ let $a[i] = s - a[i]$↵
3. $i$ : return the current value of $a[i]$ ↵
↵
$1 \leq n, q \leq 5.10^5$↵
$1 \leq s, b \leq 10^7$↵
↵
Time limit : 2.5s↵
Memory limit : 512 mb↵
↵
I'm trying to solve the easier problem when all the updates appear before the queries, but I still can't;↵
I don't have any approach for this problem yet, can anyone give me some hints or something ?↵
Sorry for bad English :( ↵
Thanks :)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English I_Love_AnhThu 2024-08-24 14:00:58 0 (published)
en8 English I_Love_AnhThu 2024-08-24 14:00:43 3 Tiny change: 'n$1 \leq s \leq 10^7' -> 'n$1 \leq s, b \leq 10^7'
en7 English I_Love_AnhThu 2024-08-24 13:59:48 2 Tiny change: 't : 2.5s\n\nMemory l' -> 't : 2.5s\nMemory l'
en6 English I_Love_AnhThu 2024-08-24 13:59:37 4 Tiny change: 'eq 10^7$\nTime limit : 2.5s\nMemory l' -> 'eq 10^7$\n\nTime limit : 2.5s\n\nMemory l'
en5 English I_Love_AnhThu 2024-08-24 13:59:20 42 Tiny change: 'eq 10^7$\n\nI'm tr' -> 'eq 10^7$\nTime limit : 2.5s\nMemory limit : 512 mb\n\nI'm tr'
en4 English I_Love_AnhThu 2024-08-24 13:58:36 137
en3 English I_Love_AnhThu 2024-08-24 13:55:30 102
en2 English I_Love_AnhThu 2024-08-24 13:54:11 56 Tiny change: 'a[i]$ \n\n' -> 'a[i]$ \n\n$1 \leq n, q \leq 5.10^5$\n$1 \leq s \leq 10^7$\n$'
en1 English I_Love_AnhThu 2024-08-24 13:52:50 374 Initial revision (saved to drafts)