Algoogle

Algorithm for Programming Contest

AOJ 0536 Shuffle

Category: AOJ Tag: implementation

Shuffle

問題概要


n(<=1,000,000,000)枚の1からnまでの数字が書かれたカードがある.
上から1枚目からx枚目とy枚目からn枚目までのカードの位置をまとめて入れ替える.
このような操作をm(<=5,000)回分与える.
操作後, 上からp枚目からq枚目までのr以下の数字が書かれたカードの枚数を答えよ.

解法


r以下の数の区間を持つ.
あとは区間の列に対して区間を切り取る操作さえ書ければよい.

コード


(0536.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
#include <bits/stdc++.h>
using namespace std;

int n, m, o, p, q, x[5010], y[5010];
vector<pair<int,int>> sp;

vector<pair<int,int>> get_sect(int l, int r)
{
        auto lb = lower_bound(begin(sp),end(sp),make_pair(l,l)), ub = upper_bound(begin(sp),end(sp),make_pair(r,r));
        if(lb != begin(sp) and (lb-1)->second > l) lb--;
        vector<pair<int,int>> ret;
        for (auto it = lb; it != ub; it++) {
                pair<int,int> s;
                if(it->first < l) s.first = l;
                else s.first = it->first;
                if(it->second > r) s.second = r;
                else s.second = it->second;
                ret.push_back(s);
        }
        return ret;
}

void dump(vector<pair<int,int>> s)
{
        for(auto &e: s) cerr << "[" << e.first << "," << e.second << ") , "; cerr << endl;
}

int solve()
{
        sp.clear();
        sp.push_back(make_pair(0,q));
        for (int i = 0; i < m; i++) {
                auto a = get_sect(0, x[i]), b = get_sect(x[i], y[i]), c = get_sect(y[i],n);
                for(auto &e: a) {
                        e.first += n-x[i];
                        e.second += n-x[i];
                }
                for(auto &e: b) {
                        e.first += n-y[i]-x[i];
                        e.second += n-y[i]-x[i];
                }
                for(auto &e: c) {
                        e.first -= y[i];
                        e.second -= y[i];
                }
                sp = c;
                sp.insert(end(sp),begin(b),end(b));
                sp.insert(end(sp),begin(a),end(a));
        }
        auto a = get_sect(o,p);
        int ans = 0;
        for(auto &e: a) ans += e.second-e.first;
        return ans;
}

bool input()
{
        scanf("%d", &n);
        if(!n) return 0;
        scanf("%d%d%d%d", &m, &o, &p, &q);
        o--;
        for (int i = 0; i < m; i++) scanf("%d%d", x+i, y+i);
        return 1;
}

int main()
{
        while(input()) printf("%d\n", solve());
        return 0;
}

Comments