某不知名校赛热身题
题目描述
给定长度为 $N$ 的序列 $A = (A_1,A_2,\cdots,A_N)$,再给定整数 $M$ 和 $K$
对于每个 $i = 1,\cdots,N - M + 1$,请求出:
对于 $A_i,A_{i + 1},\cdots,A_{i + M -1}$($1e^9$级别) 从小到大进行排序,前面 $K$ 个元素的和
输入
6 4 3
3 1 4 1 5 9
输出
5 6 10
这个题目应该用 平衡树 来维护 动态区间
1. 初始时刻
暴力得到 $K$ 个数的和 res
2. 移动区间 $[i - 1,i + m - 2]$ 为 $[i,i + m - 1]$
(1).如果上一个元素($a[i - 1]$)的最后排名仍然 $\leq K$,说明这个数删掉后,将引起 res 的变化,我们把它从 res 减去
此时将 $a[i]$ 从平衡树删去,添加 $a[i + m - 1]$
(2).如果新加元素($a[i + m - 1$)的最前排名满足 $\leq K$,说明这个数添进来后,有望更新 res ,我们先把它加入 res
(3).如果当且 res 里的组成元素个数($p$)多于 $K$,使用平衡树找到第 $p$ 小值,将其删去
(4).如果当且 res 里的组成元素个数($p$)小于 $K$,使用平衡树找到第 $p + 1$ 小值,将其添加
因为不知道如何使用 mulitiset 找到排名为 $K$ 的元素以及输出某元素的排名,我选择了
树状数组模拟平衡树,然后,如你所料,调了半天😭
树状数组模拟平衡树
#include <bits/stdc++.h>
#define fastio() ios::sync_with_stdio(0),\
cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define endl '\n'
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef tuple<int,int,int> TRI;
typedef unsigned long long ULL;
constexpr int N = 200010;
int tr[N];
int n,m,k,a[N];
vector<int> nums;
int shift(int x)
{
return lower_bound(nums.begin(),nums.end(),x) - nums.begin() + 1;
}
void insert(int u,int x)
{
for(int i = u;i <= n;i += lowbit(i) ) tr[i] += x;
}
int sum(int x)
{
int res = 0;
for(int i = x;i;i -= lowbit(i)) res += tr[i];
return res;
}
int rk(int x)// 得到离散化后的值的排名
{
return sum(x - 1) + 1;
}
int sz(int x)
{
return sum(x) - sum(x - 1);
}
int find(int x)// 根据排名找到其对应的数字
{
int l = 1,r = n;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(rk(mid) <= x) l = mid;
else r = mid - 1;
}
return nums[l - 1];
}
int main()
{
fastio();
cin >> n >> m >> k;
for(int i = 0;i < n;i ++ )
cin >> a[i],nums.push_back(a[i]);
sort(nums.begin(),nums.end());
vector<int> b;
for(int i = 0;i < m;i ++ )
insert(shift(a[i]),1),b.push_back(a[i]);
sort(b.begin(),b.end());
LL res = 0;int p = 0;
for(int i = 0;i < k;i ++ )
res += b[i],p ++;
cout << res << " ";
for(int i = 1;i < n - m + 1;i ++ )
{
if(rk(shift(a[i - 1]) + 1) - 1 <= k)
res -= a[i - 1],p --;
insert(shift(a[i - 1]),-1);
insert(shift(a[i + m - 1]),1);
if(rk(shift(a[i + m - 1])) <= k)
res += a[i + m - 1],p ++;
while(p > k) res -= find(p),p --;
while(p < k) res += find(p + 1),p ++;
cout << res << " ";
}
return 0;
}
vector骗分(T了一个点)
#include <bits/stdc++.h>
#define fastio() ios::sync_with_stdio(0),\
cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define endl '\n'
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef tuple<int,int,int> TRI;
typedef unsigned long long ULL;
constexpr int N = 200010;
int n,m,k;
int a[N],b[N];
struct BST
{
vector<int> S;
inline void insert(int x)
{
S.emplace(lower_bound(S.begin(),S.end(),x),x);
}
inline void erase(int x)
{
S.erase(lower_bound(S.begin(),S.end(),x));
}
inline int rk(int x)
{
return lower_bound(S.begin(),S.end(),x) - S.begin() + 1;
}
inline int val(int x)
{
return S[x - 1];
}
}tr;
int main()
{
fastio();
cin >> n >> m >> k;
for(int i = 0;i < n;i ++ ) cin >> a[i];
for(int i = 0;i < m;i ++ ) b[i] = a[i],tr.insert(b[i]);
sort(b,b + m);
LL res = 0;int p = 0;
for(int i = 0;i < k;i ++ ) res += b[i],p ++ ;
cout << res << " ";
for(int i = 1;i < n - m + 1;i ++ )
{
if(tr.rk(a[i - 1] + 1) - 1 <= k)
res -= a[i - 1],p --;
tr.erase(a[i - 1]);
tr.insert(a[i + m - 1]);
if(tr.rk(a[i + m - 1]) <= k)
res += a[i + m - 1],p ++;
while(p > k) res -= tr.val(p),p --;
while(p < k) res += tr.val(p + 1),p ++;
cout << res << " ";
}
return 0;
}
hxd加油!
~~~~🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏~~~~本来我也想上平衡树的,然后吕爷告诉了我一个操作:
因为set是不支持随机访问的,所以我们完全可以在第k处将set分成两部分,然后分类讨论模拟中间部分的插入删除操作即可
太有道理了
~~,这个思路应该好调一点