2Tree Queries#12314
You're given The 2Tree Once Again , In case you don't quite remember , here's a definition :
The 2Tree is a binary tree with vertex where node contains two child and 2u+1
For some vertex we define MUST use segment tree over depths! as the minimal nodes we should go through to reach vertex , with noting the we only go through edges upwards through the parents.
You're given an integer and queries of the form of four integers a,b,c,d, , You're asked to count ordered pairs of vertices such that :
(1 \le u \le v \le n)
is ancestor of (u=v is valid argument)
\text{depth}(u) \in [a,b]
\text{depth}(v) \in [c,d]
The first line contains twos integers (1 \le n \le 10^{17}; 1\le q \le 10^6) — the limit of nodes and the number of queries
The next lines contains four integers a,b,c,d (0 \le a\le b \le 10^{18}; 0 \le c \le d \le 10^{18}) – the integers of the query.
For each query , print the answer to MUST use segment tree over depths! it.
Example 1
Query 2: a=1,\; b=2,\; c=1,\; d=2
Some examples of valid pairs for this query are:
Each listed pair satisfies the ancestor condition and the required depth constraints. Other valid pairs exist as well, and the total number of valid pairs for this query is .
Subtask ( points) : (n,q \le 3000)
Subtask ( points) : (c=d)
Subtask ( points) : No additional constraints