分块进阶

· · 个人记录

P2801 教主的魔法

与上次做的最后一题一样，上次做的是找小于 c，这次是大于等于 c，所以我们 copy 一下，答案就是 (r - l + 1) - ask(l,r,k)。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e6 + 10;

int n, m, L[N], R[N], pos[N], lazy[N], sum[N], a[N];
vector<int> G[N];

void init() {
    int len = sqrt(n);
    int num = n / len;
    if (n % len != 0) {
        num++;
    }
    for (int i = 1; i <= num; i++) {
        L[i] = (i - 1) * len + 1;
        R[i] = i * len;
    }
    R[num] = n;
    for (int i = 1; i <= num; i++) {
        for (int j = L[i]; j <= R[i]; j++) {
            pos[j] = i;
            G[i].push_back(a[j]);
        }
        sort(G[i].begin(), G[i].end());
    }
}

void EA(int l, int r, int k) {
    int p = pos[l];
    for (int i = l; i <= r; i++) {
        a[i] += k;
    }
    G[p].clear();
    for (int i = L[p]; i <= R[p]; i++) {
        G[p].push_back(a[i]);
    }
    sort (G[p].begin(), G[p].end());
}

void change(int l, int r, int val) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        EA(l, r, val);
        return;
    }
    EA(l, R[p], val);
    EA(L[q], r, val);
    for (int i = p + 1; i <= q - 1; i++) {
        lazy[i] += val;
    }
}

int query(int l, int r, int k) {
    vector<int> v;
    for (int i = l; i <= r; i++) {
        v.push_back(a[i] + lazy[pos[l]]);
    }
    sort(v.begin(), v.end());
    return lower_bound(v.begin(), v.end(), k) - v.begin();
}

int ask(int l, int r, int k) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        return query(l, r, k);
    }
    int ans = 0;
    ans += query(l, R[p], k) + query(L[q], r, k);
    for (int i = p + 1; i <= q - 1; i++) {
        ans += lower_bound(G[i].begin(), G[i].end(), k - lazy[i]) - G[i].begin();
    } 
    return ans;
}

signed main() {
  cin.tie(0), cout.tie(0)->sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    init();
    while (m--) {
        char op;
        int l, r, k;
        cin >> op >> l >> r >> k;
        if (op == 'M') {
            change(l, r, k);
        } else {
            cout << (r - l + 1) - ask(l, r, k) << '\n';
        }
    }
    return 0;
}

P3793 由乃救爷爷

st 表空间炸，分块时间炸，所以考虑 st 表 + 分块。

用 st 表预处理每个块，再记录每个块的前缀最大值和后缀最大值。

对于每个完整的块，用 st 表查询，散块两端用前后缀最大值维护。

#include <bits/stdc++.h>
#define ull unsigned long long

using namespace std;

const int N = 3e7 + 5;

int n, m, a[N], p[N], q[N], dp[5005][13], L[5005], R[5005], pos[N], num;
unsigned s;

namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}

void init() {
    int len = sqrt(n);
    int num = n / len + (n % len > 0);
    for (int i = 1; i <= num; i++) {
        L[i] = (i - 1) * len + 1;
        R[i] = i * len;
    }
    R[num] = n;
    for (int i = 1; i <= num; i++) {
        for (int j = L[i]; j <= R[i]; j++) {
            pos[j] = i;
            dp[i][0] = max(dp[i][0], a[j]);
        }
        p[L[i]] = a[L[i]], q[R[i]] = a[R[i]];
        for (int j = L[i] + 1; j <= R[i]; j++) {
            p[j] = max(p[j - 1], a[j]);
        }
        for (int j = R[i] - 1; j >= L[i]; j--) {
            q[j] = max(q[j + 1], a[j]);
        }
    }
    for (int j = 1; (1 << j) <= num; j++) {
        for (int i = 1; i + (1 << j) - 1 <= num; i++) {
            dp[i][j] = max(dp[i][j - 1], dp[i + (1 << j - 1)][j - 1]);
        }
    } 
}

int query(int l, int r) {
    if (l > r)
        return 0;
    int lg = log2(r - l + 1);
    return max(dp[l][lg], dp[r - (1 << lg) + 1][lg]);
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> m >> s;
    srand(s);
    for (int i = 1; i <= n; i++) {
        a[i] = read();
    }
    init();
    ull sum = 0;    
    while (m--) {
        int l = read() % n + 1, r = read() % n + 1;
        if (l > r)
            swap(l, r);
        int x = pos[l], y = pos[r];
        int tmp = 0;
        if (x == y) {
            for (int i = l; i <= r; i++) {
                tmp = max(tmp, a[i]);
            }
        } else {
            tmp = query(x + 1, y - 1);
            tmp = max(tmp, max(q[l], p[r]));
        }
        sum += tmp;
    }
    cout << sum;
    return 0;
}

P4879 ycz的妹子

有 0 的情况，要用数组存一下。

C 的修改就直接改。

I 有妹子就覆盖，没妹子个数就加进去。

D 对于每个块里妹子个数来找，找到了就赋值为 0。

Q 就是求和。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e6 + 10;

int n, m, a[N], L[N], R[N], pos[N], sum[N], cnt[N], num, len;
bool vis[N];

void init() {
    len = sqrt(n);
    num = n / len;
    if (n % len != 0) {
        num++;
    }
    for (int i = 1; i <= num; i++) {
        L[i] = (i - 1) * len + 1;
        R[i] = i * len;
    }
    R[num] = n;
    for (int i = 1; i <= num; i++) {
        for (int j = L[i]; j <= R[i]; j++) {
            pos[j] = i;
            sum[i] += a[j];
            if (vis[j])
                cnt[i]++;
        }
    }
    return;
}

void change(int l, int r, int c) {
    int p = pos[l];
    int q = pos[r];
    if (p == q) {
        for (int i = l; i <= r; i++) {
            if (!vis[i])
                continue;
            a[i] += c;
        }
        sum[p] += (r - l + 1) * c;
        return;
    } else {
        for (int i = l; i <= R[p]; i++) {
            if (!vis[i])
                continue;
            a[i] += c;
            sum[p] += c;
        }
        for (int i = L[q]; i <= r; i++) {
            if (!vis[i])
                continue;
            a[i] += c;
            sum[q] += c;
        }
        return;
    }
}

int check(int l, int r) {
    int p = pos[l];
    int q = pos[r], ans = 0;
    if (p == q) {
        for(int i = l; i <= r; i++) {
            ans += a[i];
        }
        return ans;
    } else {
        for (int i = l; i <= R[p]; i++) {
            ans += a[i];
        }
        for (int i = L[q]; i <= r; i++) {
            ans += a[i];
        }
        p++;
        q--;
        for (int i = p; i <= q; i++) {
            ans += sum[i];
        }
        return ans;
    }
}

void calc1(int l, int c) {
    int p = pos[l];
    sum[p] -= a[l];
    a[l] = c;
    sum[p] += c;
    if (!vis[l]) {
        cnt[p] ++;
    }
    vis[l] = 1;
}

void calc2(int l) {
    int ans = 0;
    for (int i = 1; i <= num; i++) {
        ans += cnt[i];
        if (ans >= l) {
            ans -= cnt[i];
            for (int j = L[i]; j <= R[i]; j++) {
                if (vis[j]) {
                    ans ++;
                }
                if (ans == l) {
                    vis[j] = 0;
                    sum[i] -= a[j];
                    a[j] = 0;
                    cnt[i] --;
                    break;
                }
            }
            break;
        }
    }
}

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        vis[i] = 1;
    }
    n = 5e5;
    init();
    while (m--) {
        char opt;
        int l, r, c;
        cin >> opt;
        if (opt == 'C') {
            cin >> l >> c;
            change(l , l , -c);
        } else if (opt == 'I') {
            cin >> l >> c;
            calc1(l , c);
        } else if (opt == 'D') {
            cin >> l;
            calc2(l);
        } else {
            cout << check(1 , n) << "\n";
        }
    }
    return 0;
}

P4109 [HEOI2015] 定价

末尾 0 越多，移除后长度 a 越小，荒谬度可能越低，所以我们重点关注两类数：

根据上面模拟即可。

#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long

using namespace std;

int t;

int calc(int x) {
    int cnt1 = 0, cnt2 = 0;
    bool f = 0;
    while (x) {
        if (x % 10 != 0 && !f) {
            if (x % 10 == 5) {
                cnt2 = 1;
            }
            f = 1;
        }
        if (f) {
            cnt1++;
        }
        x /= 10;
    }
    return 2 * cnt1 - cnt2;
}

signed main() {
    for (cin >> t; t--;) {
        int l, r;
        cin >> l >> r;
        int minn = 1e18, rr;
        if (l % 1000 != 0) {
            rr = l - l % 1000 + 1000;
        } else {
            rr = l;
        }
        rr = min(rr, r);
        int idx = 0;
        for (int i = l; i <= rr; i++) {
            int x = calc(i);
            if (x < minn) {
                minn = x, idx = i;
            }
        }
        for (int i = rr; i <= r; i += 1000) {
            int x = calc(i);
            if (x < minn) {
                minn = x, idx = i;
            } 
        }
        cout << idx << '\n';
    }
    return 0;
}

P5356 [Ynoi Easy Round 2017] 由乃打扑克

跟上次第一题蛮像。

查询时使用二分，确定二分范围，遍历区间涉及的所有块，同步被标记为修改过的块，获取区间内元素的最小值（lt）和最大值（rt），作为二分初始范围。

查询时上一题一样用 lower_bound。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e6 + 10;

int n, m, L[N], R[N], pos[N], lazy[N], a[N];
vector<int> G[N];
bool vis[N];    

void init() {
    int len = sqrt(n);
    int num = n / len;
    if (n % len != 0) {
        num++;
    }
    for (int i = 1; i <= num; i++) {
        L[i] = (i - 1) * len + 1;
        R[i] = i * len;
    }
    R[num] = n;
    for (int i = 1; i <= num; i++) {
        for (int j = L[i]; j <= R[i]; j++) {
            pos[j] = i;
            G[i].push_back(a[j]);
        }
        sort(G[i].begin(), G[i].end());
    }
}

void EA(int p) {
    G[p].clear();
    for (int i = L[p]; i <= R[p]; i++) {
        a[i] += lazy[p];
        G[p].push_back(a[i]);
    }
    sort (G[p].begin(), G[p].end());
    lazy[p] = 0;
    vis[p] = 0;
}

int check(int l, int r, int k) {
    int p = pos[l], q = pos[r], ans = 0;
    if (p == q) {
        for (int i = l; i <= r; i++) {
            if (a[i] + lazy[p] < k) {
                ans++;
            }
        }
        return ans;
    }
    for (int i = l; i <= R[p]; i++) {
        if (a[i] + lazy[p] < k) {
            ans++;
        }
    }
    for (int i = L[q]; i <= r; i++) {
        if (a[i] + lazy[q] < k) {
            ans++;
        }
    }
    for (int i = p + 1; i <= q - 1; i++) {
        if (G[i][0] >= k - lazy[i])
            continue;
        int tmp = G[i].size() - 1;
        if (G[i][tmp] < k - lazy[i]) {
            ans += R[i] - L[i] + 1;
            continue;
        }
        ans += lower_bound(G[i].begin(), G[i].end(), k - lazy[i]) - G[i].begin();
    }
    return ans;
}

void change(int l, int r, int val) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        for (int i = l; i <= r; i++) {
            a[i] += val;
        }
        vis[p] = 1;
        return;
    }
    for (int i = p + 1; i <= q - 1; i++) {
        lazy[i] += val;
    }
    for (int i = l; i <= R[p]; i++) {
        a[i] += val;
    }
    for (int i = L[q]; i <= r; i++) {
        a[i] += val;
    }
    vis[p] = vis[q] = 1;
}

int query(int l, int r, int k) {
    int lt = 1e9, rt = -1e9, p = pos[l], q = pos[r];
    for (int i = p; i <= q; i++) {
        if (vis[i]) {
            EA(i);
        }
        lt = min(lt, G[i][0] + lazy[i]);
        rt = max(rt, G[i][G[i].size() - 1] + lazy[i]);
    }
    lt--, rt++;
    if (k > r - l + 1) {
        return -1;
    }
    while (lt + 1 < rt) {
        int mid = lt + rt >> 1;
        int tmp = check(l, r, mid);
        if (tmp > k - 1) {
            rt = mid;
        } else {
            lt = mid;
        }
    }
    return rt - 1;
}

signed main() {
    cin.tie(0), cout.tie(0)->sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    init();
    while (m--) {
        int opt, l, r, c;
        cin >> opt >> l >> r >> c;
        if (opt == 1) {
            cout << query(l, r, c) << '\n';
        } else {
            change(l, r, c);
        }
    }
    return 0;
}

P3203 [HNOI2010] 弹飞绵羊

对于 change 函数，预处理能到的点，从 x 在的块从右往左枚举位置 i，to_i = i + a_i。

若 to_i 超出当前块的右边界，则一步就行 step_i = 1。

否则，step_i = step_{to_i} + 1，且 to_i = to_{i + a_i}。

查询时，直接根据 step_i 记录答案即可。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e6 + 10;

int n, a[N], L[N], R[N], pos[N], to[N], step[N], q;

void init() {
    int len = sqrt(n), num = n / len + (n % len > 0);
    for (int i = 1; i <= num; i++) {
        L[i] = (i - 1) * len + 1;
        R[i] = i * len;
    }
    R[num] = min(R[num], n);
    for (int i = 1; i <= num; i++) {
        for (int j = L[i]; j <= R[i]; j++) {
            pos[j] = i;
        }
    }
}

int query(int x) {
    int ans = 0;
    while (x <= n) {
        ans += step[x];
        x = to[x];
    }
    return ans;
}

void change(int x, int y) {
    a[x] = y;
    for (int i = R[pos[x]]; i >= L[pos[x]]; i--) {
        to[i] = i + a[i];
        if (to[i] > R[pos[i]]) {
            step[i] = 1;
        } else {
            step[i] = step[to[i]] + 1;
            to[i] = to[i + a[i]];
        }
    }
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    init();
    for (int i = n; i >= 1; i--) {
        to[i] = a[i] + i;
        if (to[i] > R[pos[i]]) {
            step[i] = 1;
        } else {
            step[i] = step[to[i]] + 1;
            to[i] = to[i + a[i]];
        }
    }
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        y++;
        if (x == 1) {
            cout << query(y) << '\n';
        } else {
            int k;
            cin >> k;
            change(y, k);
        }
    }
    return 0;
}