NOIP2023模拟6联测27 C. 点餐

NOIP2023模拟6联测27 C. 点餐

题目大意

有 $n$ 种菜品，每样菜品有 $a_i,b_i$

假设有某位顾客点了 $k$ 样菜品，那么价格为 ${\sum }_{i=1}^k{a}_{p_i}+{\max }_{i=1}^k{b}_{p_i}$

询问所有的 $k\in (1,n)$ 的答案。

思路

先把输入按 $b$ 排序

设 $w(k,x)$ 为要选在前 $x$ 里面选 $k$ 个，那么

就是前 $x$ 个菜品内最小的 $k-1$ 个 $a$ 加上 $a_x+b_x$

显然，决策满足单调性，所以可以用一个分治来搞

维护最小的前 $k-1$ 个 $a$ 可以用主席树

code

#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define LL long long
using namespace std;
const int N = 2e5 + 5;
const LL inf = 1e18 + 5;
int n , pos , rt[N] , m , ans1[N];
LL ans[N] , a[N];
struct Re {LL a , b;
} re[N << 1];
struct Tr {int lp , rp , cnt;LL val;
} tr[10000005];
bool cmp1 (Re x , Re y) { return x.a < y.a; }
bool cmp2 (Re x , Re y) { return x.b < y.b; }
void glp (int p) {if (!tr[p].lp) tr[p].lp = ++pos;
}
void grp (int p) {if (!tr[p].rp) tr[p].rp = ++pos;
}
void change (int lst , int p , int l , int r , int x) {if (l == r) {tr[p].cnt ++;tr[p].val += a[l];}else {int mid = l + r >> 1;if (x <= mid) {glp (p);tr[p].rp = tr[lst].rp;change (tr[lst].lp , tr[p].lp , l , mid , x);}else {grp (p);tr[p].lp = tr[lst].lp;change (tr[lst].rp , tr[p].rp , mid + 1 , r , x);}tr[p].val = tr[tr[p].lp].val + tr[tr[p].rp].val;tr[p].cnt = tr[tr[p].lp].cnt + tr[tr[p].rp].cnt;}
}
LL getsum (int p , int l , int r , int k) {if (l == r)return a[l];else {int mid = l + r >> 1;if (tr[tr[p].lp].cnt >= k) {return getsum (tr[p].lp , l , mid , k);}else {return getsum (tr[p].rp , mid + 1 , r , k - tr[tr[p].lp].cnt) + tr[tr[p].lp].val;}}
}
void solve (int l , int r , int L , int R) {if (l > r) return;int mid = l + r >> 1 , now1=  0;LL now;fu (i , max (L , mid) , R) {// now = re[i].b + re[i].a + getsum (rt[i - 1] , 1 , n , mid - 1);now = re[i].b + getsum (rt[i] , 1 , n , mid);if (ans[mid] > now) {ans[mid] = now;now1 = i;ans1[mid] = i;}}solve (l , mid - 1 , L , now1);solve (mid + 1 , r , now1 , R);
}
int main () {freopen ("order.in" , "r" , stdin);freopen ("order.out" ,"w" , stdout);scanf ("%d" , &n);fu (i , 1 , n)scanf ("%lld%lld" , &re[i].a , &re[i].b);sort (re + 1 , re + n + 1 , cmp1);fu (i , 1 , n) a[i] = re[i].a , re[i].a = i;sort (re + 1 , re + n + 1 , cmp2);fu (i , 1 , n) ans[i] = inf;fu (i , 0 , n) rt[i] = ++pos;fu (i , 1 , n) {change (rt[i - 1] , rt[i] , 1 , n , re[i].a);}solve (1 , n , 1 , n);fu (i , 1 , n) {printf ("%lld\n" , ans[i]);}return 0;
}