Codeforces Round #792 (Div. 1 + Div. 2)
23:07:10 |
Codeforces Round #793 (Div. 2)
3 өдрийн дараа |
Educational Codeforces Round 129 (Rated for Div. 2)
4 өдрийн дараа |
Codeforces Round #794 (Div. 1)
7 өдрийн дараа |
Codeforces Round #794 (Div. 2)
7 өдрийн дараа |
C. Баавгай ба анхны тоонууд
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 512 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Саяхнаас баавгай өгөгдлийн бүтцийг судалж эхэлсэн ба дараах асуудалтай тулгарсан.
Чамд $n$ урттай $x_{1}, x_{2}, ..., x_{n}$ бүхэл тоонуудын дараалал болон $m$ асуулгууд өгөгдсөн, асуулга бүр нь $l_{i}, r_{i}$ хоёр бүхэл тоогоор тэмдэглэгдэнэ. $f(p)$ нь $x_{k}$-нь $p$-д хуваагддаг байх $k$ индексүүдийн тоог төлөөлнө. $l_{i}, r_{i}$ асуулгын хариулт нь: нийлбэр байх ба $S(l_{i}, r_{i})$ нь $[l_{i}, r_{i}]$ завсар дахь анхны тоонуудын олонлог юм (завсрын хязгааруудыг оруулна).
Баавгайн асуудлыг даван туулахад нь түүнд тусал.
Оролт
Эхний мөр нь $n$ $(1 ≤ n ≤ 10^{6})$ бүхэл тооноос бүрдэнэ. Хоёр дахь мөр нь $n$ ширхэг $x_{1}, x_{2}, ..., x_{n}$ $(2 ≤ x_{i} ≤ 10^{7})$ бүхэл тоонуудыг агуулна. Тоонууд нь заавал ялгаатай байх шаардлагагүй.
Гурав дахь мөр нь $m$ $(1 ≤ m ≤ 50000)$ бүхэл тоог агуулна. Дараагийн $m$ мөр бүр нь зайгаар тусгаарлагдсан $l_{i}$, $r_{i}$ $(2 ≤ l_{i} ≤ r_{i} ≤ 2*10^{9})$ бүхэл тоон хосыг агуулна. Эдгээр нь одоогийн асуулгыг тодорхойлсон тоонууд.
Гаралт
$m$ бүхэл тоонууд хэвлэнэ. Хариултууд нь асуулгуудын оруулсан дарааллаар байна.
Орчуулсан: Даариймаа
Жишээ тэстүүд
Оролт
6 5 5 7 10 14 15 3 2 11 3 12 4 4
Гаралт
9 7 0
Оролт
7 2 3 5 7 11 4 8 2 8 10 2 123
Гаралт
0 7
Тэмдэглэл
Эхний жишээг авч үзье. Эхний жишээнд нийт гурван асуулга байна.
- Эхний асуулганд $l = 2$, $r = 11$ байна. $f(2) + f(3) + f(5) + f(7) + f(11) = 2 + 1 + 4 + 2 + 0 = 9$ гэж тооцоолох хэрэгтэй.
- Хоёр дахь асуулганд $l = 3$, $r = 12$ байна. f(3) + f(5) + f(7) + f(11) = 1 + 4 + 2 + 0 = 7$ гэж тооцоолох хэрэгтэй.
- Гурав дахь асуулганд $l = 4$, $r = 4$ байна. Энэ завсарт ямар ч анхны тоо байхгүй учраас нийбэр 0-тэй тэнцүү байна.