B. Сережа ба Мод

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

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

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

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

Сережа моднуудыг шүтдэг. Өнөөдөр тэр эрс шинэчлэлт хийсэн хоёртын модтой (үндэс нь тэмдэглэгдсэн) учирсан.

Түүний шинэ мод нь $n$ давхаргатай ба орой бүр хоёр бүхэл тоон утгаар дугаарлагдана: давхаргын дугаар, тухайн давхарга дээр оройн байрлаж буй байрлалын дугаар. Модны үндэс нь $1$-р давхарга дээр байх ба үүний дугаар нь $(1, 1)$. Модны псеудо код нь:

//the global data are integer arrays cnt[], left[][], right[][]  

cnt[1] = 1;  
fill arrays left[][], right[][] with values -1;  
for(level = 1; level < n; level = level + 1){  
    cnt[level + 1] = 0;  
    for(position = 1; position <= cnt[level]; position = position + 1){  
        if(the value of position is a power of two){ // that is, 1, 2, 4, 8...  
            left[level][position] = cnt[level + 1] + 1;  
            right[level][position] = cnt[level + 1] + 2;  
            cnt[level + 1] = cnt[level + 1] + 2;              
        }else{  
            right[level][position] = cnt[level + 1] + 1;  
            cnt[level + 1] = cnt[level + 1] + 1;  
        }  
    }  
}

Псеудо код ажилласаны дараа $cnt[level]$ массивын нүд нь $level$ давхаргын оройнуудын тоог агуулна. $left[level][position]$ массивын нүд нь $(level, position)$ дугаартай оройн зүүн хүүхдийн $level + 1$ давхарга дээрх дугаарыг агуулна эсвэл тухайн оройд зүүн хүүхэд байхгүй бол $-1$-г агуулна. Үүнтэй адилаар $right[level][position]$ массивын нүд нь баруун хүүхдийг илтгэнэ. Та тэмдэглэл хэсгээс $n = 4$ давхаргатай мод ямар байхын харж болно.

Сережа юмыг төвөгтэй болгох дуртай ба тэр эхлээд мод бүтээсэн ба орой бүр дээр $A(level, position)$ хоосон бүрдэл нэмсэн. Тэгээд Сережа $m$ ширхэг үйлдэл гүйцэтгэсэн. Үйлдэл бүр дараах хоёр төрлийн аль нэг нь байна:

  • Үйлдлийн формат нь "$1$ $t$ $l$ $r$ $x$". Бүх $level, position$ $(level = t; l ≤ position ≤ r)$ оройн хувьд $x$ утгыг $A(level, position)$ бүрдэлрүү нэмнэ.
  • Үйлдлийн формат нь "$2$ $t$ $v$". $level, position$ оройн хувьд $(level, position)$ оройн дэд модны оройнуудын бүх бүрдлийн нэгдлийг олох. Уг бүрдлүүдийн нэгдлийн хэмжээг хэвлэх.

Сережад үйлдлүүдийг гүйцэтгэхэд туслана уу. Энэ бодлого дээр бүрдэл нь зөвхөн C++ дээрх std::set шиг ялгаатай утгуудыг агуулна.

Оролт

Эхний мөрөнд $n$ ба $m$ $(1 ≤ n, m ≤ 7000)$ бүхэл тоон утгууд байна.

Дараагийн $m$ мөрөнд үйлдлүүдийн тодорхойлолтууд байна. Эхний төрлийн үйлдэл таван бүхэл тоон утгаар өгөгдөнө: $1$ $t$ $l$ $r$ $x$ $(1 ≤ t ≤ n; 1 ≤ l ≤ r ≤ cnt[t]; 1 ≤ x ≤ 10^{6})$. Хоёр дахь төрлийн үйлдэл нь гурван бүхэл тоон утгаар өгөгдөнө: $2$ $t$ $v$ $(1 ≤ t ≤ n; 1 ≤ v ≤ cnt[t])$.

Гаралт

Хоёр дахь төрлийн үйлдэл бүрийн хувьд хариултыг нэг мөрөнд хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

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

Тэмдэглэл

Та үндэстэй модтой ажиллах үедээ тодорхойломжуудыг дараах линкээс олж болно: http://en.wikipedia.org/wiki/Tree_(graph_theory)

Та $n = 4$ давхаргатай байгуулагдсан модыг доод зурагнаас харж болно.

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