Codeforces Round #803 (Div. 2)
06:55:49 |
Codeforces Round #804 (Div. 2)
7 өдрийн дараа |
D. Дэд хэсэг дээрх Хафмэн Кодчилол
хугацааны хязгаарлалт 4 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Алис Бобруу чухал мэссэж явуулахыг хүсч байна. $a = (a_{1}, ..., a_{n})$ мэссэж нь эерэг бүхэл тоонуудын (тэмдэгтүүдийн) дараалал байна.
Мэссэжийг шахахын тулд Алис хоёртын Хафмэн кодчилолыг ашиглахыг хүссэн. Бид хоёртын Хафмэн код эсвэл хоёртын угтвар кодыг $f$ функц болгоно. $f$ функц нь тэмдэгт мөр дахь үсэг бүрийг ялгаатай хоёр тэмдэгт $a_{i}$ ба $a_{j}$-н хувьд $f(a_{i})$ нь $f(a_{j})$-н угтвар биш байхаар (мөн эсрэгээрээ) хоёртын тэмдэгт мөррүү (буюу зөвхөн '$0$' ба '$1$' тэмдэгтүүдээс бүрдэх) хөрвүүлнэ. $a_{1}, a_{2}, ..., a_{n}$ мэссэжийн хөрвүүлэлтийн үр дүн нь тэмдэгт бүрийн хөрвүүлэлтийн хэлхээ байх буюу $f(a_{1})f(a_{2})... f(a_{n})$ тэмдэгт мөр байна. Хэрвээ $f$ функц өгөгдсөн тохиолдолд шахсан мэссэжийг хялбар бас давтагдахгүйгээр тайлах боломжтой учир Хафмэний кодууд маш хэрэгцээтэй. Кодыг сонгохдоо ихэвчлэн шахсан мэссэжийн нийт уртыг хамгийн бага байлгахаар сонгодог, өөрөөр $f(a_{1})f(a_{2})... f(a_{n})$ тэмдэгт мөрийн урт.
Аюулгүй байдлын үүднээс Алис бүх мэссэжийг явуулахыг хүссэнгүй. Түүний оронд тэр мэссэжийн дэд тэмдэгт мөрүүдийг авч тэдгээрийг тус тусад нь явуулахыг хүссэн. Өгөгдсөн $a_{l_{i}}... a_{r_{i}}$ дэд тэмдэгт мөр бүрийн хувьд тэр Хафмэн кодчилолын хамгийн бага уртыг мэдэхийг хүсч байна.
Оролт
Оролтын эхний мөрөнд бүхэл тоон утга $n$ ($1 ≤ n ≤ 100 000$) байх буюу анхны мэссэжийн урт юм. Хоёр дахь мөрөнд $n$ бүхэл тоон утга $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{i} ≤ 100 000$) байх буюу мэссэжийн тэмдэгтүүд юм.
Дараагийн мөрөнд бүхэл тоон утга $q$ ($1 ≤ q ≤ 100 000$) байх ба асуулгуудын тоо юм.
Дараагийн $q$ мөрөнд асуулгуудын тайлбар байна. Эдгээрийн $i$-р мөрөнд хоёр бүхэл тоон утга $l_{i}$ ба $r_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ n$) байх буюу $i$-р дэд тэмдэгт мөрийн зүүн болон баруун төгсгөлүүдийн байрлал байна. Байрлалууд $1$-с эхлэн дугаарлагдана. Дэд тэмдэгт мөрүүд ямар ч тохиолдлоор давхардаж болно. Оролтонд ижил дэд тэмдэгт мөрүүд нэгээс олон байж болно.
Гаралт
Гаралтанд $q$ мөр хэвлэнэ. Мөр бүрт $a_{l_{i}}... a_{r_{i}}$ дэд тэмдэгт мөрийн Хафмэн хөрвүүлэлтийн боломжит хамгийн бага урт байна.
Орчуулсан: Г.Мэндбаяр
Жишээ тэстүүд
Оролт
7 1 2 1 3 1 2 1 5 1 7 1 3 3 5 2 4 4 4
Гаралт
10 3 3 5 0
Тэмдэглэл
Эхний асуулга дээр дэд тэмдэгт мөрийг хөрвүүлэх тохиромжтой замуудын нэг нь $1$-г "$0$", $2$-г "$10$", $3$-г "$11$" болгож хөрвүүлэх юм.
Үсгийг хоосон дэд тэмдэгт мөррүү хөрвүүлэх нь зөв (тавдугаар асуулга дээрх шиг).