前言:教练要求写的,于是过来补发题解。
分析
容易发现后缀如果是上升的那么就不用动,让前面的通过移动插进来就可以了,第一个答案就是 \(n\) 减去最长上升后缀的长度。
那应该怎么输出答案呢?
处理出最长的后缀后,考虑前 \(k\) 个数字。这个数字应该先移动到第 \(k + 1\) 位来,在根据大小关系插入后面的序列中,容易发现是 \(k - i\) 加上目前加进去的数中比他小的个数,再把这个数插入这个位置。
插入,查询比这个数小的个数,怎么弄呢?
平衡树万岁!!!看到数据范围只到\(10^5\),写一颗值域线段树(写完发现好像树状数组简单的多)就行了。
ACcode
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long ull;
const int N = 1e5 + 5, INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int n;
int a[N];
vector<int> v;
struct segment_tree
{
int l, r, val;
#define l(x) tr[x].l
#define r(x) tr[x].r
#define val(x) tr[x].val
}tr[N << 2];
void pushup(int x)
{
val(x) = val(x << 1) + val(x << 1 | 1);
}
void build(int l, int r, int x)
{
l(x) = l, r(x) = r;
if(l == r)
{
val(x) = 0;
return;
}
int mid = l + r >> 1;
build(l, mid, x << 1);
build(mid + 1, r, x << 1 | 1);
pushup(x);
}
void update(int x, int id, int v)
{
if(l(x) == id && r(x) == id)
{
val(x) += v;
return;
}
int mid = l(x) + r(x) >> 1;
if(id <= mid) update(x << 1, id, v);
else update(x << 1 | 1, id, v);
pushup(x);
}
int query(int l, int r, int x)
{
if(l <= l(x) && r(x) <= r) return val(x);
int mid = l(x) + r(x) >> 1, res = 0;
if(l <= mid) res += query(l, r, x << 1);
if(r > mid) res += query(l, r, x << 1 | 1);
return res;
}
int main() //主函数
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 1;i <= n; i++) cin >> a[i];
build(1, n, 1);
int k = n;
while(a[k - 1] < a[k]) k --;
k --;
for(int i = k + 1;i <= n;i ++) update(1, a[i], 1);
for(int i = 1;i <= k;i ++)
{
v.push_back(k - i + query(1, a[i], 1));
update(1, a[i], 1);
}
cout << k << '\n';
for(int i = 0;i < k;i ++) cout << v[i] << ' ';
return 0;
}
标签:P5200,Sorting,val,int,题解,tr,long,define
From: https://www.cnblogs.com/Svemit/p/17216009.html