Universal Cup Judging System

Universal Cup

حد الوقت: 2.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

On taulukko $a$, jonka pituus on $n$ ja jonka $i$:s luku on $a_i$. Lisäksi jokaisella luvulla on pistemäärä, ja $i$:nnen luvun pistemäärä on $c_i$. Alice ja Bob pelaavat vuorotellen, ja Alice aloittaa.

Nykyisellä kierroksella pelaaja kopioi ensin taulukon $a$ taulukkoon $b$ ja ajaa satunnaisen sekoitusohjelman sekoittaakseen taulukon $b$ satunnaisesti. Tarkemmin sanottuna sekoitusohjelma valitsee yhden taulukon $b$ permutaatioista yhtä suurella todennäköisyydellä ja korvaa alkuperäisen taulukon $b$ sillä. Oletetaan, että taulukon $a$ nykyinen pituus on $m$; tällöin pelaaja voi valita kokonaisluvun $k$ siten, että $0 \le k \le m$ ja $a[1 \dots k] = b[1 \dots k]$, ja poistaa sitten osuuden $a[1 \dots k]$ (eli taulukon $a$ pituutta $k$ olevan etuliitteen) ja saada poistettujen lukujen pisteet. Peli päättyy, kun taulukko $a$ on tyhjennetty.

Huomaa, että taulukkoa $a$ ja sen pistetaulukkoa $c$ ei sekoiteta koko prosessin aikana, vaan ainoastaan niiden etuliitteitä poistetaan.

Sekä Alice että Bob haluavat maksimoida omat pisteensä. Alice haluaa tietää, mikä on hänen odotettu pistemääränsä, kun molemmat pelaajat käyttävät optimaalisia strategioita.

Alice teki myös $q$ muutosten ryhmää (muuttaen taulukkoa ja pisteitä), ja hän haluaa sinun etsivän vastauksen alkuperäiselle taulukolle sekä vastaukset jokaisen muutosryhmän jälkeen.

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 10^6$), joka kuvaa alkuperäisen taulukon $a$ pituutta.

Toinen rivi sisältää $n$ kokonaislukua $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), jotka kuvaavat alkuperäisen taulukon $a$.

Kolmas rivi sisältää $n$ kokonaislukua $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$), jotka kuvaavat taulukon kunkin luvun pistemäärän.

Seuraava rivi sisältää kokonaisluvun $q$ ($0 \le q \le 10$), joka kuvaa muutosryhmien lukumäärää.

Seuraavassa kuvataan $q$ muutosryhmää:

Jokaiselle muutosryhmälle ensimmäinen rivi sisältää luvun $k_i$ ($1 \le k_i \le 10^5$), joka kertoo muutosten lukumäärän tässä ryhmässä.

Seuraavat $k_i$ riviä sisältävät kukin kolme kokonaislukua $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$), jotka kertovat, että $a_{p_j}$ muutetaan arvoksi $x_j$ ja $c_{p_j}$ muutetaan arvoksi $y_j$.

Taataan, että $p_1 < p_2 < \dots < p_{k_i}$.

Tuloste

Tulosta yhteensä $q + 1$ riviä, joista jokainen sisältää vastausta kuvaavan liukuluvun.

Ensimmäinen rivi on vastaus alkuperäiselle taulukolle, ja sitä seuraavat $q$ riviä ovat vastaukset kunkin muutosryhmän jälkeen.

Vastaus katsotaan oikeaksi, jos suhteellinen tai absoluuttinen virhe mallivastaukseen verrattuna on enintään $10^{-9}$.

Esimerkit

Syöte 1

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

Tuloste 1

1.333333333333
3.000000000000
4.000000000000

Syöte 2

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

Tuloste 2

9.013888888889

Huomautus

Tässä tehtävässä on suuri syötekoko; käytäthän tehokasta syötteenlukumenetelmää.

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.