题解：P14977 [USACO26JAN1] Lineup Queries S

· · 题解

观察表。

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

发现我打点的位置左下方的每个元素都是在持续向左下“转”的，转到边界就会回到下一行的分界线。画一画发现分界线左下方的点满足 x\times2-t\le1，于是我们模拟这个过程即可。

查询一：

对于每个元素，它先不动，之后进入“转”，进入转的时间满足 x\times2-t=1，我们就可以解出它进入转的时间。（x=0 需要特判。）

之后模拟向左下方转的过程，如果在转到 x=0 前会经过查询的时间 t，就可以直接输出了。

否则我们算出它转到 x=0 的时间，再算一下几个时间点的上图打点的位置，把它挪过去接着算即可。

查询二：

和查询一相同，不断向右上挪，如果再挪一步会跑出 x\times2-t\le1，则停下来。

如果恰好 x\times2-t=1，那么这个元素会离开“转”，直接输出 x 即可。最终总会立刻或者 t=0。

代码不是太难，时间复杂度 O(T\times\log_2n)。

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

// signed main() {
    // vector<int> v{0};
    // for (int t = 1; t <= 99; t++) {
        // v.insert(v.begin() + (t + 2) / 2, v[0]);
        // v.erase(v.begin());
        // v.push_back(t);
        // printf("%2d : ", t);
        // for (int i : v) {
            // printf("%3d", i);
        // }
        // cout << endl;
    // }
    // return 0;
// }
int T, op, x, t;
signed main() {
    cin >> T;
    while (T--) {
        cin >> op >> x >> t;
        if (op == 1) {
            if (x == 0 && t <= 1) {
                cout << "0\n";
                continue;
            }
            if (x >= t / 2 + 1) {
                cout << x << '\n';
                continue;
            }
            int nowt = (x ? x * 2 - 1 : 1);
            while (1) {
                int endt = nowt + x;
                if (t <= endt) {
                    x -= t - nowt;
                    break;
                } else {
                    nowt = endt + 1;
                    x = nowt / 2;
                }
            }
            cout << x << '\n';
        } else {
            while (x * 2 - t < 1) {
                int d = 1 - (x * 2 - t);
                d /= 3;
                t -= d;
                x += d;
                if (x * 2 - t < 1) {
                    t--;
                    x = 0;
                }
            }
            cout << x << endl;
        }
    }
}

/*

t-- x++

x*2-t<=1

*/