COCI 2023/2024 #2 T3「Dizalo」详细题解

📋 标签: 传统 | ⏱️ 时间限制: 3000 ms | 💾 内存限制: 512 MiB

🎯 题目核心理解

问题建模

🏢 n层楼，n个人，第i个人想去a[i]层（a是1~n的排列）
🚪 电梯很窄，人排成一列：位置1最靠近门，位置n最远
📉 下电梯规则：某人要下时，他前面所有人都要暂时离开
🔄 返回策略：离开的人可以任意重排顺序返回（最优策略）
❓ 求：总共有多少次"离开电梯"的事件？

关键观察：最优返回策略

💡 核心思想：让目标楼层大的人先返回，楼层小的人后返回

举例：位置1,2,3的人暂时离开，目标楼层分别是3,1,4
❌ 错误顺序：3→1→4（位置1的人去3楼时，位置2的人还要再离开）
✅ 最优顺序：4→3→1（按楼层降序返回）

✨ 效果：已经下过电梯的人，按楼层降序排好后，
        后续下电梯时不会再让前面的人产生额外代价！

🔑 核心结论：后缀最小值

什么是后缀最小值？

初始序列：a = [3, 4, 1, 2, 5]（位置1~5的人的目标楼层）

从右往左扫描：

后缀最小值位置：3, 4, 5（对应值 1, 2, 5）

为什么只有后缀最小值产生贡献？

🎯 关键性质：
   • 非后缀最小值：后面有目标楼层更小的人，那人会先下电梯
   • 后缀最小值：后面没有更小的人，他下电梯时前面未下的人都要离开

📐 贡献计算公式：
   对于后缀最小值位置 i，值为 a[i]
   
   前面大于 a[i] 的数的个数 
   = (全局大于 a[i] 的个数) - (i 后面大于 a[i] 的个数)
   = (n - a[i]) - (n - i) 
   = i - a[i]  ✨ 简洁！

📊 总答案 = n（每人自己下电梯1次）+ Σ(i - a[i])（所有后缀最小值的贡献）

🛠️ 数据结构设计

需要维护的信息

// 三个树状数组
bit1: 位置维度 - 位置 1~i 中未被删除的人数
bit2: 值域维度 - 值 1~i 中未被删除的人数  
bit3: 标记维度 - 位置 1~i 中是后缀最小值的个数

// set：维护当前所有后缀最小值 {值, 位置}，按值排序，用于二分查找
set<pair<int,int>> st;

// 线段树：维护区间最大值，用于离线确定"成为后缀最小值的时间"
// tr[p].c = 区间内所有位置"被删除时间"的最大值

离线处理：何时成为后缀最小值？

💡 核心问题：删除某些人后，原来不是后缀最小值的位置可能变成后缀最小值

🔍 判断条件：位置 i 成为后缀最小值 
   ⇔ i 后面所有满足 a[j]<a[i] 的位置 j 都被删除

⏰ 成为时间：max{ ti[j] | j>i 且 a[j]<a[i] }
   其中 ti[j] 表示位置 j 被删除的时间（询问序号），没被删除则为 Q+1

🔄 离线算法（倒序扫描）：
   for (int i = n; i >= 1; --i) {
       // 查询 [1, a[i]-1] 区间（值比 a[i] 小）的最大删除时间
       int become_time = seg.query(1, 1, a[i]-1);
       g[become_time].push_back(i);  // 记录：在 become_time 时刻，i 可能成为后缀最小值
       seg.update(1, a[i], ti[i]);   // 更新：值 a[i] 对应位置的删除时间
   }

📝 算法流程详解

初始化阶段

// 1. 读入数据，标记删除时间
for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    ti[i] = Q + 1;  // 默认不被删除
}
for (int i = 1; i <= Q; ++i) {
    cin >> va[i];
    ti[va[i]] = i;  // va[i] 在第 i 个询问被删除
}

// 2. 离线预处理：计算每个位置成为后缀最小值的时间
for (int i = n; i >= 1; --i) {
    int become_time = seg.query(1, 1, a[i]-1);
    g[become_time].emplace_back(i);
    seg.update(1, a[i], ti[i]);
}

// 3. 处理初始状态（时间 0 就成为后缀最小值的位置）
st.insert({0, 0}), st.insert({n+1, n+1});  // 哨兵
for (int i : g[0]) {
    sum += i - a[i];        // 累加贡献
    bit3.add(i, 1);         // 标记为后缀最小值
    vis[i] = 1;
    st.insert({a[i], i});   // 加入 set
}
cout << sum + n << " ";     // 输出初始答案

处理每个询问

for (int i = 1; i <= Q; ++i) {
    int pos = va[i];  // 第 i 个询问删除的位置
    del[pos] = true;
    
    // 🎯 情况 1：删除的是后缀最小值
    if (vis[pos]) {
        bit3.add(pos, -1);  // 取消标记
        // 减去它的贡献：前面大于它的数的个数
        sum -= bit1.query(pos) - bit2.query(a[pos]);
        st.erase({a[pos], pos});  // 从 set 移除
    }
    // 🎯 情况 2：删除的不是后缀最小值
    else {
        // 减去：它后面、比它小的后缀最小值的个数
        auto it = --st.lower_bound({a[pos], 0});
        sum -= bit3.query(it->second) - bit3.query(pos);
    }
    
    // 更新树状数组（位置和价值维度都删除这个数）
    bit1.add(pos, -1);
    bit2.add(a[pos], -1);
    
    // 🎯 检查：是否有新位置在此时成为后缀最小值？
    for (int j : g[i]) {
        if (del[j]) continue;
        bit3.add(j, 1);
        vis[j] = true;
        st.insert({a[j], j});
        sum += bit1.query(j) - bit2.query(a[j]);
    }
    
    // 输出当前答案：sum + 剩余人数 (n-i)
    cout << sum + n - i << " ";
}

🧮 样例验证

样例 1：n=5, a=[3,4,1,2,5], 询问=[3,2]

初始后缀最小值：位置 3(值 1), 4(值 2), 5(值 5)

贡献计算：
• 位置 3: 3-1 = 2（前面位置 1,2 的值 3,4 都>1）
• 位置 4: 4-2 = 2（前面位置 1,2 的值 3,4 都>2）
• 位置 5: 5-5 = 0
总贡献 = 4, 答案 = 4 + 5 = 9 ✓

删除位置 3 后：
• 减去位置 3 的贡献：2
• 位置 4 新贡献：bit1.query(4)-bit2.query(2) = 3-1 = 2
• 新答案 = (4-2+2) + 4 = 8? 

💡 注意：实际答案是 6，因为删除位置 3 后，
   位置 1,2 还在，但位置 4 要下时仍需他们离开，
   贡献计算需用树状数组动态维护当前未被删除的数！

⚡ 复杂度分析

📊 时间复杂度：
• 线段树/树状数组单次操作：O(log n)
• 每个位置最多成为 1 次后缀最小值，最多被处理 1 次
• 总操作数：O((n+q) log n) ✓

📊 空间复杂度：
• 树状数组×3 + 线段树 + set + vector：O(n) ✓

🎓 思维总结

✅ 本题核心思维链：

1️⃣ 最优策略 → 降序返回 → 已下电梯的人不产生额外代价

2️⃣ 额外代价来源 → 只有后缀最小值下电梯时，前面未下的人要离开

3️⃣ 贡献公式 → 后缀最小值 i 的贡献 = i - a[i]

4️⃣ 动态维护 → 删除操作可能改变"谁是后缀最小值"

5️⃣ 离线技巧 → 预处理每个位置"成为后缀最小值的时间"，按时间顺序激活

6️⃣ 数据结构组合拳：
   • 树状数组：快速查询区间计数
   • set：二分查找相邻后缀最小值
   • 线段树：离线预处理成为时间
   • vector 桶：按时间分组激活

✨ 难度：⭐⭐⭐⭐（思维 + 数据结构综合）
✨ 适合：熟悉树状数组/线段树后，练习"动态维护 + 离线处理"的好题

🔧 调试建议

// 调试时建议输出：
// 1. 每个时刻的后缀最小值集合
// 2. 当前 sum 值和各部分贡献
// 3. bit1/bit2/bit3 的关键查询结果

// 常见坑点：
⚠️ set.lower_bound 返回值是迭代器，--操作前确保不是 begin()
⚠️ 树状数组 query(x) 是 [1,x] 的和，注意边界
⚠️ 离线时 g 数组要开到 Q+2，因为 ti 可能是 Q+1
⚠️ 答案要 + 剩余人数 (n-已删除数)，不是固定 +n

💡 一句话总结：这道题的本质是动态维护后缀最小值集合，并用树状数组高效计算"前面大于它的数的个数"。离线预处理 + 时间桶激活是处理"删除后新成为后缀最小值"的关键技巧。

P9910「COCI 2023/2024 #2」dizalo 题解

知识点

树状数组，线段树，STL 库中的 set。

前言

这道题不错，使用了三个树状数组，一个线段树，一个 set，维护一系列基础的东西，但结合起来就变的复杂了。

各个操作不难，但思维含金量很高，适合刚熟悉树状数组和线段树的新手来做。

题意分析

先看到题目要求：求出所有人下电梯的总次数最少是多少。

题目说：“当一个人要下电梯时，所有在他前面的人也必须暂时下电梯，而每次临时下电梯的人总是以最优策略来决定返回电梯的顺序”，那么为了减小总次数，回来时肯定会让楼层大的先回来，楼层小的后回来，这样这一部分下过电梯的人在到达目标楼层时就都不会让站在他前面的人产生额外的下电梯次数，总次数也就不会再增加。

那么，哪些人会让他之前的人产生额外的下电梯次数使总次数增加呢？

之前已经说到临时下电梯的人不会让他之前的人产生额外的下电梯次数，那么会让他之前的人产生额外的下电梯次数的人就是在到达目标楼层之前都没下过电梯的人。

可以发现，这类人的目标楼层在序列中是一个后缀最小值，即在上电梯之前的序列中，在他之后 没有人的目标楼层比他小。而总次数也就是后缀最小值之前大于它的数的个数之和+总人数（每个人自己都要下一次电梯的）。

所以题目就是让我们求：第一次操作前以及每次操作之后的后缀最小值之前大于它的数的个数之和+总人数。

题解

离线题解

本代码有一条核心计算文字表达式：总次数 = 后缀最小值之前大于它的数的个数之和 + 总人数，而其中后缀最小值之前大于它的数的个数之和，就等于 大于后缀最小值的数的总个数 - 它后面大于它的数的个数 。

故我们开两个树状数组：分别维护编号为 $1 ~ i$ 的数中没被删除的数的个数，以及值为 $1 ~ i$ 的数中没被删除的数的个数 。加入或删除一个后缀最小值的问题就解决了。

还有不是后缀最小值的部分：删除时减去它后面比它小的后缀最小值即可。

我们再开一个 set 记后缀最小值和它的编号，用于查询时二分，和一个树状数组，记 $1 ~ i$ 区间后缀最小值个数。

至于什么时候什么数成为后缀最小值，开一个线段树，维护区间最大值，其中记在某数之后比它小的数的所有删除时间最大值，即成为一个所谓的后缀最小值的时间前一刻，我们可以把它离线下来进行操作。

详见代码：

#include<bits/stdc++.h>
#define ll long long
#define Pii pair<int,int>
#define S second
#define tomax(a,b) ((a)=max((a),(b)))
#define FOR(i,a,b) for(register int i=(a);i<=(b);++i)
#define DOR(i,a,b) for(register int i=(a);i>=(b);--i)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0);return Main();}signed Main
using namespace std;
const int N=1e5+10;
int n,Q;
int a[N],ti[N],va[N];
bool vis[N],del[N];
vector<int> g[N];
set< Pii > st;
ll sum=0;
struct Binary_Indexed_Trees {
#define lowbit(a) ((a)&(-a))
	int c[N],n;
	void init(int m) {
		n=m;
	}
	void build() {
		FOR(i,1,n)c[i]=1;
		FOR(i,1,n)if(i+lowbit(i)<=n)c[i+lowbit(i)]+=c[i];
	}
	void add(int x,int v) {
		for(; x<=n; x+=lowbit(x))c[x]+=v;
	}
	int query(int x) {
		int res=0;
		for(; x; x^=lowbit(x))res+=c[x];
		return res;
	}
} bit1,bit2,bit3;
/*bit1维护编号1~i中没被删除的数的个数*/
/*bit2维护值1~i中没被删除的数的个数*/
/*bit3维护区间后缀最小值个数*/
struct Segment_Tree {
#define ls (p<<1)
#define rs (p<<1|1)
	int n;
	struct node {
		int l,r,len,c;
	} tr[N<<2];
	void init(int _n) {
		return (void)(n=_n,build(1,n,1));
	}
	void push_up(int p) {
		tr[p].c=max(tr[ls].c,tr[rs].c);
	}
#define mid (tr[p].l+tr[p].r>>1)
	void build(int l,int r,int p) {
		tr[p]= {l,r,r-l+1,0};
		if(l==r)return;
		build(l,mid,ls),build(mid+1,r,rs);
	}//建树
	void update(int p,int x,int d) {
		if(tr[p].len==1)return tr[p].c=d,void();
		if(mid>=x)update(ls,x,d);
		else update(rs,x,d);
		push_up(p);
	}//修改
	int query(int p,int l,int r) {
		if(l<=tr[p].l&&tr[p].r<=r)return tr[p].c;
		int ans=0;
		if(mid>=l)tomax(ans,query(ls,l,r));
		if(mid<r)tomax(ans,query(rs,l,r));
		return ans;
	}//查询
#undef mid
} seg; //维护删除时间最大值.
signed main() {
	cin>>n>>Q;
	bit1.init(n),bit1.build();
	bit2.init(n),bit2.build();//O(n)建树
	bit3.init(n);
	seg.init(n);
	FOR(i,1,n)cin>>a[i],ti[i]=Q+1;
	FOR(i,1,Q)cin>>va[i],ti[va[i]]=i;//标记第va[i]个人是在第i个被删除的,即删除时间.
	/*输入+初始化*/
	DOR(i,n,1)g[seg.query(1,1,a[i]-1)].emplace_back(i),seg.update(1,a[i],ti[i]);
	//倒序求在某数之后比它小的数的所有删除时间最大值,seg.query(1,1,a[i]-1)就是该时间,即成为一个所谓的后缀最小值的时间前一刻,我们直接存入一个vector,以便查询.
	/*求成为后缀最小值的时间*/
	st.insert({0,0}),st.insert({n+1,n+1});
	for(int i:g[0]) {
		sum+=i-a[i];
		//这里基于一个数学推导:一开始作为一个后缀最小值,整个数组中大于它的有:n-a[i]个,他后面大于它的有:n-i个,那么前面大于它的就有:i-a[i]个.
		bit3.add(i,1);
		vis[i]=1;//标记已经成为后缀最小值的数.
		st.insert({a[i],i});
	}
	cout<<sum+n<<" ";
	/*输出*/
	/*处理第一次操作前的总数*/
	FOR(i,1,Q) {
		del[va[i]]=1;
		if(vis[va[i]]) { //当它是一个后缀最小值时,要消除它之前造成的所有影响
			bit3.add(va[i],-1);
			sum-=bit1.query(va[i])-bit2.query(a[va[i]]);
			/*同上"sum+=i-a[i]",总数减去半边,得到另一半*/
			st.erase({a[va[i]],va[i]});
		} else sum-=bit3.query((--st.lower_bound({a[va[i]],0}))->S)-bit3.query(va[i]);//当它不是后缀最小值,减去他后面比他小的后缀最小值的数量
		bit1.add(va[i],-1);
		bit2.add(a[va[i]],-1);
		for(int j:g[i]) {
			if(del[j])continue;
			bit3.add(j,1);
			vis[j]=1;
			st.insert({a[j],j});
			sum+=bit1.query(j)-bit2.query(a[j]);
		}//同理
		cout<<sum+n-i<<" ";
		/*输出*/
	}
	cout<<endl;//结尾换行好习惯 (*^▽^*)
	return 0;
}

在线题解

这是 Codeforces 上的在线做法。

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 2;
const int OFF = 1 << 18;

int n, q, a[MAXN], inv[MAXN];
long long ans;
set<int> suffix_min;

struct Fenwick {
	int fen[MAXN] = {0};

	void add(int x, int val = 1) {
		for (++x; x <= n; x += x & -x) fen[x] += val;
	}
	int count(int x) {
		int ret = 0;
		for (++x; x; x -= x & -x) ret += fen[x];
		return ret;
	}
	int count(int l, int r) {
		return count(r) - count(l - 1);
	}

} removed_values, removed_indices, marked_values, marked_indices;

struct Tournament {
	int tour[OFF] = {0};

	void update(int i, int val, int x = 0, int l = 0, int r = n - 1) {
		if (l > i || r < i) return ;
		if (l == r) {
			tour[x] = val;
			return ;
		}
		int mid = (l + r) >> 1;
		update(i, val, x * 2 + 1, l, mid);
		update(i, val, x * 2 + 2, mid + 1, r);

		tour[x] = min(tour[x * 2 + 1], tour[x * 2 + 2]);
	}

	int query(int ql, int qr, int x = 0, int l = 0, int r = n - 1) {
		if (ql <= l && r <= qr) return tour[x];
		if (ql > r || l > qr) return n;

		int mid = (l + r) >> 1;
		return min(query(ql, qr, x * 2 + 1, l, mid), query(ql, qr, x * 2 + 2, mid + 1, r));
	}

} values;

void mark(int i) {
	suffix_min.insert(i);
	marked_indices.add(i);
	marked_values.add(a[i]);

	ans += (i - removed_indices.count(i)) - (a[i] - removed_values.count(a[i]));
}

void unmark(int i) {
	ans -= (i - removed_indices.count(i)) - (a[i] - removed_values.count(a[i]));
	marked_indices.add(i, -1);
	marked_values.add(a[i], -1);

	int L = n, R = 0;
	auto it = suffix_min.find(i);
	if (it != suffix_min.end()) {
		if (++it != suffix_min.end()) R = *it;
		else R = n;
		--it;
	}
	if (it != suffix_min.begin()) L = (*--it) + 1;
	else L = 0;

	suffix_min.erase(suffix_min.find(i));

	while (L < R) {
		int j = values.query(L, R - 1);
		if (j == n) break;

		j = inv[j];
		if (a[j] < ((R == n) ? n : a[R])) mark(j);

		L = j + 1;
	}

}

int main() {

	cin >> n >> q;

	for (int i = 0; i < n; ++i) {
		cin >> a[i], --a[i];

		values.update(i, a[i]);
		inv[a[i]] = i;
	}

	int cur = n;
	for (int i = n - 1; i >= 0; --i) {
		cur = min(cur, a[i]);
		if (cur == a[i]) {
			mark(i);
		}
	}

	ans += n;
	cout << ans << " ";

	while (q--) {
		int i;
		cin >> i, --i;

		values.update(i, n);

		if (suffix_min.count(i)) unmark(i);

		ans += marked_values.count(a[i], n - 1);
		ans -= marked_indices.count(i, n - 1);

		removed_values.add(a[i]);
		removed_indices.add(i);

		--ans;
		cout << ans << " ";
	}

	return 0;
}

无脑树套树做法

考试时只会一个树套树的做法。

首先一个人下去之后回来时肯定贪心地将 $a_i$ 小的放前面。

乍一看很像 P3157 [CQOI2011] 动态逆序对，但发现有些人的贡献不能算（一个人 $i$ 的贡献为满足 $j<i$ 且 $a_j > a_i$ 的 $j$ 的数量）。

如果人 $i$ 的后面存在一个人 $k$ 使得 $a_k < a_i$，那么人 $i$ 的贡献就不能算了，因为前面所有人会在 $k$ 下去时排好序。

那么我们对每一个人记录他后面所有比他小的人的离开时间的最大值（树状数组简单维护），就可以知道每个人从什么时刻可以开始算贡献。如果把树状数组换成线段树在线维护可以做到在线，但没必要。

剩下的就是动态逆序对了，开两棵树套树。一棵维护当前存在的人数，一棵维护存在的可以算贡献的人数。

我写的树状数组套线段树，时空复杂度 $O(n\log^2n)$，可以通过（很慢就是了）。

Code:

#include<bits/stdc++.h>
using namespace std;
namespace IO{
    template<typename T>inline void read(T &x){
        x=0;int f=1;char c=getchar();
        while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
        while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x*=f;
    }
    const int BUF=1<<21;
    char buf[BUF],tp,st[32];
    int plen;
    #define flush() fwrite(buf,1,plen,stdout),plen=0
    inline void pc(char c){
        buf[plen++]=c;
        if(plen==BUF) flush();
    }
    template<typename T>inline void print(T x){
        if(!x){pc(48);return;}
        if(x<0) x=~x+1,pc('-');
        while(x) st[++tp]=48^x%10,x/=10;
        while(tp) pc(st[tp--]);
    }
}
using namespace IO;
const int N=1e5+5;
int n,q,a[N],b[N],tot,ti[N];
struct Tree{
	int ls,rs,cnt;
}t[N*360];
#define mid ((l+r)>>1)
void change(int &p,int l,int r,int x,int y){
	if(!p) p=++tot;
	t[p].cnt+=y;
	if(l<r){
		if(x<=mid) change(t[p].ls,l,mid,x,y);
		else change(t[p].rs,mid+1,r,x,y); 
	}
}
int query_(int p,int l,int r,int lt,int rt){
	if(!p) return 0;
	if(lt<=l&&r<=rt) return t[p].cnt;
	int ans=0;
	if(lt<=mid) ans=query_(t[p].ls,l,mid,lt,rt);
	if(mid<rt) ans+=query_(t[p].rs,mid+1,r,lt,rt);
	return ans;
}
struct Tree_in_Tree{
	int root[N];
	inline void add(int x,int y,int v){for(;x<=n;x+=x&-x) change(root[x],1,n,y,v);}
	inline int query(int x,int y,int l,int r){
		if(x>y||l>r) return 0;
		int ans=0;
		for(--x;x;x-=x&-x) ans-=query_(root[x],1,n,l,r);
		for(;y;y-=y&-y) ans+=query_(root[y],1,n,l,r);
		return ans;
	}
}C,T;
struct Bit_tree{
	int mx[N];
	inline void add(int x,int y){for(;x<=n&&mx[x]<y;x+=x&-x) mx[x]=y;}
	inline int query(int x){
		int ans=0;
		for(;x;x-=x&-x) ans=max(ans,mx[x]);
		return ans;
	}
}B;
vector<int> P[N];
long long ans;
bool vis[N];
int main(){
	read(n),read(q);
	for(int i=1;i<=n;++i){
		read(a[i]);
		C.add(i,a[i],1);
		ti[i]=n+1;
	}
	for(int i=1;i<=q;++i) read(b[i]),ti[b[i]]=i;
	for(int i=n;i;--i){
		int qq=B.query(a[i]);
		if(qq<=q&&qq<=ti[i]) P[qq].push_back(i);
		B.add(a[i],ti[i]);
	}
	for(int j:P[0]){
		ans+=C.query(1,j-1,a[j]+1,n);
		T.add(j,a[j],1);
		vis[j]=1;
	}
	ans+=n;
	print(ans),pc(' ');
	for(int t=1;t<=q;++t){
		C.add(b[t],a[b[t]],-1);
		ans-=T.query(b[t]+1,n,1,a[b[t]]-1);
		if(vis[b[t]]){
			ans-=C.query(1,b[t]-1,a[b[t]]+1,n);
			T.add(b[t],a[b[t]],-1);
		}
		for(int j:P[t]){
			ans+=C.query(1,j-1,a[j]+1,n);
			T.add(j,a[j],1);
			vis[j]=1;
		}
		print(--ans),pc(' ');
	}
	flush();
	return 0;
}