J. 2D Travel
观察到 \(L, R\) 和 \(U, D\) 相互独立, 那么分成两个一样的子问题.
这里讨论 \(L, R\):
我们发现可以快速地求从当前点开始什么时候撞墙, 线段树上二分即可, 但是每次询问撞墙的次数是 \(O(n)\) 的, 直接写会 TLE.
考虑前后两次撞墙的关系: 撞墙后一定在 \(0\) 或者 \(n\), 那么我们预处理从 \(1\sim k\) 操作开始, 初始 \(x = 0\ or\ n\) 的情况下下一步撞墙会是哪个操作/ \(x\) 的位置/走的路程.
运用倍增思想: 预处理 \(2^i\) 次撞墙, 这样就可以在 \(log(n)\) 下找到最后一次撞墙点, 剩下的前缀和即可.
注意细节, 还有cv的时候别忘记改变量().
我的代码:
template <class info, class tag>
class LSGT {
std::vector<info> node;
std::vector<tag> ta;
int siz;
void build(int idx, int l, int r) {
if (l == r)
return;
int mid = (l + r) >> 1;
build(idx << 1, l, mid), build(idx << 1 | 1, mid + 1, r);
node[idx] = node[idx << 1] + node[idx << 1 | 1];
}
template <typename T>
void build(int idx, int l, int r, const std::vector<T> &vec) {
if (l == r) {
node[idx] = vec[l];
return;
}
int mid = (l + r) >> 1;
build(idx << 1, l, mid, vec), build(idx << 1 | 1, mid + 1, r, vec);
node[idx] = node[idx << 1] + node[idx << 1 | 1];
}
void apply(int idx) {
if (ta[idx].empty())
return;
ta[idx << 1].apply(ta[idx]);
ta[idx << 1 | 1].apply(ta[idx]);
node[idx << 1].apply(ta[idx]);
node[idx << 1 | 1].apply(ta[idx]);
ta[idx] = {};
}
void modify(int idx, int l, int r, int ql, int qr, const tag &add) {
if (ql <= l && qr >= r) {
ta[idx].apply(add);
node[idx].apply(add);
return;
}
apply(idx);
int mid = (l + r) >> 1;
if (ql <= mid)
modify(idx << 1, l, mid, ql, qr, add);
if (qr > mid)
modify(idx << 1 | 1, mid + 1, r, ql, qr, add);
node[idx] = node[idx << 1] + node[idx << 1 | 1];
}
info query(int idx, int l, int r, int ql, int qr) {
if (ql <= l && qr >= r)
return node[idx];
apply(idx);
int mid = (l + r) >> 1;
if (qr <= mid)
return query(idx << 1, l, mid, ql, qr);
else if (ql > mid)
return query(idx << 1 | 1, mid + 1, r, ql, qr);
else
return query(idx << 1, l, mid, ql, qr) + query(idx << 1 | 1, mid + 1, r, ql, qr);
}
int search(int idx, int l, int r, int ql, int qr, LL min, LL max) {
if (l == r) {
if (node[idx].max > max || node[idx].min < min)
return l;
else
return -1;
}
int mid = (l + r) >> 1;
if (ql <= mid && (node[idx << 1].max > max || node[idx << 1].min < min)) {
int d = search(idx << 1, l, mid, ql, qr, min, max);
if (d != -1)
return d;
}
if (qr > mid && (node[idx << 1 | 1].max > max || node[idx << 1 | 1].min < min)) {
return search(idx << 1 | 1, mid + 1, r, ql, qr, min, max);
}
return -1;
}
public:
LSGT(const int size) : node(size << 2), ta(size << 2), siz(size) {
build(1, 1, siz);
}
template <typename T>
LSGT(const std::vector<T> &vec) : node(vec.size() << 2), ta(vec.size() << 2), siz(vec.size() - 1) {
build(1, 1, siz, vec);
}
void modify(int ql, int qr, const tag &add) {
modify(1, 1, siz, ql, qr, add);
}
info query(int ql, int qr) {
return query(1, 1, siz, ql, qr);
}
int search(int ql, int qr, LL min, LL max) {
return search(1, 1, siz, ql, qr, min, max);
}
};
struct tag {
tag() {}
bool empty() const {
return 1;
}
void apply(const tag &o) {
return;
}
};
struct info {
long long max, min;
info() {}
info(long long x) : max(x), min(x) {}
info(long long max, long long min) : max(max), min(min) {}
info operator+(const info &o) const {
return info{std::max(max, o.max), std::min(min, o.min)};
}
void apply(const tag &o) {
return;
}
};
unordered_map<char, int> d{{'L', 0}, {'R', 0}, {'U', 1}, {'D', 1}}, dd{{'L', -1}, {'R', 1}, {'U', 1}, {'D', -1}};
unordered_map<char, char> pairofd{{'L', 'R'}, {'R', 'L'}, {'U', 'D'}, {'D', 'U'}};
void solve() {
int n, m, k, q;
cin >> n >> m >> k >> q;
vector<vector<LL>> sumofmv(2, vector<LL>(k + 1)); // lr, ud
vector<vector<LL>> sumoflength(2, vector<LL>(k + 1)); // lr, ud
vector nextfail(k + 2, vector(2, vector(20, array<LL, 3>()))); // [from][0,n/m][2^i][to/length/{0,n/m}]
vector<int> next(k + 2); // lr, ud
vector<int> nextlr(k + 1), nextud(k + 1);
for (int i = 0; i < 20; i++) nextfail[k + 1][0][i] = nextfail[k + 1][1][i] = {k + 1, 114514, 0};
vector<char> oper(k + 1);
for (int i = 1; i <= k; i++) {
char c;
int t;
cin >> c >> t;
oper[i] = c;
sumofmv[0][i] = sumofmv[0][i - 1];
sumofmv[1][i] = sumofmv[1][i - 1];
sumofmv[d[c]][i] += dd[c] * t;
sumoflength[0][i] = sumoflength[0][i - 1];
sumoflength[1][i] = sumoflength[1][i - 1];
sumoflength[d[c]][i] += t;
}
vector<int> tempnext(2, k + 1);
next[k + 1] = k + 1;
for (int i = k; i >= 0; i--) {
next[i] = tempnext[d[oper[i]]];
nextlr[i] = tempnext[0];
nextud[i] = tempnext[1];
tempnext[d[oper[i]]] = i;
}
LSGT<info, tag> tr[2]{sumofmv[0], sumofmv[1]}; // lr, ud
for (int i = 1; i <= k; i++) {
int tp = d[oper[i]];
LL min, max;
LL begin;
if (tp == 0) {
min = 0 + sumofmv[tp][i - 1], max = n + sumofmv[tp][i - 1];
begin = 0;
int d = tr[tp].search(i, k, min, max);
if (d == -1) {
nextfail[i][0][0] = {k + 1, 114514, 0};
} else {
LL leng = sumoflength[tp][d - 1] - sumoflength[tp][i - 1];
begin += sumofmv[tp][d - 1] - sumofmv[tp][i - 1];
if (oper[d] == 'L') {
leng += begin;
} else if (oper[d] == 'R') {
leng += n - begin;
} else if (oper[d] == 'U') {
leng += m - begin;
} else {
leng += begin;
}
nextfail[i][0][0] = {d, leng, dd[oper[d]] > 0};
}
min = -n + sumofmv[tp][i - 1], max = sumofmv[tp][i - 1];
begin = n;
d = tr[tp].search(i, k, min, max);
if (d == -1) {
nextfail[i][1][0] = {k + 1, 114514, 0};
} else {
LL leng = sumoflength[tp][d - 1] - sumoflength[tp][i - 1];
begin += sumofmv[tp][d - 1] - sumofmv[tp][i - 1];
if (oper[d] == 'L') {
leng += begin;
} else if (oper[d] == 'R') {
leng += n - begin;
} else if (oper[d] == 'U') {
leng += m - begin;
} else {
leng += begin;
}
nextfail[i][1][0] = {d, leng, dd[oper[d]] > 0};
}
} else {
min = sumofmv[tp][i - 1], max = m + sumofmv[tp][i - 1];
begin = 0;
int d = tr[tp].search(i, k, min, max);
if (d == -1) {
nextfail[i][0][0] = {k + 1, 114514};
} else {
LL leng = sumoflength[tp][d - 1] - sumoflength[tp][i - 1];
begin += sumofmv[tp][d - 1] - sumofmv[tp][i - 1];
if (oper[d] == 'L') {
leng += begin;
} else if (oper[d] == 'R') {
leng += n - begin;
} else if (oper[d] == 'U') {
leng += m - begin;
} else {
leng += begin;
}
nextfail[i][0][0] = {d, leng, dd[oper[d]] > 0};
}
min = -m + sumofmv[tp][i - 1], max = sumofmv[tp][i - 1];
begin = m;
d = tr[tp].search(i, k, min, max);
if (d == -1) {
nextfail[i][1][0] = {k + 1, 114514};
} else {
LL leng = sumoflength[tp][d - 1] - sumoflength[tp][i - 1];
begin += sumofmv[tp][d - 1] - sumofmv[tp][i - 1];
if (oper[d] == 'L') {
leng += begin;
} else if (oper[d] == 'R') {
leng += n - begin;
} else if (oper[d] == 'U') {
leng += m - begin;
} else {
leng += begin;
}
nextfail[i][1][0] = {d, leng, dd[oper[d]] > 0};
}
}
}
for (int x = 1; x < 20; x++) {
for (int y = 0; y < 2; y++) {
for (int i = 1; i <= k; i++) {
nextfail[i][y][x] = {nextfail[next[nextfail[i][y][x - 1][0]]][nextfail[i][y][x - 1][2]][x - 1][0],
nextfail[next[nextfail[i][y][x - 1][0]]][nextfail[i][y][x - 1][2]][x - 1][1] + nextfail[i][y][x - 1][1],
nextfail[next[nextfail[i][y][x - 1][0]]][nextfail[i][y][x - 1][2]][x - 1][2]};
}
}
}
while (q--) {
LL x, y, ll, rr;
cin >> x >> y >> ll >> rr;
LL leng = 0;
{
int l = ll, r = rr;
l = nextlr[l - 1];
int d;
if (l <= r)
d = tr[0].search(l, r, sumofmv[0][l - 1] - x, sumofmv[0][l - 1] + n - x);
else
d = -1;
if (d != -1) {
leng += sumoflength[0][d - 1] - sumoflength[0][l - 1];
x += sumofmv[0][d - 1] - sumofmv[0][l - 1];
int z;
if (oper[d] == 'L') {
leng += x;
z = 0;
} else {
leng += n - x;
z = 1;
}
for (int i = 19; i >= 0; i--) {
if (nextfail[next[d]][z][i][0] <= r) {
auto [a, b, c] = nextfail[next[d]][z][i];
d = a, leng += b, z = c;
}
}
l = min<int>(next[d], r + 1);
if (z == 0)
x = 0;
else
x = n;
}
x += sumofmv[0][r] - sumofmv[0][l - 1];
leng += sumoflength[0][r] - sumoflength[0][l - 1];
}
{
int l = ll, r = rr;
l = nextud[l - 1];
int d;
if (l <= r)
d = tr[1].search(l, r, sumofmv[1][l - 1] - y, sumofmv[1][l - 1] + m - y);
else
d = -1;
if (d != -1) {
leng += sumoflength[1][d - 1] - sumoflength[1][l - 1];
y += sumofmv[1][d - 1] - sumofmv[1][l - 1];
int z;
if (oper[d] == 'D') {
leng += y;
z = 0;
} else {
leng += m - y;
z = 1;
}
for (int i = 19; i >= 0; i--) {
if (nextfail[next[d]][z][i][0] <= r) {
auto [a, b, c] = nextfail[next[d]][z][i];
d = a, leng += b, z = c;
}
}
l = min<int>(next[d], r + 1);
if (z == 0)
y = 0;
else
y = m;
}
y += sumofmv[1][r] - sumofmv[1][l - 1];
leng += sumoflength[1][r] - sumoflength[1][l - 1];
}
cout << x << ' ' << y << ' ' << leng << '\n';
}
}