1、1行星序列（seq）“神州“載人飛船的發(fā)射成功讓小可可非常激動(dòng)，他立志長(zhǎng)大后要成為一名宇航員假期一始，他就報(bào)名參加了“小小宇航員夏令營(yíng)”，在這里小可可不僅學(xué)到了豐富的宇航知識(shí)，還參與解決了一些模擬飛行中發(fā)現(xiàn)，今天指導(dǎo)老師交給他一個(gè)任務(wù)，在這次模擬飛行的路線上有 N 個(gè)行星，暫且稱它們?yōu)橐粋€(gè)行星序列，并將他們從 1 至 n 標(biāo)號(hào)，在宇宙未知力量的作用下這 N 個(gè)行星的質(zhì)量是不斷變化的，所以他們對(duì)飛船產(chǎn)生的引力也會(huì)不斷變化，小可可的任務(wù)就是在飛行途中計(jì)算這個(gè)行星序列中某段行星的質(zhì)量和，以便最終到達(dá)目的地，行星序列質(zhì)量變化有兩種形式： 1，行星序列中某一段行星的質(zhì)量全部乘以一個(gè)值2，行星序列中某一段

2、行星的質(zhì)量全部加上一個(gè)值修正飛船的飛行線路，由于行星的質(zhì)量和很大，所以求出某段行星的質(zhì)量和后只要輸出這個(gè)值模 P 的結(jié)果即可，小可可被這個(gè)任務(wù)難住了，聰明的你能夠幫他完成這個(gè)任務(wù)嗎？輸入：第一行兩個(gè)整數(shù)N 和P（1p1000000000）；第二行含有 N 個(gè)非負(fù)整數(shù)，從左到右依次為 a1，a2，an（0ai。100000000，1in），其中 ai 表示第i 個(gè)行星的質(zhì)量：第三行有一個(gè)整數(shù)m，表示模擬行星質(zhì)量變化以及求質(zhì)量和等操作的總次數(shù)。從第四行開始每行描述一個(gè)操作，輸入的操作有以下三種形式：操作 1：1 t g c 表示把所有滿足tig 的行星質(zhì)量ai 改為 aic操作 2：2 t g c

3、 表示把所有滿足tig 的行星質(zhì)量ai 改為 aic操作 3：3 t g 表示輸出所有滿足tig 的ai 的和模 p 的值其中：1tgN，0c10000000注：同一行相鄰的兩數(shù)之間用一個(gè)空格隔開，每行開頭和末尾沒有多余空格輸出：對(duì)每個(gè)操作 3，按照它在輸入中出現(xiàn)的順序，依次一行輸出一個(gè)整數(shù)表示所求行星質(zhì)量和樣例：輸入：7 431 2 3 4 5 6 751 2 5 53 2 42 3 7 93 1 33 4 7輸出：2358樣例說明：略提示： 100的數(shù)據(jù)中，M，N100000 40的數(shù)據(jù)中，M，N10000（Neilc-lc 提醒你，直接模擬可能是一個(gè)點(diǎn)都過不去，加上每次 mod 的優(yōu)化，

4、可以過 3 到 4 個(gè)點(diǎn)正解是用線段樹來做）2同類分布（self）在模擬飛行的過程中，小可可發(fā)現(xiàn)在一個(gè)未知星球周圍分布著許多同類的小行星帶，而這些小行星帶的分布非常有規(guī)律，經(jīng)過研究發(fā)現(xiàn)實(shí)些小行星帶到未知星球的距離為x（x 為非負(fù)整數(shù)）與如下的函數(shù)有一定的關(guān)系：dsum(x)0 x=0;dsum(x/10)+x mod 10 x0即x 可以被dsum（x）整除。小可可非常希望能研究出距離這個(gè)未知星球的某一區(qū)域內(nèi)小行星帶的分布規(guī)律，具體來說，就是在與未知行星距離 a 和b 的范圍內(nèi)分布了多少個(gè)小行星帶，你能幫助他解決這個(gè)問題嗎？輸入：輸入文件僅一行，包含兩個(gè)正整數(shù)a 和 b（a=b).輸出：輸出文

5、件中僅包含一個(gè)整數(shù)，表示a，b內(nèi)分布多少個(gè)小行星帶。樣例 1:輸入：1 10輸出：10樣例 2：輸入：1234567912345679 1234567912346789輸出：37提示：100的數(shù)據(jù)中，a，b 不超過30的數(shù)據(jù)中，ba 不超過 1000000（10 的 18 次方）；3最小截?cái)嘤钪媛眯锌偸浅霈F(xiàn)一些意想不到，這次小可可所駕駛的宇宙飛船所停的空間站發(fā)生了故障，這個(gè)宇宙空間站非常大，它由 N 個(gè)子站組成，子站之間有 M條單向通道，假設(shè)其中第 i（1iM）條單向通道連接了 xi，yi 兩個(gè)中轉(zhuǎn)站，那么 xi 子站可以通過這個(gè)通道到達(dá) yi 子站，如果截?cái)噙@條通道，需要代價(jià) ci?，F(xiàn)在為了

6、將故障的代價(jià)控制到最小，小可可必須想出一個(gè)截?cái)喾桨福?a 站不能到達(dá)b 子站，并且截?cái)嗟拇鷥r(jià)之和最小。稱之為最小截?cái)啵】煽珊芸旖鉀Q了這個(gè)故障，但是愛思考的小可可并不局限于此，為了今后更方便的解決同類故障，他考慮對(duì)每條單向通道： 1，是否存在一個(gè)最小代價(jià)路徑截?cái)喾桨?，其中該通道被切斷?，是否對(duì)任何一個(gè)最小代價(jià)路徑切斷方案，都有該通道被切斷？聰明的你能幫小可可解決他的疑問嗎？輸入：第一行有 4 個(gè)整數(shù)，依次為N，M，a 和b；第二行到第(m+1)行每行 3 個(gè)正整數(shù)x，y，c 表示 x 子站到 y 子站之間有單向通道相連，單向通道的起點(diǎn)是 x 終點(diǎn)是y，切斷它的代價(jià)是 c（1c10000）；兩個(gè)子站之間可能有多條通道直接連接。輸出：對(duì)每一個(gè)單向通道，按輸入的順序，依次輸出一行包含兩個(gè)非 0 即 1 的整數(shù)，分別表示對(duì)問題一和問題二的回答（其中 1 表示是，0 表示否）。每行兩個(gè)整數(shù)之間用一個(gè)空格分隔開。樣例：輸入：6 72 5