C. Машмок ба хөрвүүлэх үйлдэл

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Машмок түүний дарга болох Бимокд таалагдсангүй. Тиймээс түүнийг ажлаас нь халжээ. Машмок их сургуульд явахаар шийдсэн ба шинэ ажил хайхын оронд ACM-д орохоор шийджээ. Тэр Бамох багийн гишүүн болохыг хүссэн. Нэгдэхийн тулд долоо хоногийн хугацаатай зарим нэг програмчлалын даалгаврыг түүнд өгсөн. Машмок туршлагатай програмист биш, үнэндээ яг ч програмист биш. Тэгэхээр тэр энэ асуудлыг шийдвэрлэж чадахгүй гэсэн үг юм. Тэр эдгээр даалгавруудад таны тусламжийг хүсэж байна. Эдгээр даалгавруудын нэг нь дараах болно.

Танд $2^{n}$ урттай $a$ массив ба түүн дээрх $m$ асуулгууд байна. $i$-р асуулга нь $q_{i}$ бүхэл тоогоор тодорхойлогдоно. Та $i$-р асуулгыг гүйцэтгэхийн тулд:

  • хэсэг бүр нь $2^{q_{i}}$ тоонууд агуулсан дэд массив байхаар массивыг $2^{n - q_{i}}$ хэсгүүдэд хуваана; $j$-р дэд массив $(1 ≤ j ≤ 2^{n - q_{i}})$ нь $a[(j - 1)*2^{q_{i}} + 1], a[(j - 1)*2^{q_{i}} + 2], ..., a[(j - 1)*2^{q_{i}} + 2^{q_{i}}]$ элементүүдийг агуулсан байх ёстой;

  • дэд массив бүрийг хөрвүүлнэ;

  • тэдгээрийг ижил дараллаар нэг массивт нэгтгэнэ (энэ массив нь шинэ $a$ массив болно);

  • шинэ $a$ массивын өөрчлөлтийн тоог хэвлэнэ.

Анхны $a$ массив болон бүх асуулгууд өгөгдөнө. Бүх асуулгуудад хариулна. Зарим асуулгын өөрчлөлт нь дараагийн асуулгад хадгалагдсан болохыг анхаарна уу.

Оролт

Оролтын эхний мөр нь бүхэл $n (0 ≤ n ≤ 20)$ тоог агуулна.

Оролтын хоёр дахь мөр нь анхны массив болох зайгаар тусгаарлагдсан $2^{n}$ ширхэг $a[1]$, $a[2]$, ..., $a[2^{n}]$ $(1 ≤ a[i] ≤ 10^{9})$ бүхэл тоонуудыг агуулна.

Оролтын гурав дахь мөр нь бүхэл $m (1 ≤ m ≤ 10^{6})$ тоог агуулна.

Оролтын дөрөв дахь мөр нь асуулгуудын тоо болох зайгаар тусгаарлагдсан $m$ ширхэг $q_{1}, q_{2}, ..., q_{m} (0 ≤ q_{i} ≤ n)$ бүхэл тоонуудыг агуулна.

Анхааруулга: оролт болон гаралтын хэмжээ нь маш том байж болох учраас таны хэлний удаан гаралтын аргыг ашиглахгүй байна уу. Жишээлбэл C++ хэлэнд (cin, cout) оролт болон гаралтын урсгалуудыг бүү ашигла.

Гаралт

$m$ мөрүүд гарна. $i$-р мөрөнд $i$-р асуулгын хариуг (өөрчлөлтийн тоо) хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
2
2 1 4 3
4
1 2 0 2
Гаралт
0
6
6
0
Оролт
1
1 2
3
0 1 1
Гаралт
0
1
0

Тэмдэглэл

Хэрвээ $x[1], x[2], ..., x[n]$ массивыг хөрвүүлвэл энэ нь $i$ бүрийн хувьд $y[i] = x[n - i + 1]$ байх $y[1], y[2], ..., y[n]$ шинэ массив болно.

$x[1], x[2], ..., x[n]$ массивын өөрчлөлтийн тоо нь $i < j$ ба $x[i] > x[j]$ байх $i, j$ индекстэй хосуудын тоо юм.

Сэтгэгдлүүдийг ачааллаж байна...