Universal Cup Judging System

Universal Cup

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

Det er en tabell $a$ med lengde $n$, der det $i$-te tallet er $a_i$. I tillegg har hvert tall en poengsum, og poengsummen til det $i$-te tallet er $c_i$. Alice og Bob bytter på å trekke, og Alice begynner.

I den gjeldende runden kopierer spilleren først tabellen $a$ til tabellen $b$ og kjører et tilfeldig stokkeprogram for å stokke tabellen $b$ tilfeldig. Mer spesifikt vil stokkeprogrammet velge en av permutasjonene av $b$ med lik sannsynlighet og erstatte den opprinnelige tabellen $b$ med den. Anta at den nåværende lengden på tabellen $a$ er $m$; da kan spilleren velge et heltall $k$ slik at $0 \le k \le m$ og $a[1 \dots k] = b[1 \dots k]$, og deretter slette $a[1 \dots k]$ (dvs. prefikset med lengde $k$ av $a$) og få poengsummen til de slettede tallene. Spillet slutter når tabellen $a$ er tømt.

Merk at tabellen $a$ og poengtabellen $c$ ikke blir stokket gjennom hele prosessen, men at kun prefiksene deres fjernes.

Både Alice og Bob ønsker å maksimere poengsummen sin. Alice vil vite hva hennes forventede poengsum er når begge spillerne bruker optimale strategier.

Alice gjorde også $q$ grupper av endringer (endret tabellen og poengsummene), og hun vil at du skal finne svaret for den opprinnelige tabellen, samt svarene etter hver gruppe av endringer.

Inndata

Den første linjen inneholder et heltall $n$ ($1 \le n \le 10^6$), som representerer lengden på den opprinnelige tabellen $a$.

Den andre linjen inneholder $n$ heltall $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), som representerer den opprinnelige tabellen $a$.

Den tredje linjen inneholder $n$ heltall $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$), som representerer poengsummen til hvert tall i tabellen.

Den neste linjen inneholder et heltall $q$ ($0 \le q \le 10$), som representerer antall endringsgrupper.

Det følgende beskriver $q$ grupper av endringer:

For hver gruppe av endringer inneholder den første linjen $k_i$ ($1 \le k_i \le 10^5$), som angir antall endringer i denne gruppen.

De neste $k_i$ linjene inneholder hver tre heltall $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$), som angir at $a_{p_j}$ endres til $x_j$ og $c_{p_j}$ endres til $y_j$.

Det er garantert at $p_1 < p_2 < \dots < p_{k_i}$.

Utdata

Skriv ut totalt $q + 1$ linjer, der hver linje inneholder et flyttall som representerer svaret.

Den første linjen er svaret for den opprinnelige tabellen, etterfulgt av $q$ linjer for svarene etter hver gruppe av endringer.

Et svar regnes som riktig hvis den relative eller absolutte feilen sammenlignet med fasitsvaret ikke overstiger $10^{-9}$.

Eksempler

Inndata 1

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

Utdata 1

1.333333333333
3.000000000000
4.000000000000

Inndata 2

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

Utdata 2

9.013888888889

Merk

Denne oppgaven har stor inndatastørrelse; vennligst bruk en effektiv innlesingsmetode.

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.