题目描述
给定一个包含 \(n\) 个整数的数组 \(x_1, x_2, \dots, x_n\)。你需要回答 \(q\) 个询问 \((a, b)\)。每次操作中，你可以执行以下两种操作之一：
- 将前 \(a\) 个数按非递减序排序，或
- 将后 \(b\) 个数按非递减序排序。
若要使得整个数组按非递减序列排列，至少需要多少次操作？在每个询问中，数组均从初始值 \(x_1, x_2, \dots, x_n\) 开始。
输入格式
第一行包含两个整数 \(n\) 和 \(q\)，分别表示数组的长度和询问的数量。
第二行包含 \(n\) 个整数 \(x_1, x_2, \dots, x_n\)，表示数组的内容。
接下来的 \(q\) 行描述各询问。每行包含两个整数 \(a\) 和 \(b\)。
输出格式
输出 \(q\) 行，每行是对应询问的答案。如果无法将数组排序，则输出 \(-1\)。
子任务
| 子任务 | 约束条件 | 分值 |
|---|---|---|
| 1 | \(n, q \leq 10\) 且所有询问满足 \(a + b \leq n\) | 6 |
| 2 | \(n, q \leq 10\) | 5 |
| 3 | 所有询问满足 \(a + b \leq n\) | 7 |
| 4 | \(1 \leq x_i \leq 2\) | 14 |
| 5 | \(n, q \leq 5000\) 且数组是 \(1, 2, \dots, n\) 的一个排列 | 23 |
| 6 | \(n, q \leq 5000\) | 12 |
| 7 | 无额外限制 | 33 |
输入输出样例 #1
输入 #1
6 3
3 1 4 1 5 9
4 1
3 3
2 5
输出 #1
1
-1
2
说明/提示
解释
- 在第一个询问中，可以通过对前 4 个数排序，在一次操作内将数组排序。
- 在第二个询问中，无法利用给定的操作将数组排序。
- 在第三个询问中，可以通过两次操作将数组排序：首先对前 2 个数排序，然后对后 5 个数排序。
数据范围
- \(1 \leq n, q \leq 2 \cdot 10^5\)
- \(1 \leq x_i \leq 10^9\)
- 所有询问中 \(1 \leq a, b \leq n\)
题解
超级【】的题，分类讨论。
下文定义 \(S\) 为将前
\(x\) 个数按非递减序排序，\(T\) 为将后 \(
y\) 个数按非递减序排序。
- \(x+y \le n\)：
- \(0\) 次操作：数组初始已有序。
- 如果 \(x+y \le n\)，说明前缀 \(x\) 和后缀 \(y\) 完全没有重叠，中间还隔着 \(n-(x+y)\) 个元素。这意味着元素永远无法跨越区域移动。
- 最多只需 \(1\) 次或 \(2\) 次操作就能排好序。
- 如果 \(1\) 次或 \(2\) 次操作后仍未有序，则永远无法有序，返回 \(-1\)。
- \(x+y > n\)：存在长度为 \(z = x+y-n\) 的重叠区域。这个重叠区域是元素从左边运送到右边，或从右边运送到左边的唯一通道。每一次完整的 \(S\) 和 \(T\) 的循环，最多能将 \(z\) 个元素通过重叠区运送过去。
对每个阈值 \(k \in [1, n-1]\) 进行分析。将排序后数组的前 \(k\) 小的元素视为 \(0\)，其余视为 \(1\)。我们的目标是把所有的 \(0\) 移到前 \(k\) 个位置，所有的 \(1\) 移到后 \(n-k\) 个位置。
定义两个错位元素数量：
- \(c_L(k)\)：在左侧区 \([1 \dots n-y]\) 中，不该在那里的 \(1\) 的数量。
- \(c_R(k)\)：在右侧区 \([x+1 \dots n]\) 中，不该在那里的 \(0\) 的数量。
每次操作能运送 \(z\) 个元素，因此消除这些错位元素所需的基础操作趟数为：
- \(m_L(k) = \lceil c_L(k) / z \rceil\)
- \(m_R(k) = \lceil c_R(k) / z \rceil\)
对于特定的阈值 \(k\)，根据最后一次操作是 \(S\) 还是 \(T\)，以及 \(k\) 所处的区间，可以推导出所需的确切操作步数。
为了让数组完全有序，所有阈值 \(k\) 限制都必须被同时满足。对于任何一个 \(k\)，为了满足左右两端的容量要求，操作次数必须是 \(\max(f(k), g(k))\)。
因此，全局所需的最少操作数是：
等价于：
因为 \(f(k)\) 是随着 \(k\) 单调递增的（受 \(getR\) 也就是右侧的 \(0\) 数量限制），它的最大值直接在区间右端点 \(k = x\) 处取到；同理，\(g(k)\) 是单调递减的（受 \(getL\) 即左侧的 \(1\) 数量限制），它的最大值直接在区间左端点 \(k = n-y\) 处取到。
结论：全域的瓶颈就是独立的四个极值点。
我们可以直接使用 \(O(1)\) 公式。
数据结构优化：
\(c_L(k)\) 和 \(c_R(k)\) 需计数某个区间内，排名 \(\le k\) 的元素个数。这可以通过建立的主席树来实现在 \(O(\log n)\) 时间内查询。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,q,x,y,z;
int a[N];
int st[2][N][20];
int lg[N];
vector<int> g;
inline int qry(int op,int l,int r){if(op==0) return max(st[op][l][lg[r-l+1]],st[op][r-(1<<(lg[r-l+1]))+1][lg[r-l+1]]);return min(st[op][l][lg[r-l+1]],st[op][r-(1<<(lg[r-l+1]))+1][lg[r-l+1]]);
}
inline bool check(int l,int r){int u=upper_bound(g.begin(),g.end(),l)-g.begin();assert(g[u-1]<=l);return g[u]>r;
}
struct Node{int cnt;int l,r;
}tr[N*40];
int rt[N];
int tot=0;
int insert(int fa,int l,int r,int v){int p=++tot;tr[p]=tr[fa];tr[p].cnt++;if(l==r) return p;int mid=l+r>>1;if(v<=mid) tr[p].l=insert(tr[p].l,l,mid,v);else tr[p].r=insert(tr[p].r,mid+1,r,v);return p;
}
int query(int p,int l,int r,int k){if(!p||k<l) return 0;if(r<=k) return tr[p].cnt;int mid=l+r>>1;return query(tr[p].l,l,mid,k)+query(tr[p].r,mid+1,r,k);
}
inline int getL(int k){if(n==y) return 0;return n-y-query(rt[n-y],1,n,k);
}
inline int getR(int k){if(n==x) return 0;return k-query(rt[x],1,n,k);
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>q;for(int i=1;i<=n;i++)cin>>a[i];int fl=1,fr=n;while(fl<n&&a[fl+1]>=a[fl]) fl++;while(fr>1&&a[fr-1]<=a[fr]) fr--;g.push_back(1);for(int i=2;i<=n;i++)if(a[i]<a[i-1])g.push_back(i);g.push_back(n+1);if(fl==n&&fr==1){while(q--)cout<<0<<'\n';return 0;}for(int i=1;i<=n;i++)st[0][i][0]=st[1][i][0]=a[i];for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;for(int j=1;j<=lg[n];j++)for(int i=1;i<=n-(1<<j)+1;i++){st[0][i][j]=max(st[0][i][j-1],st[0][i+(1<<(j-1))][j-1]);st[1][i][j]=min(st[1][i][j-1],st[1][i+(1<<(j-1))][j-1]);}vector<pair<int,int> > _a;vector<int> p(n+1);for(int i=1;i<=n;i++)_a.push_back(make_pair(a[i],i));sort(_a.begin(),_a.end());for(int i=1;i<=n;i++)p[_a[i-1].second]=i;for(int i=1;i<=n;i++)rt[i]=insert(rt[i-1],1,n,p[i]);while(q--){cin>>x>>y;if(x+y<=n){if(x+y==n){if(qry(0,1,x)<=qry(1,n-y+1,n)){int res=0;if(x>fl) res++;if(n-y+1<fr) res++;cout<<res<<'\n';continue;}cout<<-1<<'\n';continue;}if(check(x+1,n-y)&&qry(0,1,x)<=qry(1,x+1,n-y)&&qry(0,x+1,n-y)<=qry(1,n-y+1,n)){int res=0;if(x>fl) res++;if(n-y+1<fr) res++;cout<<res<<'\n';continue;}cout<<-1<<'\n';continue;}if(x==n||(check(x+1,n)&&qry(0,1,x)<=qry(1,x+1,n))){cout<<1<<'\n';continue;}if(y==n||(check(1,n-y)&&qry(0,1,n-y)<=qry(1,n-y+1,n))){cout<<1<<'\n';continue;}z=x+y-n;int L_req=(getL(n-y)+z-1)/z;int R_req=(getR(x)+z-1)/z;int L2R=(getL(x)+z-1)/z;int R2L=(getR(n-y)+z-1)/z;int ans1=max({2ll,2*L_req-1,2*R2L+1,2*R_req,2*L2R});int ans2=max({2ll,2*L_req,2*R2L,2*R_req-1,2*L2R+1});if(getL(x)==0||getR(n-y)==0){ans1=min(ans1,2ll);ans2=min(ans2,2ll);}cout<<min(ans1,ans2)<<'\n';}return 0;
}