304380: CF837G. Functions On The Segments

Memory Limit:1024 MB Time Limit:5 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Functions On The Segments

题意翻译

你有 $n$ 个函数,第 $i$ 个函数 $f_i$ 为: $$f_i(x)=\begin{cases}y_1,&x\le x_1\\ax+b,&x_1<x\le x_2\\y_2,&x>x_2\end{cases}$$ $m$ 次询问,每次询问给出 $l,r,x$,求 $\displaystyle\sum_{i=l}^r f_i(x)$。**强制在线。**

题目描述

You have an array $ f $ of $ n $ functions.The function $ f_{i}(x) $ ( $ 1<=i<=n $ ) is characterized by parameters: $ x_{1},x_{2},y_{1},a,b,y_{2} $ and take values: - $ y_{1} $ , if $ x<=x_{1} $ . - $ a·x+b $ , if $ x_{1}&lt;x<=x_{2} $ . - $ y_{2} $ , if $ x&gt;x_{2} $ . There are $ m $ queries. Each query is determined by numbers $ l $ , $ r $ and $ x $ . For a query with number $ i $ ( $ 1<=i<=m $ ), you need to calculate the sum of all $ f_{j}(x_{i}) $ where $ l<=j<=r $ . The value of $ x_{i} $ is calculated as follows: $ x_{i}=(x+last) $ mod $ 10^{9} $ , where $ last $ is the answer to the query with number $ i-1 $ . The value of $ last $ equals $ 0 $ if $ i=1 $ .

输入输出格式

输入格式


First line contains one integer number $ n $ ( $ 1<=n<=75000 $ ). Each of the next $ n $ lines contains six integer numbers: $ x_{1},x_{2},y_{1},a,b,y_{2} $ ( $ 0<=x_{1}&lt;x_{2}<=2·10^{5} $ , $ 0<=y_{1},y_{2}<=10^{9} $ , $ 0<=a,b<=10^{4} $ ). Next line contains one integer number $ m $ ( $ 1<=m<=500000 $ ). Each of the next $ m $ lines contains three integer numbers: $ l $ , $ r $ and $ x $ ( $ 1<=l<=r<=n $ , $ 0<=x<=10^{9} $ ).

输出格式


输入输出样例

输入样例 #1

1
1 2 1 4 5 10
1
1 1 2

输出样例 #1

13

输入样例 #2

3
2 5 1 1 1 4
3 6 8 2 5 7
1 3 5 1 4 10
3
1 3 3
2 3 2
1 2 5

输出样例 #2

19
17
11

Input

题意翻译

你有 $n$ 个函数,第 $i$ 个函数 $f_i$ 为: $$f_i(x)=\begin{cases}y_1,&x\le x_1\\ax+b,&x_1<x\le x_2\\y_2,&x>x_2\end{cases}$$ $m$ 次询问,每次询问给出 $l,r,x$,求 $\displaystyle\sum_{i=l}^r f_i(x)$。**强制在线。**

加入题单

上一题 下一题 算法标签: