Algoogle

Algorithm for Programming Contest

JOI 春合宿 2011 Apples

Category: JOI Tag: segment-tree

Apples

問題概要


M(<=100,000)個のクエリを処理する.

  • クエリA: 濃さD[i](<=1,000,000,000)のリンゴを1つ入荷する

  • クエリR: リンゴをN[i](<=100,000)個, その全ての組の濃さの差がB(<=1,000,000,000)以内になるようなもののうち濃さの総和が最大になるようなものを出荷する

解法


各リンゴの濃さに対してその後ろに幅Bの区間を考える.
その区間が重なる数をみると, 濃さのバラつきがB以内となるものの数がわかる.
これを各区間での最大値をもち, 区間に値を加えるsegment-treeで考えれば良い.
N[i]以上になる一番濃い場所を探すには各区間での最大値をもち, 条件を満たすようなものを右側優先に潜っていけばよい.

問題では濃さの値が大きいが入荷するリンゴは高々10^5個, つまり濃さの種類は高々10^5.
segment-treeの各ノードを全て持つと当然まずいので必要になったら作る感じでやる.

コード


(apples.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>
using namespace std;

struct segtree
{
        struct node
        {
                int mval, l , r, added;
                node *par, *left, *right;
                node() : mval(0), l(0), r(0), added(0){}
                node(node *p, int l, int r) : mval(0), l(l), r(r), added(0){
                        par = p;
                        left = right = NULL;
                }
        };
        int N;
        node *root;
        map<int,int> vs;

        segtree(){}
        segtree(int n) {
                N = 1;
                while(N < n) N *= 2;
                root = new node(NULL,0,N);
        }

        void update(int a, int b, int x) {
                vs[a] += x;
                if(!vs[a]) vs.erase(a);
                update(a,min(b,N),x,root);
        }
        int update(int a, int b, int x, node *v) {
                if(a >= v->r or b <= v->l) return v->mval;
                if(a <= v->l and v->r <= b) {
                        v->added += x;
                        v->mval += x;
                        return v->mval;
                }
                int m = (v->l+v->r)/2;
                if(v->left == NULL) v->left = new node(v, v->l, m);
                v->mval = update(a,b,x,v->left);
                if(v->right == NULL) v->right = new node(v, m, v->r);
                v->mval = max(v->mval, update(a,b,x,v->right));
                v->mval += v->added;
                return v->mval;
        }

        void query(int x, int b) {
                int r = get_right(x, root);
                if(r < 0) {
                        cout << "NO" << endl;
                        return;
                }
                auto it = vs.upper_bound(r-1);
                it--;
                vector<int> ws;
                while(x--) {
                        while(!it->second) it--;
                        ws.push_back(it->first);
                        it->second--;
                }
                for(int i = (int)ws.size()-1; i >= 0; i--) {
                        cout << ws[i] << (i>0? " ": "");
                        update(ws[i],ws[i]+b+1,-1,root);
                } cout << endl;
        }
        int get_right(int x, node *v) {
                if(v->mval < x) return -1;
                x -= v->added;
                if(v->right != NULL and v->right->mval >= x) return get_right(x, v->right);
                if(v->left != NULL and v->left->mval >= x) return get_right(x, v->left);
                return v->r;
        }
};

int q, b, x;

void solve()
{
        segtree st(1e9);
        char c;
        while(q--) {
                cin >> c;
                if(c == 'E') break;
                cin >> x;
                if(c == 'A') st.update(x,x+b+1,1);
                else st.query(x, b);
        }
}

void input()
{
        cin >> q >> b;
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        solve();
        return 0;
}

Comments