Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

Ұзындығы $n$ болатын $a$ массиві бар, мұндағы $i$-ші сан $a_i$-ге тең. Сонымен қатар, әр санның ұпайы бар, және $i$-ші санның ұпайы $c_i$-ге тең. Алиса мен Боб кезектесіп жүреді, ойынды Алиса бірінші бастайды.

Ағымдағы раундта ойыншы алдымен $a$ массивін $b$ массивіне көшіреді және $b$ массивін кездейсоқ араластыру үшін кездейсоқ араластыру программасын іске қосады. Нақтырақ айтқанда, кездейсоқ араластыру программасы бірдей ықтималдықпен $b$ массивінің алмастыруларының бірін таңдап, бастапқы $b$ массивін сонымен алмастырады. Ағымдағы $a$ массивінің ұзындығы $m$ болсын делік, сонда ойыншы $0 \le k \le m$ және $a[1 \dots k] = b[1 \dots k]$ болатындай $k$ бүтін санын таңдап, содан кейін $a[1 \dots k]$ бөлігін (яғни $a$ массивінің ұзындығы $k$ болатын префиксін) өшіріп, өшірілген сандардың ұпайын ала алады. Ойын $a$ массиві босаған кезде аяқталады.

Бүкіл процесс барысында $a$ массиві мен оның ұпайлар массиві $c$ араластырылмайтынына, тек олардың префикстері ғана өшірілетініне назар аударыңыз.

Алиса да, Боб та өз ұпайларын барынша арттырғысы келеді. Алиса екі ойыншы да оңтайлы стратегияны қолданған кезде оның күтілетін ұпайы қандай болатынын білгісі келеді.

Сонымен қатар Алиса $q$ өзгертулер тобын (массив пен ұпайларды өзгерту) жасады, және ол сізден бастапқы массив үшін жауапты, сондай-ақ әрбір өзгертулер тобынан кейінгі жауаптарды табуыңызды қалайды.

Кіріс деректері

Бірінші жолда бастапқы $a$ массивінің ұзындығын білдіретін бүтін сан $n$ ($1 \le n \le 10^6$) берілген.

Екінші жолда бастапқы $a$ массивін білдіретін $n$ бүтін сан $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) берілген.

Үшінші жолда массивтегі әрбір санның ұпайын білдіретін $n$ бүтін сан $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$) берілген.

Келесі жолда өзгертулер топтарының санын білдіретін бүтін сан $q$ ($0 \le q \le 10$) берілген.

Төменде $q$ өзгертулер тобы сипатталған:

Әрбір өзгертулер тобы үшін бірінші жолда осы топтағы өзгертулер санын көрсететін $k_i$ ($1 \le k_i \le 10^5$) саны берілген.

Келесі $k_i$ жолдың әрқайсысында $a_{p_j}$ мәні $x_j$-ге, ал $c_{p_j}$ мәні $y_j$-ге өзгертілетінін көрсететін үш бүтін сан $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$) берілген.

$p_1 < p_2 < \dots < p_{k_i}$ екеніне кепілдік беріледі.

Шығыс деректері

Барлығы $q + 1$ жол шығарыңыз, әр жолда жауапты білдіретін жылжымалы нүктелі сан болуы керек.

Бірінші жол — бастапқы массив үшін жауап, одан кейін әрбір өзгертулер тобынан кейінгі жауаптарға арналған $q$ жол шығарылады.

Стандартты жауаппен салыстырғанда салыстырмалы немесе абсолютті қателік $10^{-9}$-нен аспаса, жауап дұрыс деп есептеледі.

Мысалдар

Кіріс деректері 1

2
1 2
1 1
2
1
2 1 2
1
1 1 2

Шығыс деректері 1

1.333333333333
3.000000000000
4.000000000000

Кіріс деректері 2

6
1 1 4 5 1 4
2 3 3 3 3 3
0

Шығыс деректері 2

9.013888888889

Ескертпе

Бұл есепте кіріс деректерінің көлемі үлкен, тиімді енгізу әдісін пайдалануыңызды сұраймыз.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.