阅读这篇题解前，请先阅读我的银组第一题题解并深刻理解分界线和“转”理论。这里应该会讲一个比较形象的理论。

查询包括时间、人、目标。到底用银组第一题第一问的“转人”还是第二问的“倒着转目标”？

思考发现，连续的人经过转，如果达到最左侧，会在回到最右侧的过程中被插入新的人，无法维护。但是“倒着转目标”发现不会发生这种情况。

怎么形容我的想法呢？

把一个胡萝卜放在一个由大量刀片组成的板上刮，会刮出胡萝卜丝，这是很重要的结论，之后胡萝卜会缩小，你会获得连续的一段胡萝卜丝。

观察这个 $2x-t\in[-1,1]$ 组成的线。这里拿出我在银组第一题题解中放的图。

t = 0 | 0.
t = 1 | 0.1.
t = 2 | 1 0.2
t = 3 | 0 1.2.3
t = 4 | 1 2 0.3 4
t = 5 | 2 0 1.3.4 5
t = 6 | 0 1 3 2.4 5 6
t = 7 | 1 3 2 0.4.5 6 7
t = 8 | 3 2 0 4 1.5 6 7 8
t = 9 | 2 0 4 1 3.5.6 7 8 9

如果一个目标被向右上不断转到恰好 $2x-t=1$，那么它就会退出左下方的“转”区。$x$ 就是答案。这就是我们的银组第一问。现在问题变成了一段目标转转转。

我们用同样的方法，先把 $r_2>\lfloor\frac t2\rfloor$ 的部分直接确定，把整个线段向右上方挪。这个线段经过 $2x-t\in[-1,1]$ 组成的线后，恰好踩到 $2x-t=1$ 的目标会被直接确定，因此每次刮会产生长度约等于当前长度 $\frac13$ 的确定目标，它们还是连续的，和 $[l_1,r_1]$ 求交后更新答案。模拟刮的过程求出最后的 $[l_2,r_2]$ 挪到的位置（这时刮完一次了显然新的 $l_2=0$），进行下一轮的移动和“刮”。

不断“刮”后产生 $\log_{\frac32}n$ 个连续段，模拟这个过程即可，时间复杂度 $O(T\times\log_{\frac32}n)$。

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
#define int long long
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vpii = vector<pii>;
int T, l1, r1, l2, r2, t, ans;
void check(int l, int r) {
	// cout << "check " << l << ' ' << r << endl;
	if (l < l1) {
		l = l1;
	}
	if (r > r1) {
		r = r1;
	}
	if (l <= r) {
		ans += r - l + 1;
	}
}
signed main() {
	cin >> T;
	while (T--) {
		cin >> l1 >> r1 >> l2 >> r2 >> t;
		ans = 0;
		if (l2 > t / 2) {
			check(l2, r2);
		} else {
			if (r2 > t / 2) {
				check(t / 2 + 1, r2);
				r2 = t / 2;
			}
			while (t > 0) {
				int d = 1 - r2 * 2 + t;
				d /= 3;
				l2 += d;
				r2 += d;
				t -= d;
				// cout << "move " << d << endl;
				// cout << '[' << l2 << ',' << r2 << "] " << t << endl;
				int f = 1 - r2 * 2 + t;
				// assert(f >= 0 && f <= 2);
				int c = r2 - l2 + 1;
				int g = (c + 2 - f) / 3;
				// cout << "got " << g << endl;
				check(r2 - g + 1, r2);
				if (t == 0) {
					break;
				}
				d = 1 - l2 * 2 + t;
				d /= 3;
				l2 += d;
				r2 += d;
				t -= d;
				// cout << "move " << d << endl;
				// cout << '[' << l2 << ',' << r2 << "] " << t << endl;
				if (t == 0) {
					break;
				}
				if (l2 * 2 - t == 1) {
					d--;
					l2--;
					r2--;
					t++;
				}
				r2 -= l2 + g;
				l2 = 0;
				t--;
				if (l2 < 0) {
					break;
				}
				// cout << '[' << l2 << ',' << r2 << "] " << t << endl;
			}
			if (l2 <= r2) {
				check(l2, r2);
			}
		}
		cout << ans << endl;
	}
	return 0;
}

(Analysis by Alexander Wang)

Subtask 1: $Q \leqslant 1000, t \leqslant 100$

Let $f(i, t)$ denote the position of cow $i$ at time $t$. Cow $i$ first joins the line at time $t = i$ at position $i$. At times $i \leqslant t \leqslant 2i - 1$, cow $i$ does not move. At every time $t \geqslant 2i$, cow $i$ either moves forward one position in line or moves to position $\lfloor \frac{t}{2} \rfloor$. This means we have the following recursive formula for $f(i, t)$:

$$f(i, t) = \begin{cases} i & i \leqslant t \leqslant 2i - 1 \\ f(i, t - 1) - 1 & f(i, t - 1) \neq 0, t \geqslant 2i \\ \lfloor \frac{t}{2} \rfloor & f(i, t - 1) = 0, t \geqslant 2i \end{cases}$$

We can directly compute the values of the sequence with this recursion and check whether $l_2 \leqslant f(i, t) \leqslant r_2$ for each $l_1 \leqslant i \leqslant r_1$.

Subtask 2: $l_1 = r_1$

We need a faster method to compute $f(i, t)$ for large $t$. In this subtask, we only need to compute $f(i, t)$ for one value $i = l_1 = r_1$. We can speed up the calculation by observing that if $f(i, t') = 0$, then $f(i, t' + 1) = \lfloor \frac{t' + 1}{2} \rfloor$, so $f(i, t' + 1 + k) = \lfloor \frac{t' + 1}{2} \rfloor - k$ for all $0 \leqslant k \leqslant \lfloor \frac{t' + 1}{2} \rfloor$. This means that the next time which satisfies $f(i, t) = 0$ is $t' + 1 + \lfloor \frac{t' + 1}{2} \rfloor$. Therefore, if $i \leqslant t \leqslant 2i - 1$, we know $f(i, t) = i$. Otherwise, we have $f(i, 3i - 1) = 0$. Then, define the sequence $t_{i, 1} = 3i - 1$ and $t_{i, j} = t_{i, j - 1} + 1 + \lfloor \frac{t_{i, j - 1} + 1}{2} \rfloor$ for each positive integer $j \geqslant 1$. For convenience, define $t_{i, 0} = 2i - 1$. When $j > 0$, each $t_{i, j}$ satisfies $f(i, t_{i, j}) = 0$, so if $t_{i, j - 1} < t \leqslant t_{i, j}$, then $f(i, t) = t_{i, j} - t$. Since $t_j \geqslant \frac{3}{2} t_{j - 1}$ and $(\frac{3}{2})^{110} > 10^{18}$, we only need to compute at most 110 values of the sequence to calculate the value of $f(i, t)$, which is fast enough for subtask 2.

Full solution:

For each $l_1 \leqslant t \leqslant r_1$, there are two cases: $t \leqslant 2i - 1$ and $t \geqslant 2i$.

If $t \leqslant 2i - 1$, then $f(i, t) = i$. In the interval $l_1 \leqslant i \leqslant r_1$, the values of $i$ which satisfy this inequality are $\max \left( l_1, \frac{t + 1}{2} \right) \leqslant i \leqslant r_1$. Then, $l_2 \leqslant f(i, t) \leqslant r_2$ corresponds to the inequality $l_2 \leqslant i \leqslant r_2$. The values of $i$ that satisfy both inequalities are

$$\max \left( l_1, l_2, \frac{t + 1}{2} \right) \leqslant i \leqslant \min(r_1, r_2).$$

Therefore, the count of all such $i$ is equal to

$$\max \left( 0, \min(r_1, r_2) - \max \left( l_1, l_2, \left\lceil \frac{t + 1}{2} \right\rceil \right) + 1 \right).$$

If $t \geqslant 2i$, then $f(i, t) = t_{i, j} - t$ when $t_{i, j - 1} < t \leqslant t_{i, j}$ and $1 \leqslant j \leqslant 110$. Fix some $j$. The values of $i$ which satisfy $i \leqslant \frac{t}{2}$, $l_1 \leqslant i \leqslant r_1$, $l_2 \leqslant t_{i, j} - t \leqslant r_2$, $t \leqslant t_{i, j}$, and $t_{i, j - 1} < t$ form an interval. The last three inequalities simplify to $l_2 + t \leqslant t_{i, j} \leqslant r_2 + t$ and $t_{i, j - 1} \leqslant t - 1$.

To compute the interval of $i$ that satisfies these inequalities, we will calculate the maximum value of $i$ such that $t_{i, j} \leqslant x$ for some fixed $j$ and $x$. Since $t_{i, j}$ is an increasing function for fixed $j$, the values of $i$ which satisfy $t_{i, j} \leqslant x$ are exactly $i \leqslant a$ for some integer $a$. The inequality is always true when $j = 0$, so we can say that the maximum value of $i$ is a large number greater than $10^{18}$. When $j = 1$, the inequality is $3i - 1 \leqslant x$, so the maximum $i$ is $\lfloor \frac{x + 1}{3} \rfloor$. For $j \geqslant 2$, we use recursion to rewrite the inequality as $t_{i, j - 1} + 1 + \lfloor \frac{t_{i, j - 1} + 1}{2} \rfloor \leqslant x$. The inequality is true if and only if $t_{i, j - 1} \leqslant \lfloor \frac{2x - 2}{3} \rfloor$. If we define the function $g(n) = \lfloor \frac{2n - 2}{3} \rfloor$, then $t_{i, j} \leqslant x$ if and only if $t_{i, j - 1} \leqslant g(x)$. Therefore, we can continue this process to get $t_{i, j} \leqslant x$ if and only if $t_{i, 1} \leqslant g^{j - 1}(x)$, which simplifies to $3i - 1 \leqslant g^{j - 1}(x)$.

We can calculate the arrays $\text{inv1}[j] = g^{j - 1}(t - 1)$, $\text{inv2}[j] = g^{j - 1}(l_2 + t - 1)$, and $\text{inv3}[j] = g^{j - 1}(r_2 + t)$ for $1 \leqslant j \leqslant 110$ quickly, and set $\text{inv1}[0] = \text{inv2}[0] = \text{inv3}[0] > 10^{18}$. The inequalities $l_2 + t \leqslant t_{i, j} \leqslant r_2 + t$ and $t_{i, j - 1} \leqslant t - 1$ is equivalent to the inequalities $3i - 1 \leqslant \text{inv3}[j]$, $3i - 1 > \text{inv2}[j]$, and $3i - 1 \leqslant \text{inv1}[j - 1]$. Therefore, the number of $i$ in the interval described by these three inequalities and the two inequalities $i \leqslant \frac{t}{2}$ and $l_1 \leqslant i \leqslant r_1$ can be calculated in $O(1)$ time for each $j$.

The total time complexity is $O(110Q)$.

#include <bits/stdc++.h>
using namespace std;

vector<long long> inv(long long n) {
    vector<long long> ans;
    ans.push_back(400000000000000000);
    for(int i=0;i<111;i++) {
        ans.push_back(n);
        n = (2*n+4)/3-2;
    }
    return ans;
}

int main() {
    int q;
    cin >> q;
    while(q--) {
        long long l1, r1, l2, r2, t;
        cin >> l1 >> r1 >> l2 >> r2 >> t;

        long long ans = 0;
        vector<long long> inv1 = inv(t-1);
        vector<long long> inv2 = inv(l2+t-1);
        vector<long long> inv3 = inv(r2+t);
        for(int j=1;j<111;j++) {
            // l1 <= i <= min(t/2, r1)
            // 3*i-1 <= min(inv1[j-1], inv3[j])
            // 3*i-1 > inv2[j]
            long long low = max(l1, (inv2[j]+4)/3);
            long long high = min(min(t/2, r1), (min(inv1[j-1], inv3[j])+4)/3-1);
            ans += max(0LL, high-low+1);
        }

        // l1 <= i <= r1
        // l2 <= i <= r2
        // t <= 2*i-1
        ans += max(0LL, min(r1, r2) - max(max(l1, l2), t/2+1) + 1);
        cout << ans << endl;
    }
}