T1 怎么又是先增后减(why)描述青蛙又给了周欣一个长为 的正整数序列 周欣可以进行若干次操作每次可以选择一个位置 满足 将 的值和 的值进行交换。设经过这若干次操作后的序列为 那么需要存在一个整数 满足区间 构成的子序列 是一个非严格单调递增的序列即相邻两项允许相等但是左边元素不能大于右边元素。区间 构成的子序列 是一个非严格单调递减的序列即相邻两项允许相等但是左边元素不能小于右边元素。周欣想知道至少需要对序列进行多少次上述操作后这个要求才能得以满足他把这个问题交给了你来解决。输入第一行一个整数 表示序列长度。第二行 个整数表示 。输出输出一个整数表示答案即最少的操作次数。样例共 组。数据范围对于 的数据满足 。对于 的数据满足 。对于 的数据满足 。题解我们令 为当前序列中最小的数字。以样例3 1 4 1 5 9 2为例子假设为第一个 。我们知道 必须被移动到最左边或最右边。样例中往左移动需要 步但往右移动需要 步不是 步因为相同的 不需要交换。于是我们得到一个解题思路对于每个数计算出左边严格比他大的有多少个记为 再计算出右边严格比他大的有多少个记为 。然后将 累加 即可。暴力统计的复杂度为 可以得到 的分数。使用树状数组优化复杂度为 可以得到 的分数。#includebits/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 (x1) (x3) (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 国中从当前他在的城市旅游到另一个城市从编号为 的城市移动到编号为 的城市会让他花费 元钱。如果一次美食节举办时青蛙不在美食节举办的范围内此时我们假设青蛙当前所在城市到美食节举办范围内城市的最短距离为 则青蛙会花费 元请人帮他从最近的美食节举办的城市买美食。为了让青蛙省钱你需要求出所有的美食节举办结束后青蛙最少的花费。输入第一行两个正整数 。接下来 行每行两个正整数 。输出输出一个整数表示答案。样例共 组。数据范围对于 的数据满足 。对于 的数据满足 。对于 的数据满足 。题解考虑令 表示第 个活动后在 的最小疲劳值。显然的对于每个 先赋初始值为 部分然后把不在范围内的 加上距离作为代价。如果要移动则使用 更新 和 。然后我们对于每个 把 看成关于 的函数。可以证明这个函数最多由 个部分组成斜率分别为 函数下凸。于是我们只需要维护最下面的一段即可。令 代表这段区间的范围对每个节日动态更新即可复杂度 。证明考虑使用归纳法。当 时满足要求。当 增大时“把不在范围内的 加上距离作为代价”部分会使函数加上一个差分为 的函数差分变为 。但第二部分计算移动时会让函数的差分绝对值不超过 差分又变成 。证毕。代码如下#includebits/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; }