|
||||||||||
I love data structureTime Limit: 8000/5000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 734 Accepted Submission(s): 192 Problem Description This is a simple data structure problem. In this problem, you need to maintain a sequence of numbers. Each position of the sequence has two parameters $a$ and $b$. Now there are $m$ operations, and these operations can be divided into four types. Type 1: Given interval $(l, r)$ and $x$, and mark 0/1 represents $a$ parameter or $b$ parameter, for each position in the interval, add $x$ to the $a$ parameter or $b$ parameter at this position. Type 2: Given interval $(l, r)$, for each position in the interval, the $a$ parameter of this position becomes $3a+2b$, and the $b$ parameter becomes $3a-2b$.For example, originally $a=1$, $b=2$, after the operation becomes $a=7$, $b=-1$. Type 3: Given interval $(l, r)$, for each position in the interval, exchange the two parameters $a$, $b$ corresponding to this position. Type 4: Given interval $(l,r)$, query$\sum_{i=l}^ra_i*b_i$ This question is very simple, can you finish it? Input There is only one test case for this question. In the first line, a positive integer $n$ ($n \leq 200000$) represents the length of the sequence. In the next $n$ lines, the i-th line have two numbers in each line to represent the two parameters $a_i$ and $b_i$($1 \leq a_i,b_i \leq 1000000000$) at each position In the next line, a positive integer $q$ ($q \leq 200000$) represents the number of operations. For the next $q$ lines $1$ $tag$ $l$ $r$ $x$($0 \leq tag \leq 1,1 \leq x \leq 1000000000$)means $a$ or $b$ plus $x$ in every position of this interval $2$ $l$ $r$ Let $a$ become $3a+2b$ and $b$ become $3a-2b$ in every position of this interval $3$ $l$ $r$ exchange the weight of $a$ and $b$ in every position of this interval $4$ $l$ $r$ Query the sum of value of $a*b$ in every position of this interval Output For each type $4$ query, output a line of a positive integer to represent the result of the query, and the answer is modulo $1000000007$. Sample Input
Sample Output
Source | ||||||||||
|