P9910「COCI 2023/2024 #2」dizalo 题解
Meta_Morph · · 题解
P9910「COCI 2023/2024 #2」dizalo 题解
知识点
树状数组，线段树，STL 库中的 set。
前言
这道题不错，使用了三个树状数组，一个线段树，一个 set，维护一系列基础的东西，但结合起来就变的复杂了。
各个操作不难，但思维含金量很高，适合刚熟悉树状数组和线段树的新手来做。
题意分析
先看到题目要求：求出所有人下电梯的总次数最少是多少。
题目说：“当一个人要下电梯时，所有在他前面的人也必须暂时下电梯，而每次临时下电梯的人总是以最优策略来决定返回电梯的顺序”，那么为了减小总次数，回来时肯定会让楼层大的先回来，楼层小的后回来，这样这一部分下过电梯的人在到达目标楼层时就都不会让站在他前面的人产生额外的下电梯次数，总次数也就不会再增加。
那么，哪些人会让他之前的人产生额外的下电梯次数使总次数增加呢？
之前已经说到临时下电梯的人不会让他之前的人产生额外的下电梯次数，那么会让他之前的人产生额外的下电梯次数的人就是在到达目标楼层之前都没下过电梯的人。
可以发现，这类人的目标楼层在序列中是一个后缀最小值，即在上电梯之前的序列中，在他之后 没有人的目标楼层比他小。而总次数也就是后缀最小值之前大于它的数的个数之和+总人数（每个人自己都要下一次电梯的）。
所以题目就是让我们求：第一次操作前以及每次操作之后的后缀最小值之前大于它的数的个数之和+总人数。
题解
离线题解
本代码有一条核心计算文字表达式：总次数 = 后缀最小值之前大于它的数的个数之和 + 总人数，而其中后缀最小值之前大于它的数的个数之和，就等于 大于后缀最小值的数的总个数 - 它后面大于它的数的个数 。
故我们开两个树状数组：分别维护编号为
还有不是后缀最小值的部分：删除时减去它后面比它小的后缀最小值即可。
我们再开一个 set 记后缀最小值和它的编号，用于查询时二分，和一个树状数组，记
至于什么时候什么数成为后缀最小值，开一个线段树，维护区间最大值，其中记在某数之后比它小的数的所有删除时间最大值，即成为一个所谓的后缀最小值的时间前一刻，我们可以把它离线下来进行操作。
详见代码：
#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;
}