$des$
有 $n$ 个物品，第 $i$ 个物品的价格是 $v_i$ ，有两个人，每个人都喜欢 $n$ 个物品中的一些物品。
要求选出正好 $m$ 个物品，满足选出的物品中至少有 $k$ 个物品被第一个人喜欢，$k$ 个物品被第二个人喜欢。并求出最小的价格和。
$sol$
将所有物品分成 $4$ 类
1. $a \cap b$
2. $a – a \cap b$
3. $b – a \cap b$
4. $全集 – a \cup b$
枚举 $1$ 选了多少个
此时 $2, 3$ 选多少个是固定的了
这样的话只需维护剩余元素的前 $x$ 小值之和
对顶堆维护
大根堆维护前 $x$ 小
查询时就是大根堆的权值之和
删除元素标记
维护剩余元素的前 $x$ 小值之和也可以用权值线段树
#include <bits/stdc++.h>using namespace std;
const int N = 2e5 + ;#define gc getchar()
inline int read() {
int x = ; char c = gc;
while(c < '' || c > '') c = gc;
while(c >= '' && c <= '') x = x * + c - '', c = gc;
return x;
}#define Rep(i, a, b) for(int i = a; i <= b; i ++)
#define LL long long
#define Fin(a) freopen(a, "r", stdin)
#define Fout(a) freopen(a, "w", stdout)
#define E return
#define End cout << "\n"map <int, int> Map;
int W[N];
int n, m, k, a, b;
bool usea[N], useb[N];priority_queue <int, vector <int>, less <int> > Big;
priority_queue <int, vector <int>, greater <int> > Small;int szab[N], jsab;
int sza[N], jsa;
int szb[N], jsb;
int sznot[N], jsnot;
LL sum1[N], sum2[N], sum3[N];int Size;
LL Sum;void Update() {
while(Big.size() && Map[Big.top()]) Map[Big.top()] --, Big.pop();
while(Small.size() && Map[Small.top()]) Map[Small.top()] --, Small.pop();
}int Now_size;
int ato, bto, abto;void Add(int x) {
Update();
while(Size < Now_size && Small.size()) {
int topsmall = Small.top(); Small.pop();
Size ++, Sum += topsmall, Big.push(topsmall);
}
if(Size == Now_size) {
if(Big.size() == ) Small.push(x);
else if(x < Big.top()) {
int topbig = Big.top();
Sum += (x - topbig);
Big.pop(); Big.push(x);
Small.push(topbig);
}
return ;
}
if(Size < Now_size) {
Big.push(x);
Size ++; Sum += x;
return ;
}
Update();
int topbig = Big.top();
if(x < topbig) {
Sum += (x - topbig);
Big.pop(); Big.push(x);
Small.push(topbig);
} else {
Small.push(x);
}
}bool Judge() {
if(m < k) return ;
if(jsab + jsa < k || jsab + jsb < k) return ;
if(k * - jsab > m) return ;
return ;
}void RE() {
cout << "error" << "\n";
}void Bef_work() {
Rep(i, , n) {
if(usea[i] && useb[i]) szab[++ jsab] = W[i];
else if(usea[i]) sza[++ jsa] = W[i];
else if(useb[i]) szb[++ jsb] = W[i];
else sznot[++ jsnot] = W[i];
} sort(szab + , szab + jsab + );
sort(sza + , sza + jsa + );
sort(szb + , szb + jsb + );
sort(sznot + , sznot + jsnot + ); Rep(i, , jsab) sum1[i] = sum1[i - ] + szab[i];
Rep(i, , jsa) sum2[i] = sum2[i - ] + sza[i];
Rep(i, , jsb) sum3[i] = sum3[i - ] + szb[i]; if(Judge()) {puts("-1"); exit() ;} Rep(i, , jsab) Add(szab[i]);
Rep(i, k + , jsa) Add(sza[i]);
Rep(i, k + , jsb) Add(szb[i]);
Rep(i, , jsnot) Add(sznot[i]); ato = min(k, jsa);
bto = min(k, jsb);
abto = ;}bool Judge2(int x) {
if(k - x > jsa || k - x > jsb || k * - x > m) return ;
return ;
}void Del(int x) {
Update();
Map[x] ++;
int topbig = Big.top();
if(x <= topbig) {
Size --, Sum -= x;
}
Update();
}LL Ask(int x) {
Update();
while(Size > x && Big.size()) {
int topbig = Big.top();
Size --, Sum -= topbig;
Big.pop();
Small.push(topbig);
Update();
}
while(Size < x && Small.size()) {
int topsmall = Small.top();
Size ++, Sum += topsmall;
Small.pop();
Big.push(topsmall);
Update();
}
return Sum;
}LL Calc(int x) {
LL ret = ;
while(abto <= x && abto) {
Del(szab[abto]);
abto ++;
}
ret += sum1[abto - ];
while(ato > k - x && ato) {
Add(sza[ato]);
ato --;
}
ret += sum2[ato];
while(bto > k - x && bto) {
Add(szb[bto]);
bto --;
}
ret += sum3[bto];
ret += Ask(m - k * + x);
return ret;
}int main() {
n = read(), m = read(), k = read();
Rep(i, , n) W[i] = read();
a = read(); Rep(i, , a) W[] = read(), usea[W[]] = ;
b = read(); Rep(i, , b) W[] = read(), useb[W[]] = ; Now_size = m;
Bef_work(); abto = ; LL Answer = 1e18;
Rep(i, , jsab) {
if(!Judge2(i)) continue;
Now_size = m - k * + i;
Answer = min(Answer, Calc(i));
}
cout << (Answer == 1e18 ? - : Answer);
return ;
}
对顶堆
orz zbq
/*
枚举两个人都喜欢的物品选择了几个， 那么我们就知道了只有一个人喜欢的物品选择了几个
这两种显然贪心要最小的
然后剩下的都可以随便选 所以扔到数据结构里找前k小的和
枚举移动一位时， 线段树里的数据改动量是O1的即可 */#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<iostream>
#define ll long long
#define M 300010
#include<map>
#define tmp tot
using namespace std;
int read() {
int nm = , f = ;
char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') f = -;
for(; isdigit(c); c = getchar()) nm = nm * + c - '';
return nm * f;
}ll n, m, k;
int ver[M];
bool vis1[M], vis2[M];
ll st1[M], tp1, st2[M], tp2,st3[M], tp3,st4[M], tp4;
ll ans = 1000000000000000010ll;
ll allans = ;
ll note[M], biao[M];
map<ll, ll> mp;
ll notev[M * ];ll t[M * ], sz[M * ];
#define lson l, mid, now << 1
#define rson mid + 1, r, now << 1 | 1void insert(int l, int r, int now, int x) {
if(l > x || r < x) return;
if(l == r) {
t[now] += biao[x];
sz[now]++;
notev[now] = biao[x];
return;
}
int mid = (l + r) >> ;
insert(lson, x), insert(rson, x);
t[now] = t[now << ] + t[now << | ];
sz[now] = sz[now << ] + sz[now << | ];
}void del(int l, int r, int now, int x) {
if(l > x || r < x) return;
if(l == r) {
t[now] -= biao[x];
sz[now]--;
return;
}
int mid = (l + r) >> ;
del(lson, x), del(rson, x);
t[now] = t[now << ] + t[now << | ];
sz[now] = sz[now << ] + sz[now << | ];
}ll query(int k) { int now = ;
ll tmp = ;
while(k) {
if(sz[now] == ) break;
if(sz[now] && !sz[now << ] && !sz[now << | ])tmp += notev[now] * k, k = /*-= sz[now]*/, now = now << | ;
else if(sz[now << ] <= k) tmp += t[now << ], k-= sz[now << ], now = now << | ;
else now = now << ;
}
return tmp;
}int main() {
n = read(), m = read(), k = read();
for(int i = ; i <= n; i++) {
note[i] = ver[i] = read();
}
int q = read();
for(int i = ; i <= q; i++) {
int op = read();
vis1[op] = true;
}
q = read();
for(int i = ; i <= q; i++) {
int op = read();
vis2[op] = true;
}
for(int i = ; i <= n; i++) {
if(vis1[i] && vis2[i]) st1[++tp1] = ver[i];
else if(vis1[i]) st2[++tp2] = ver[i];
else if(vis2[i]) st3[++tp3] = ver[i];
else st4[++tp4] = ver[i];
}
sort(st1 + , st1 + tp1 + );
sort(st2 + , st2 + tp2 + );
sort(st3 + , st3 + tp3 + );
sort(st4 + , st4 + tp4 + );
sort(note + , note + n + );
note[] = -;
int tot = ;
for(int i = ; i <= n; i++) {
if(note[i] == note[i - ]) continue;
tot++;
biao[tot] = note[i];
mp[note[i]] = tot;
}
/* 前面是数据预处理， 离散化部分
*/
int rx = min(k, tp1);
int lx = max(0ll, max(k - tp2, k - tp3));
/*
确定m上下界， 不能弄出不够的情况
*/
if(min(tp2, tp3) + tp1 < k || rx < lx) {
printf("-1");
return ;
} for(int i = ; i <= tp4; i++) insert(, tmp, , mp[st4[i]]);
for(int i = lx + ; i <= tp1; i++) insert(, tmp, , mp[st1[i]]);
for(int i = k - lx + ; i <= tp2; i++) insert(, tmp, , mp[st2[i]]);
for(int i = k - lx + ; i <= tp3; i++) insert(, tmp, , mp[st3[i]]);
/*
将所有随便选的扔到线段树里
*/
for(int i = ; i <= lx; i++) allans += st1[i];
for(int i = ; i <= k - lx; i++) allans += st2[i] + st3[i];
/*
统计当前答案
*/
int tppp = k - lx; // 这个变量是一个人喜欢的选了几个
int zz = m - * (k - lx) - lx;
if(zz >= ) ans = min(ans, allans + query(zz));//当前可行就统计答案
for(int i = lx + ; i <= rx; i++) {
// i是两个人喜欢的
del(, tmp, , mp[st1[i]]); ;// 强制要选 所以从线段树中删除
allans += st1[i];
if(tppp == ) break;//不合法
insert(, tmp, , mp[st2[tppp]]), allans -= st2[tppp];
insert(, tmp, , mp[st3[tppp]]), allans -= st3[tppp];
/* 将已经可以随便选的 一个人喜欢的加入线段树
*/
tppp--;
int op = m - * tppp - i; //从线段树中要拿多少
if(op < ) continue;
if(op > sz[]) continue;
ans = min(ans, allans + query(op));
}
if(ans == 1000000000000000010ll) ans = -;
cout << ans << "\n";
return ;
}
权值线段树
