题解：P3992 [BJOI2017] 开车

lovely_nst · 2025-05-17 19:47:16 · 题解

P3992 [BJOI2017] 开车

前言

分块好题。

本文讲述的算法总复杂度为 O(q\log n+q\sqrt{n}\log n)，其中瓶颈在桶（unordered_map）。

正文

考虑不带修。首先将 a 与 b 的元素放入 c 排序并去重，设第 i 位及其以前车的数量减加油站的数量为 s_i，w_i=c_{i+1}-c_i 则答案可以转换为

为什么呢？因为若前面少了车（s_i<0）则后面一定有车来补，那就一定会经过 [c_i,c_{i+1}]，于是贡献就要加上 w_i；而当前面多了车（s_i>0），同理，前面的车也一定要补后面，贡献是一样的。而这样的车又有 |s_i| 个，于是就得到上面的式子。

那带修怎么做？现在的 c 还要加上修改的位置元素，之后考虑分块维护几样东西：

1. 加数 tag

2. up=\sum_{s_i+tag\ge 0} s_i\times w_i
3. down=\sum_{s_i+tag<0} -s_i\times w_i
4. upcnt=\sum_{s_i+tag\ge 0} w_i
5. downcnt=\sum_{s_i+tag<0} w_i
6. cnt_i=\sum_{s_k=i} w_k

散块暴力重构是简单的。而每次修改可以看作对一段区间的 s_i 进行 \pm 1 操作。当是 -1 操作时（pos<newpos）：

当是 +1 操作时（pos>newpos）：

最后的答案就是：

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4 + 5 , M = 2e5 , B_ = 500;
int n , m;
int a[N] , b[N] , d[N] , p[N] , s[M] , w[M];
vector <pair <int , int> > S;
int B , id[M] , tag[B_] , s_[B_] , t_[B_] , up[B_] , down[B_] , upcnt[B_] , downcnt[B_];
unordered_map <int , int> cnt[B_];

void rbd (int pid)
{
    cnt[pid].clear ();
    for (int i = s_[pid];i <= t_[pid];i ++)
        s[i] += tag[pid];
    tag[pid] = up[pid] = down[pid] = upcnt[pid] = downcnt[pid] = 0;
    for (int i = s_[pid];i <= t_[pid];i ++)
    {
        cnt[pid][s[i]] += w[i];
        if (s[i] >= 0) up[pid] += w[i] * s[i] , upcnt[pid] += w[i];
        else down[pid] -= w[i] * s[i] , downcnt[pid] += w[i];
    }
}

void upd (int l , int r , int C)
{
    if (r > n) r = n;
    int lid = id[l] , rid = id[r];
    if (lid == rid)
    {
        for (int i = l;i <= r;i ++)
            s[i] += C;
        rbd (lid);
        return ;
    }
    for (int i = l;id[i] == lid;i ++)
        s[i] += C;
    rbd (lid);
    for (int i = lid + 1;i < rid;i ++)
    {
        if (C == 1) up[i] += upcnt[i] , upcnt[i] += cnt[i][-tag[i] - 1] , down[i] -= downcnt[i] , downcnt[i] -= cnt[i][-tag[i] - 1];
        else upcnt[i] -= cnt[i][-tag[i]] , up[i] -= upcnt[i] , downcnt[i] += cnt[i][-tag[i]] , down[i] += downcnt[i];
        tag[i] += C;
    }
    for (int i = r;id[i] == rid;i --)
        s[i] += C;
    rbd (rid);
}
vector <pair <int , int> > unique ()
{
    vector <pair <int , int> > ans;
    int lst = -1 , sum = 0;
    for (auto it : S)
    {
        if (lst == it.first) sum += it.second;
        else
        {
            if (lst != -1) ans.push_back ({lst , sum});
            lst = it.first , sum = it.second;
        }
    }
    ans.push_back ({lst , sum});
    return ans;
}
signed main ()
{
    ios::sync_with_stdio (0); cin.tie (0) , cout.tie (0);
    cin >> n;
    for (int i = 1;i <= n;i ++) cin >> a[i] , S.push_back ({a[i] , 1});
    for (int i = 1;i <= n;i ++) cin >> b[i] , S.push_back ({b[i] , -1});
    cin >> m;
    for (int i = 1;i <= m;i ++) cin >> d[i] >> p[i] , S.push_back ({p[i] , 0});
    sort (S.begin () , S.end ());
    S = unique ();
    int l = S.size ();
    S.push_back ({2e9 , 0});
    for (int i = 1;i <= l;i ++)
        s[i] = s[i - 1] + S[i - 1].second , w[i] = S[i].first - S[i - 1].first;
    int ans = 0;
    n = l - 1;
    int cc = 0;
    B = sqrt (n);
    for (int i = 1;i <= n;i += B)
    {
        s_[++ cc] = i , t_[cc] = min (i + B - 1 , n);
        for (int j = s_[cc];j <= t_[cc];j ++) id[j] = cc;
        rbd (cc);
        ans += up[cc] + down[cc];
    }
    cout << ans << '\n';
    for (int i = 1;i <= m;i ++)
    {
        int P = lower_bound (S.begin () , S.end () , (pair <int , int>){a[d[i]] , 1e9}) - S.begin ();
        a[d[i]] = p[i];
        int Q = lower_bound (S.begin () , S.end () , (pair <int , int>){a[d[i]] , 1e9}) - S.begin ();
        if (P < Q)
            upd (P , Q - 1 , -1);
        else if (P > Q)
            upd (Q , P - 1 , 1);
        ans = 0;
        for (int j = 1;j <= cc;j ++)
            ans += up[j] + down[j];
        cout << ans << '\n';
    return 0;
}

最后提供一组大样例。