考场上顺序开题。
\(\mathrm{A.}\mathbb{Game}\)：数据结构
\(\mathrm{B.}\mathbb{Time}\)：数据结构
\(\mathrm{C.}\mathbb{Cover}\)：树形 \(\mathrm{dp}\)
首看 \(\mathrm{A}\)，发现很容易求出其中一种情况，于是又绕进去了，不过在大约一个小时的时候发现了亿些问题，于是便转 \(\mathrm{B}\) 了。（事实上按照这个思路是能打一部分分的，但是最后也没调出来）
看 \(\mathrm{B}\) 时，也有一定的思路，由于以前做过一道类似的题，便考虑最大值，期间也考虑过最小值，但当时并不知道如何贪心，于是便叉掉了。
\(\mathrm{C}\) 没看几眼，只看出来可以建成树的形式，没有细想。
最后的一个小时主要还是卡在 \(\mathrm{A}\) 上了，数据结构还是应用的不够熟练，应该多做些题，大胆尝试使用数据结构（
估分：\([0,100]+0+0=[0,100]\)
实际：\(10+0+0=10\)
还是说正解吧（
\(\mathrm{A.}\mathbb{Game}\)
正解
\(\mathrm{B.}\mathbb{Time}\)
考场上考虑答案为最大值移动后所分成的两个区间以及最大值移动的操作数之和，以为最大值移动的次数越少越好，很明显是假的（
正解
考虑最小值，只能在序列的最左边或是最右边，每次贪心的选择更优（操作数更少）的那一边，将操作数累计到答案里，再去掉这个点，解决子问题。
用 \(\mathrm{deque}\) 以值为下标，把位置存进去，按照值域从小到大扫一遍。
需要单独考虑有值相同的情况，每次取出队首与队尾，比较它们谁更优，然后再将其弹出。
由于需要查询删去数之后的排名，因此用一个线段树（或树状数组），来支持单点修改和区间查询的操作。
code
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
int l,r,mx;
deque<int> q[N];
long long ans;
struct Tree
{
int l,r;
int sum;
}tree[N*4];
void pushup(int p)
{
tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
return;
}
void build(int p,int l,int r)
{
tree[p].l=l;
tree[p].r=r;
if(l==r)
{
tree[p].sum=1;
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
pushup(p);
return;
}
int ask(int p,int l,int r)
{
if(tree[p].l>=l&&tree[p].r<=r) return tree[p].sum;
int mid=(tree[p].l+tree[p].r)/2;
int sum=0;
if(l<=mid) sum+=ask(p*2,l,r);
if(r>=mid+1) sum+=ask(p*2+1,l,r);
return sum;
}
void change(int p,int l,int r,int d)
{
if(tree[p].l>=l&&tree[p].r<=r)
{
tree[p].sum+=d;
return;
}
int mid=(tree[p].l+tree[p].r)/2;
if(l<=mid) change(p*2,l,r,d);
if(r>=mid+1) change(p*2+1,l,r,d);
pushup(p);
return;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
q[x].push_back(i);
mx=max(mx,x);
}
build(1,1,n);
for(int i=1;i<=mx;i++)
{
while(q[i].size())
{
int l=q[i].front(),r=q[i].back();
int a=ask(1,1,l-1),b=ask(1,r+1,n);
if(a<b)
{
ans+=a;
change(1,l,l,-1);
q[i].pop_front();
}
else
{
ans+=b;
change(1,r,r,-1);
q[i].pop_back();
}
}
}
printf("%d\n",ans);
return 0;
}
\(\mathrm{C.}\mathbb{Cover}\)
正解