专栏文章

题解：P3992 [BJOI2017] 开车

llovely_nst
P3992题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipa0eux
此快照首次捕获于
2025/12/03 08:36
3 个月前
此快照最后确认于
2025/12/03 08:36
3 个月前
查看原文

P3992 [BJOI2017] 开车

前言

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

正文

考虑不带修。首先将 aa 与 bb 的元素放入 cc 排序并去重，设第 ii 位及其以前车的数量减加油站的数量为 sis_i，wi=ci+1−ciw_i=c_{i+1}-c_i 则答案可以转换为
∑i=1n×2−1∣si∣×wi\sum_{i=1}^{n\times 2-1}|s_i|\times w_i
为什么呢？因为若前面少了车（si<0s_i<0）则后面一定有车来补，那就一定会经过 [ci,ci+1][c_i,c_{i+1}]，于是贡献就要加上 wiw_i；而当前面多了车（si>0s_i>0），同理，前面的车也一定要补后面，贡献是一样的。而这样的车又有 ∣si∣|s_i| 个，于是就得到上面的式子。
那带修怎么做？现在的 cc 还要加上修改的位置元素，之后考虑分块维护几样东西：
  1. 加数 tagtag
  2. up=∑si+tag≥0si×wiup=\sum_{s_i+tag\ge 0} s_i\times w_i
  3. down=∑si+tag<0−si×widown=\sum_{s_i+tag<0} -s_i\times w_i
  4. upcnt=∑si+tag≥0wiupcnt=\sum_{s_i+tag\ge 0} w_i
  5. downcnt=∑si+tag<0widowncnt=\sum_{s_i+tag<0} w_i
  6. cnti=∑sk=iwkcnt_i=\sum_{s_k=i} w_k
散块暴力重构是简单的。而每次修改可以看作对一段区间的 sis_i 进行 ±1\pm 1 操作。当是 −1-1 操作时（pos<newpospos<newpos）：
newupcnt=∑si+tag>0wi=upcnt−cnt−tagnewup=up−∑si+tag>0wi=up−newupnewdowncnt=∑si+tag≤0wi=downcnt+cnt−tagnewdown=down+∑si+tag≤0wi=down+newdownnewtag=tag−1newupcnt=\sum_{s_i+tag>0}w_i=upcnt-cnt_{-tag}\\ newup=up-\sum_{s_i+tag>0}w_i=up-newup\\ newdowncnt=\sum_{s_i+tag\le0}w_i=downcnt+cnt_{-tag}\\ newdown=down+\sum_{s_i+tag\le0}w_i=down+newdown\\ newtag=tag-1
当是 +1+1 操作时（pos>newpospos>newpos）：
newupcnt=∑si+tag≥−1wi=upcnt+cnt−tag−1newup=up+∑si+tag≥0wi=up+upcntnewdowncnt=∑si+tag<−1wi=downcnt−cnt−tag−1newdown=down−∑si+tag<0wi=down−newdownnewtag=tag+1newupcnt=\sum_{s_i+tag\ge-1}w_i=upcnt+cnt_{-tag-1}\\ newup=up+\sum_{s_i+tag\ge0}w_i=up+upcnt\\ newdowncnt=\sum_{s_i+tag<-1}w_i=downcnt-cnt_{-tag-1}\\ newdown=down-\sum_{s_i+tag<0}w_i=down-newdown\\ newtag=tag+1
最后的答案就是：
∑i=1Bupi+downi\sum_{i=1}^{B} up_i+down_i

AC Code

CPP
#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;
}
最后提供一组大样例。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...