300613: CF117D. Not Quick Transformation
Memory Limit:256 MB
Time Limit:6 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Not Quick Transformation
题意翻译
对一个数列 $s$ 定义 $odd_s$ 是将 $s$ 的奇数位取出,即 $odd_s=\{s_{2i}\mid1\le 2i\le |S|\}$;$even_s$ 是将其偶数位取出,同理。 定义一个数列 $s$ 的变换 $F(s)$: $$ F(s)=\begin{cases} F(odd_s)+F(even_s)&|s|>1\\ s&|s|=1 \end{cases} $$ (上面的 $+$ 表示将两个数列首尾相接) 给定正整数 $n$,数列 $a=\{1,2,\dots,n\}$。通过变换得到 $b=F(a)$。 然后进行 $m$ 次询问,每次给出正整数 $l,r,u,v$,求 $$ \sum_{l\le i\le r}[u\le b_i\le v]b_i $$ 即求 $b$ 的 $[l,r]$ 区间内,权值在 $u,v$ 之间的数的权值和,答案对一开始输入的正整数 $mod$ 取模。 数据规模:$1\le n\le10^{18}$,$1\le m\le10^5$,$1\le mod\le10^9$;$1\le l\le r\le n$,$1\le u\le v\le 10^{18}$。题目描述
Let $ a $ be an array consisting of $ n $ numbers. The array's elements are numbered from $ 1 $ to $ n $ , $ even $ is an array consisting of the numerals whose numbers are even in $ a $ ( $ even_{i}=a_{2i} $ , $ 1<=2i<=n $ ), $ odd $ is an array consisting of the numberals whose numbers are odd in $ а $ ( $ odd_{i}=a_{2i-1} $ , $ 1<=2i-1<=n $ ). Then let's define the transformation of array $ F(a) $ in the following manner: - if $ n>1 $ , $ F(a)=F(odd)+F(even) $ , where operation " $ + $ " stands for the arrays' concatenation (joining together) - if $ n=1 $ , $ F(a)=a $ Let $ a $ be an array consisting of $ n $ numbers $ 1,2,3,...,n $ . Then $ b $ is the result of applying the transformation to the array $ a $ (so $ b=F(a) $ ). You are given $ m $ queries $ (l,r,u,v) $ . Your task is to find for each query the sum of numbers $ b_{i} $ , such that $ l<=i<=r $ and $ u<=b_{i}<=v $ . You should print the query results modulo $ mod $ .输入输出格式
输入格式
The first line contains three integers $ n $ , $ m $ , $ mod $ ( $ 1<=n<=10^{18},1<=m<=10^{5},1<=mod<=10^{9} $ ). Next $ m $ lines describe the queries. Each query is defined by four integers $ l $ , $ r $ , $ u $ , $ v $ ( $ 1<=l<=r<=n $ , $ 1<=u<=v<=10^{18} $ ). Please do not use the %lld specificator to read or write 64-bit integers in C++. Use %I64d specificator.
输出格式
Print $ m $ lines each containing an integer — remainder modulo $ mod $ of the query result.
输入输出样例
输入样例 #1
4 5 10000
2 3 4 5
2 4 1 3
1 2 2 4
2 3 3 5
1 3 3 4
输出样例 #1
0
5
3
3
3
输入样例 #2
2 5 10000
1 2 2 2
1 1 4 5
1 1 2 5
1 1 1 3
1 2 5 5
输出样例 #2
2
0
0
1
0