T1 怎么又是先增后减(why)

描述

青蛙又给了周欣一个长为 的正整数序列 ，周欣可以进行若干次操作，每次可以选择一个位置 ，满足 ，将 的值和 的值进行交换。

设经过这若干次操作后的序列为 ，那么需要存在一个整数 ，满足：

• 区间 构成的子序列 是一个非严格单调递增的序列，即相邻两项允许相等，但是左边元素不能大于右边元素。

• 区间 构成的子序列 是一个非严格单调递减的序列，即相邻两项允许相等，但是左边元素不能小于右边元素。

周欣想知道至少需要对序列进行多少次上述操作后，这个要求才能得以满足，他把这个问题交给了你来解决。

输入

第一行一个整数 ，表示序列长度。

第二行 个整数表示 。

输出

输出一个整数，表示答案，即最少的操作次数。

样例

共 组。

数据范围

对于 的数据，满足 。

对于 的数据，满足 。

对于 的数据，满足 。

题解

我们令 为当前序列中最小的数字。

以样例3 1 4 1 5 9 2为例子，（假设为第一个 ）。

我们知道， 必须被移动到最左边或最右边。样例中，往左移动需要 步，但往右移动需要 步（不是 步，因为相同的 不需要交换）。

于是我们得到一个解题思路：

对于每个数，计算出左边严格比他大的有多少个，记为 ；再计算出右边严格比他大的有多少个，记为 。然后将 累加 即可。

暴力统计的复杂度为 ，可以得到 的分数。

使用树状数组优化，复杂度为 ，可以得到 的分数。

#include<bits/stdc++.h> using namespace std; inline int read(){ int x = 0, f = 1; char ch = getchar(); while(!isdigit(ch)){ if(ch == '-') f = -1; ch = getchar(); } while(isdigit(ch)){ x = (x<<1) + (x<<3) + (ch^48); ch = getchar(); } return x * f; } const int N = 1e5 + 10; int n, a[N], t[N], LEFT[N], RIGHT[N]; inline int lowbit(int x){ return x & (-x); } inline void add(int x){ while(x <= N){ t[x]++; x += lowbit(x); } return; } inline int query(int x){ int ans = 0; while(x){ ans += t[x]; x -= lowbit(x); } return ans; } signed main(){ n = read(); for(int i = 1; i <= n; i++) a[i] = read(); for(int i = 1; i <= n; i++){ add(a[i]); LEFT[i] = query(N) - query(a[i]); } memset(t, 0, sizeof(t)); for(int i = n; i >= 1; i--){ add(a[i]); RIGHT[i] = query(N) - query(a[i]); } long long ans = 0; for(int i = 1; i <= n; i++) ans += min(LEFT[i], RIGHT[i]); cout << ans << endl; return 0; }

T2 美食节(festival)

描述

在 OI 国，所有城市排成了一个序列，从左往右分布是编号为 的城市。

青蛙今天在 OI 国旅游，一开始他在编号为 的城市。

OI 国准备举办 次美食节，第 次的美食节在编号区间 内的城市上举办。在每次美食节开始之前，青蛙可以在 OI 国中从当前他在的城市旅游到另一个城市，从编号为 的城市移动到编号为 的城市会让他花费 元钱。

如果一次美食节举办时，青蛙不在美食节举办的范围内，此时我们假设青蛙当前所在城市到美食节举办范围内城市的最短距离为 ，则青蛙会花费 元，请人帮他从最近的美食节举办的城市买美食。

为了让青蛙省钱，你需要求出所有的美食节举办结束后，青蛙最少的花费。

输入

第一行两个正整数 。

接下来 行，每行两个正整数 。

输出

输出一个整数，表示答案。

样例

共 组。

数据范围

对于 的数据，满足 。

对于 的数据，满足 。

对于 的数据，满足 。

题解

考虑令 表示第 个活动后在 的最小疲劳值。

显然的对于每个 ，先赋初始值为 部分，然后把不在范围内的 加上距离作为代价。如果要移动，则使用 更新 和 。

然后，我们对于每个 ，把 看成关于 的函数。可以证明这个函数最多由 个部分组成，斜率分别为 ，函数下凸。

于是我们只需要维护最下面的一段即可。令 代表这段区间的范围，对每个节日动态更新即可，复杂度 。

证明

考虑使用归纳法。

当 时，，满足要求。

当 增大时，“把不在范围内的 加上距离作为代价”部分会使函数加上一个差分为 的函数，差分变为 。

但第二部分计算移动时，会让函数的差分绝对值不超过 ，差分又变成 。

证毕。

代码如下：

#include<bits/stdc++.h> #define int long long using namespace std; signed main(){ int n, x; cin >> n >> x; int l = x, r = x; //维护下凸函数最下方的区间范围 int ans = 0; for(int i = 1; i <= n; i++){ int li, ri; cin >> li >> ri; if(li > r){ ans += li - r; l = r, r = li; }else{ if(ri < l){ ans += l - ri; r = l, l = ri; }else{ l = max(l, li); r = min(r, ri); } } } cout << ans << endl; return 0; }