P15365 [CTS 2026] Signal Connection (No testdata yet)

There are $n$ communication stations in space, numbered from $1 \sim n$. Each station has two parameters. For station $i$ ($1 \le i \le n$), its transmission coefficient is $a_i$, and its receiving coefficient is $b_i$. If station $i$ ($1 \le i \le n$) transmits a signal to station $j$ ($1 \le j \le n$), then a bidirectional signal connection will be established between these two stations, and the required cost is $a_i b_j$. Since stations may absorb energy from cosmic rays, the required cost may be negative. To establish a bidirectional signal connection between stations $i, j$ ($1 \le i, j \le n$), you may choose either station to initiate the connection as the transmitter, so the minimum cost is $\min(a_i b_j, a_j b_i)$. When two stations are directly connected, or are indirectly connected through other stations, they can join the same communication system. To reduce costs, usually only some of the stations are operating. You need to compute, for stations whose indices are within the interval $l \sim r$, when **signal connections can only be established among these stations**, the minimum cost to **use as few bidirectional signal connections as possible** to make all these stations join the same communication system. ### Implementation Details Contestants do not need to, and should not, implement the `main` function. Contestants must ensure that the submitted program includes the header file `signal.h`, i.e., add the following code at the beginning: ```cpp #include "signal.h" ``` Contestants need to implement the following two functions in the submitted source file: ```cpp void signal(int n, std::vector a, std::vector b); ``` - $n$ is the number of communication stations. - For $1 \le i \le n$, $a_i$ is the transmission coefficient of station $i$, and $b_i$ is the receiving coefficient of station $i$. Note: $a, b$ are two sequences of length $n+1$, where $a_0, b_0$ have no actual meaning. - Note: for each test point, this function may be called multiple times by the interactive library. ```cpp long long mincost(int l, int r); ``` - $l, r$ denote the index interval of the stations that are operating. - This function needs to return the minimum cost to use as few bidirectional signal connections as possible to make all these stations join the same communication system. - Note: the transmission and receiving coefficients are the parameters passed in the most recent call to `signal`. - All calls to this function occur after at least one call to `signal`. **Note**: Under all circumstances, the running time required by the interactive library will not exceed 0.1 seconds, and the memory used is of fixed size and does not exceed 64 MiB. ### How to Run the Test Program In the problem directory, `grader.cpp` is a reference implementation of the interactive library. The interactive library used in final testing is different from this reference implementation, so your solution should not rely on the interactive library implementation. You can compile an executable program in this directory using the following command: ```bash g++ grader.cpp signal.cpp -o signal -std=gnu++14 -O2 -pipe -static -s ```

For the compiled executable: - The executable will read data from **standard input** in the following format: - The first line contains a positive integer $t$, denoting the number of testdata groups. - Then for each testdata group: * The first line contains two positive integers $n, q$, denoting the number of communication stations and the number of queries. * The second line contains $n$ integers $a_1, \dots, a_n$, denoting the transmission coefficients of each station. * The third line contains $n$ integers $b_1, \dots, b_n$, denoting the receiving coefficients of each station. * Line $i+3$ ($1 \le i \le q$) contains two positive integers $l, r$, denoting the index interval of stations that are operating in the $i$-th query.

- The executable will output data to **standard output** in the following format: - For each testdata group, output one line with $q$ integers, each being the minimum cost for the corresponding query to use as few bidirectional signal connections as possible to make all operating stations join the same communication system.

### Sample 1 Explanation This sample contains two testdata groups. For the first testdata group, in the query all stations are operating. You can transmit signals from station 1 to stations 2 and 3, with total cost $1 \times 1 + 1 \times 4 = 5$. At this point, all stations can join the same communication system. ### Additional Files Description In the additional files: 1. `grader.cpp` is the provided reference implementation of the interactive library. 2. `signal.h` is the header file; contestants do not need to care about its specific content. 3. `template_signal.cpp` is the provided sample code; contestants can refer to it and implement their own code. ### Subtasks Let $N, Q$ be the sums of $n, q$ over all testdata in a single test point. For all testdata, we have: - $1 \le t \le 10^5$. - $1 \le n, q \le 10^5$, $N, Q \le 10^5$. - For all $1 \le i \le n$, $|a_i|, |b_i| \le 10^6$. - $1 \le l \le r \le n$. ::cute-table{tuack} | Subtask ID | Score | $N, Q \le$ | Special Property | |:-:|:-:|:-:|:-:| | $1$ | $3$ | $10^2$ | None | | $2$ | $7$ | $5,000$ | A | | $3$ | $11$ | ^ | B | | $4$ | $13$ | ^ | None | | $5$ | $14$ | $10^5$ | A | | $6$ | $16$ | ^ | B | | $7$ | $36$ | ^ | None | **Special Property A**: for all $1 \le i \le n$, $a_i, b_i > 0$. **Special Property B**: for all $1 \le i \le n$, $a_i b_i < 0$. ### Scoring **Note**: - Contestants should not obtain internal information from the interactive library through illegal means, such as directly interacting with standard input/output streams. Such behavior will be considered cheating. - **The interactive library used in final evaluation is different from the one used for samples**. This problem is first subject to the same limits as traditional problems. For example, compilation errors will cause the entire problem to score 0 points; runtime errors, exceeding the time limit, exceeding the memory limit, etc., will cause the corresponding test points to score 0 points. Contestants may only access variables defined by themselves and variables provided by the interactive library; attempting to access other address spaces may cause compilation errors or runtime errors. Based on the above conditions: - For each test point, the program gets full score if and only if the answer returned by every call to `mincost` is correct. Translated by ChatGPT 5