P10637 BZOJ4262 Sum

Given an integer sequence $a_i$ of length $10^5$, you need to answer $t$ queries. Each query provides four values $l_1, l_2, r_1, r_2$, and you need to compute: $$\sum_{l \in [l_1,r_1]} \sum_{r \in [l_2,r_2]} (\max_{i \in [l,r]} a_i-\min_{i\in [l,r]} a_i)$$ You do not have to process the queries online. In this problem, the sequence $a_i$ is generated by the following code: ```cpp const int mod = 1e9; long long fst = 1023, sec = 1025; for (int i = 1; i

The first line contains an integer $t$, indicating the number of queries. The next $t$ lines each contain four integers $l_1, r_1, l_2, r_2$.

Output $t$ lines in total. Each line contains one number $\text{Sum}$, which is the answer.

Constraints: $1\leq t\leq 40000$, $1\leq l_1 \leq r_1\leq 10^5$, $1\leq l_2 \leq r_2\leq 10^5$. Translated by ChatGPT 5