AOJ プログラミング応用 トピック#7, トピック#8, トピック#9

#トピック#7
##[ITP2_7_A](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_7_A)
###Set: Search

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>

#define rep(i,n) for(int i=0; i<(n); i++)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int q;
    cin >> q;
    set<int> st;
 
    rep(i, q){
        int query, x;
        cin >> query >> x;
        
        if(query==0){
            st.insert(x);
            cout << st.size() << endl;
        }else{
            cout << st.count(x) << endl;
        }
    }

    return 0;
}
```

##[ITP2_7_B](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_7_B)
###Set: Delete

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>

#define rep(i,n) for(int i=0; i<(n); i++)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int q;
    cin >> q;
    set<int> st;
 
    rep(i, q){
        int query, x;
        cin >> query >> x;
        
        if(query==0){
            st.insert(x);
            cout << st.size() << endl;
        }else if(query==1){
            cout << st.count(x) << endl;
        }else{
            st.erase(x);
        }
    }

    return 0;
}
```
##[ITP2_7_C](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_7_C)
###Set: Range Search

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>

#define rep(i,n) for(int i=0; i<(n); i++)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int q;
    cin >> q;
    set<int> st;
 
    rep(i, q){
        int query, x, r;
        cin >> query;
        
        if(query==0){
            cin >> x;
            st.insert(x);
            cout << st.size() << endl;
        }else if(query==1){
            cin >> x;
            cout << st.count(x) << endl;
        }else if(query==2){
            cin >> x;
            st.erase(x);
        }else{
            cin >> x >> r;;
            set<int>::iterator itr_l = st.lower_bound(x);
            set<int>::iterator itr_r = st.upper_bound(r);
            while(itr_l != itr_r){
                cout << *itr_l << endl;
                itr_l++;
            }
            
        }
    }

    return 0;
}
```

##[ITP2_7_D](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_7_D)
###Multi-Set

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>

#define rep(i,n) for(int i=0; i<(n); i++)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int q;
    cin >> q;
    multiset<int> st;
 
    rep(i, q){
        int query, x, r;
        cin >> query;
        
        if(query==0){
            cin >> x;
            st.insert(x);
            cout << st.size() << endl;
        }else if(query==1){
            cin >> x;
            cout << st.count(x) << endl;
        }else if(query==2){
            cin >> x;
            st.erase(x);
        }else{
            cin >> x >> r;;
            set<int>::iterator itr_l = st.lower_bound(x);
            set<int>::iterator itr_r = st.upper_bound(r);
            while(itr_l != itr_r){
                cout << *itr_l << endl;
                itr_l++;
            }
            
        }
    }

    return 0;
}
```

#トピック#8
##[ITP2_8_A](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_8_A)
###Map: Search

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>

#define rep(i,n) for(int i=0; i<(n); i++)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int q;
    cin >> q;
    map<string, int> m;
 
    rep(i, q){
        int query, x;
        string key;
        cin >> query;
        
        if(query==0){
            cin >> key >> x;
            if(m.find(key) == m.end()) m.insert(make_pair(key, x));
            else m[key] = x;
        }else if(query==1){
            cin >> key;
            cout << m[key] << endl;
        }
    }

    return 0;
}
```

##[ITP2_8_B](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_8_B)
###Map: Delete

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>

#define rep(i,n) for(int i=0; i<(n); i++)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int q;
    cin >> q;
    map<string, int> m;
 
    rep(i, q){
        int query, x;
        string key;
        cin >> query;
        
        if(query==0){
            cin >> key >> x;
            if(m.find(key) == m.end()) m.insert(make_pair(key, x));
            else m[key] = x;
        }else if(query==1){
            cin >> key;
            if(m.find(key) == m.end()) cout << 0 << endl;
            else cout << m[key] << endl;
        }else if(query==2){
            cin >> key;
            m.erase(key);
        }
    }

    return 0;
}
```

##[ITP2_8_C](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_8_C)
###Map: Range Search

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>

#define rep(i,n) for(int i=0; i<(n); i++)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int q;
    cin >> q;
    map<string, int> m;
 
    rep(i, q){
        int query, x;
        string key, right;
        cin >> query;
        
        if(query==0){
            cin >> key >> x;
            if(m.find(key) == m.end()) m.insert(make_pair(key, x));
            else m[key] = x;
        }else if(query==1){
            cin >> key;
            if(m.find(key) == m.end()) cout << 0 << endl;
            else cout << m[key] << endl;
        }else if(query==2){
            cin >> key;
            m.erase(key);
        }else if(query==3){
            cin >> key >> right;
            map<string, int>::iterator l = m.lower_bound(key);
            map<string, int>::iterator r = m.upper_bound(right);
            while(l != r){
                cout << l->first.c_str() << ' ' << l->second << endl;
                l++;
            }
        }
    
    }

    return 0;
}
```

##[ITP2_8_D](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_8_D)
###Multi-Map

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>

#define rep(i,n) for(int i=0; i<(n); i++)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int q;
    cin >> q;
    multimap<string, int> m;
 
    rep(i, q){
        int query, x;
        string key, right;
        cin >> query;
        
        if(query==0){
            cin >> key >> x;
            m.insert(make_pair(key, x));
        }else if(query==1){
            cin >> key;

            pair<multimap<string, int>::iterator, multimap<string, int>::iterator> itrs = m.equal_range(key);
            for(multimap<string, int>::iterator itr = itrs.first; itr != itrs.second; itr++){
                cout << itr->second << endl;
            }
            
        }else if(query==2){
            cin >> key;
            m.erase(key);
        }else if(query==3){
            cin >> key >> right;
            multimap<string, int>::iterator l = m.lower_bound(key);
            multimap<string, int>::iterator r = m.upper_bound(right);
            while(l != r){
                cout << l->first.c_str() << ' ' << l->second << endl;
                l++;
            }
        }
    
    }

    return 0;
}
```

#トピック#9
##[ITP2_9_A](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_9_A)
###Set Union

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>

#define rep(i,n) for(int i=0; i<(n); i++)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int n, m;
    cin >> n;
    set<int> A;
    set<int> B;
    set<int> result;
 
    rep(i, n){
        int x;
        cin >> x;
        A.insert(x);
    }
    
    cin >> m;
    rep(i, m){
        int x;
        cin >> x;
        B.insert(x);
    }
    
    set_union(A.begin(), A.end(), B.begin(), B.end(), inserter(result, result.end()));
    
    for(set<int>::iterator itr = result.begin(); itr != result.end(); itr++){
        cout << *itr << endl;
    }

    return 0;
}
```

##[ITP2_9_B](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_9_B)
###Set Intersection

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>

#define rep(i,n) for(int i=0; i<(n); i++)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int n, m;
    cin >> n;
    set<int> A;
    set<int> B;
    set<int> result;
 
    rep(i, n){
        int x;
        cin >> x;
        A.insert(x);
    }
    
    cin >> m;
    rep(i, m){
        int x;
        cin >> x;
        B.insert(x);
    }
    
    set_intersection(A.begin(), A.end(), B.begin(), B.end(), inserter(result, result.end()));
    
    for(set<int>::iterator itr = result.begin(); itr != result.end(); itr++){
        cout << *itr << endl;
    }

    return 0;
}
```

##[ITP2_9_C](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_9_C)
###Set Difference

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>

#define rep(i,n) for(int i=0; i<(n); i++)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int n, m;
    cin >> n;
    set<int> A;
    set<int> B;
    set<int> result;
 
    rep(i, n){
        int x;
        cin >> x;
        A.insert(x);
    }
    
    cin >> m;
    rep(i, m){
        int x;
        cin >> x;
        B.insert(x);
    }
    
    set_difference(A.begin(), A.end(), B.begin(), B.end(), inserter(result, result.end()));
    
    for(set<int>::iterator itr = result.begin(); itr != result.end(); itr++){
        cout << *itr << endl;
    }

    return 0;
}
```

##[ITP2_9_D](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_9_D)
###Set Symmetric Difference

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>

#define rep(i,n) for(int i=0; i<(n); i++)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int n, m;
    cin >> n;
    set<int> A;
    set<int> B;
    set<int> result;
 
    rep(i, n){
        int x;
        cin >> x;
        A.insert(x);
    }
    
    cin >> m;
    rep(i, m){
        int x;
        cin >> x;
        B.insert(x);
    }
    
    set_symmetric_difference(A.begin(), A.end(), B.begin(), B.end(), inserter(result, result.end()));
    
    for(set<int>::iterator itr = result.begin(); itr != result.end(); itr++){
        cout << *itr << endl;
    }

    return 0;
}
```