题解：UVA11136 Hoax or what

Bobi2014 · 2025-09-21 21:08:27 · 题解

这是一道可爱的可以使用线段树做的题目。

前置知识

• 线段树

思路

使用权值线段树实现添加、删除、查询这棵树内的最小值与最大值，值域是 [0,10^{6}]，多测记得清空线段树，答案要使用 long long 存储，所有测试数据设一共有 n 张发票，值域为 V，那么时间复杂度为 O(n \log V)。

Code

#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int n,k,x;
ll ans;
namespace SegmentTree{
    struct node{
        int l,r,sum;
    } tri[N << 2];
    void build(int p,int l,int r){
        tri[p].l = l;
        tri[p].r = r;
        tri[p].sum = 0;
        if(l == r){
            return;
        }
        int mid = (l + r) >> 1;
        build(p << 1,l,mid);
        build(p << 1 | 1,mid + 1,r);
    }
    void update(int p,int pos,int val){
        tri[p].sum += val;
        if(tri[p].l == tri[p].r){
            return;
        }
        int mid = (tri[p].l + tri[p].r) >> 1;
        if(pos <= mid){
            update(p << 1,pos,val);
        }else{
            update(p << 1 | 1,pos,val);
        }
    }
    int query_min(int p){
        if(tri[p].l == tri[p].r){
            return tri[p].l;
        }
        if(tri[p << 1].sum > 0){
            return query_min(p << 1);
        }else{
            return query_min(p << 1 | 1);
        }
    }
    int query_max(int p){
        if(tri[p].l == tri[p].r){
            return tri[p].l;
        }
        if(tri[p << 1 | 1].sum > 0){
            return query_max(p << 1 | 1);
        }else{
            return query_max(p << 1);
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while(true){
        cin >> n;
        if(n == 0){
            break;
        }
        SegmentTree::build(1,0,N - 10);
        ans = 0;
        while(n --){
            cin >> k;
            while(k --){
                cin >> x;
                SegmentTree::update(1,x,1);
            }
            int minn = SegmentTree::query_min(1),maxx = SegmentTree::query_max(1);
            ans += (ll)(maxx - minn);
            SegmentTree::update(1,minn,-1);
            SegmentTree::update(1,maxx,-1);
        }
        cout << ans << '\n';
    }
    return 0;
}