P8211 [THUPC2022 初赛] 搬砖

· · 题解

以下设 B 为一个阈值，同时也表示值域分块的块长。

先考虑所有 b 都不为 0 的情况。对于一组询问，我们设一个 x 表示：当前已搬完所有 a\leq x 的砖。那么每次只可能是以下两种情况之一：

  1. 有至少一摞砖在当前这个单位时间内被搬完

    拿 x 加上 d，之后拿 d 减去 \sum_{a_i\in[x+1,x+d+1]}b_i。

  2. 没有砖搬完

    结束此过程。

对于单组询问，我们尝试分析其时间复杂度：

修改只需要维护一下上述值域分块即可。总时间复杂度 O(T(B+\frac{T}{B})+V(B+\frac{V}{B}))。

但是，原命题中实际存在 b=0 的情况，也就是上述方法可能会在一些数据下变成 O(n) 的，那我们又该如何应对？

易发现，复杂度退化只会在 d\leq\sqrt V 的情况下产生。故而考虑维护一个 O(\sqrt n) 修改、O(1) 查询 \geq i 的第一个非零位置的值域分块。同时对于每种 \leq\sqrt V 的 d 维护一个并查集，以求解 d 取当前值、x 为起点，最多能加到达哪里（具体操作见上述操作 1，可以认为这个维护是在只考虑“如果没有任何一摞砖被搬完，小E就会停止工作”这一条件下进行的）。

于是询问中 d\leq B 的部分，就可以用这两个数据结构去维护 x,d 了。

时间复杂度多个 \log，为并查集的复杂度（注意这里不能用按秩合并）。

#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); i++)
#define FR(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 1e5 + 170, C = 650;
int n, L, S;
inline char gc(){
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)? EOF : *p1++;
}
inline int read(){
    register char ch = gc(); register int sum = 0;
    while(!(ch >= '0' && ch <= '9')) ch = gc();
    while(ch >= '0' && ch <= '9') sum = sum * 10 + ch - 48, ch = gc();
    return sum;
}
inline void write(int x){
    if(x < 10){putchar('0' + x); return;}
    write(x / 10), putchar('0' + x % 10);
}
struct B1{
    int a[N + 10], t[C];
    void Upd(int x, int v){
        int b = x / L;
        FL(i, x, b * L + L - 1) a[i] += v;
        FL(i, b + 1, N / L) t[i] += v;
    }
    int Qry(int l, int r){
        l = min(l, N), r = min(r, N); 
        return a[r] + t[r / L] - a[l - 1] - t[(l - 1) / L];
    }
} b1, b2;
struct B3{
    int a[N + 10], t[C];
    B3(){fill(a, a + N + 1, 1e9), fill(t, t + C, 1e9);}
    void Upd(int x, int v){
        int b = x / L;
        FL(i, b * L, x) a[i] = min(a[i], v);
        FL(i, 0, b - 1) t[i] = min(t[i], v);
    }
    int Qry(int x){
        x = min(x, N); return min(a[x], t[x / L]);
    }
} b3;
struct DSU{
    int fa[N + 10];
    DSU(){FL(i, 0, N) fa[i] = i;}
    int F(int x){return fa[x] == x? x : fa[x] = F(fa[x]);}
} u[163];
int main(){
    n = read(), L = 160, S = N / L + 1;
    FL(id, 1, n){
        int op = read(), a, b, d, x = 0, ans = 0;
        if(op == 1){
            a = read(), b = read();
            b1.Upd(a, 1), b2.Upd(a, b);
            if(b) b3.Upd(a, a); int r = a;
            while(r < min(N, a + L) && !b1.Qry(r + 1, r + 1)) r++;
            FL(i, 1, L) FR(j, min(a - 1, r - i), a - i){
                if(j + i > N || j < 0 || u[i].fa[j] != j) break;
                u[i].fa[j] = j + i;
            }
        }
        else{
            d = read();
            while(d > 0){
                ans++; if(!b1.Qry(x + 1, x + d)) break;
                if(d <= L){
                    int y = min(b3.Qry(x + 1), u[d].F(x));
                    ans += (y - x - 1) / d, x += (y - x - 1) / d * d;
                }
                x += d, d -= b2.Qry(x - d + 1, x);
            }
            write(ans), putchar('\n');
        }
    }
    return 0;
}