题解：P13239 「2.48sOI R1」化妆品

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 10; // 数组大小：2n (n ≤ 500,000)

int n;
int x[N], y[N];         // x[i]：第i个化妆品的时尚值，y[i]：美丽值
int f[N], b[N];         // f：按时尚值排序的索引数组，b：按美丽值排序的索引数组
bool vis[N];            // vis[i]：标记第i个化妆品是否已被选择
int curfl, curfr;       // 时尚值数组的指针：curfl（最小），curfr（最大）
int curbl, curbr;       // 美丽值数组的指针：curbl（最小），curbr（最大）
int m1, m2;             // M的总时尚值、总美丽值
int s1, s2;             // S的总时尚值、总美丽值

// 比较函数：按时尚值升序排序
bool cmpf(int a, int b) {
    return x[a] < x[b];
}

// 比较函数：按美丽值升序排序
bool cmpb(int a, int b) {
    return y[a] < y[b];
}

// 更新指针：确保四个指针指向未选元素
void update() {
    // 更新时尚值数组指针：跳过已选元素
    while (curfl <= curfr && vis[f[curfl]]) curfl++;
    while (curfl <= curfr && vis[f[curfr]]) curfr--;
    // 更新美丽值数组指针：跳过已选元素
    while (curbl <= curbr && vis[b[curbl]]) curbl++;
    while (curbl <= curbr && vis[b[curbr]]) curbr--;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    // 读入数据
    cin >> n;
    curfl = 1, curfr = 2 * n; // 初始化指针：时尚值数组范围[1, 2n]
    curbl = 1, curbr = 2 * n; // 初始化指针：美丽值数组范围[1, 2n]
    
    // 读入时尚值并初始化索引
    for (int i = 1; i <= 2 * n; i++) {
        cin >> x[i];
        f[i] = i; // 索引初始为自身
    }
    // 读入美丽值并初始化索引
    for (int i = 1; i <= 2 * n; i++) {
        cin >> y[i];
        b[i] = i;
    }
    
    // 对索引数组排序：f按x升序，b按y升序
    sort(f + 1, f + 2 * n + 1, cmpf);
    sort(b + 1, b + 2 * n + 1, cmpb);
    
    // 处理n轮选择
    for (int i = 1; i <= n; i++) {
        int q;
        cin >> q; // 本轮指示：1-时尚最大，2-美丽最大
        
        update(); // 更新指针，确保指向未选元素
        
        if (q == 1) { // M选择时尚值最大
            // 1. M选时尚值最大的化妆品
            int idx = f[curfr];   // 当前时尚值最大的索引
            m1 += x[idx];         // 累加时尚值
            m2 += y[idx];         // 累加美丽值
            vis[idx] = true;      // 标记已选
            curfr--;              // 指针左移
            
            update(); // 更新指针（S选择前需跳过新选元素）
            
            // 2. S选时尚值最小的化妆品
            idx = f[curfl];       // 当前时尚值最小的索引
            s1 += x[idx];         // 累加时尚值
            s2 += y[idx];         // 累加美丽值
            vis[idx] = true;      // 标记已选
            curfl++;              // 指针右移
        } else { // M选择美丽值最大
            // 1. M选美丽值最大的化妆品
            int idx = b[curbr];   // 当前美丽值最大的索引
            m1 += x[idx];         // 累加时尚值
            m2 += y[idx];         // 累加美丽值
            vis[idx] = true;      // 标记已选
            curbr--;              // 指针左移
            
            update(); // 更新指针
            
            // 2. S选美丽值最小的化妆品
            idx = b[curbl];       // 当前美丽值最小的索引
            s1 += x[idx];         // 累加时尚值
            s2 += y[idx];         // 累加美丽值
            vis[idx] = true;      // 标记已选
            curbl++;              // 指针右移
        }
    }
    
    // 输出结果
    cout << m1 << ' ' << m2 << '\n'; // M的时尚值和美丽值
    cout << s1 << ' ' << s2 << '\n'; // S的时尚值和美丽值
    
    return 0;
}