algoNote

プログラミング関連

Rustでシェルを作った

大学の課題でシェルを作ってみるというものがあり、言語は何でもよいということだったのでRustで実装しました。そのときの感想やら何やらを残しておこうと思います。

ソースコード

github.com

動作例

クリックで開く

単一コマンド

[algon@ThinkPad-X1-Carbon:~/msh (master %)]$ cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.03s
     Running `target/debug/msh`
msh version 0.2.0
algon@/home/algon/msh $ ls
Cargo.lock  Cargo.toml  README.md  build.rs  src  target  test
=> 0

標準入出力の切り替え

algon@/home/algon/msh $ wc < Cargo.toml > wc_res
=> 0
algon@/home/algon/msh $ cat wc_res
 11  29 199
=> 0
algon@/home/algon/msh $ wc < Cargo.toml > wc_res
error: `wc_res` already exists, use `>=` to overwrite it.
algon@/home/algon/msh $ wc < Cargo.toml >= wc_res
=> 0

パイプライン

algon@/home/algon/msh $ cd test  
=> 0
algon@/home/algon/msh/test $ vim data1
=> 0
algon@/home/algon/msh/test $ vim data2
=> 0
algon@/home/algon/msh/test $ cat data1 data2
a
aa
aa
aaa
aaa
bbb
bbb
b
aaa
=> 0
algon@/home/algon/msh/test $ cat data1 data2 | sort | uniq
a
aa
aaa
b
bbb
=> 0

終了

algon@/home/algon/msh/test $ exit
good bye.
[algon@ThinkPad-X1-Carbon:~/msh (master %)]$ 

標準エラー出力の切り替え

algon@/home/algon/msh/test $ vim ce.c
=> 0
algon@/home/algon/msh/test $ cat ce.c
#include <stdio.h>
int main() {
    printf("compile error")
    return 0;
}
=> 0
algon@/home/algon/msh/test $ gcc ce.c  
ce.c: In function ‘main’:
ce.c:4:5: error: expected ‘;’ before ‘return’
     return 0;
     ^~~~~~
=> 1
algon@/home/algon/msh/test $ gcc ce.c |& tee error
ce.c: In function ‘main’:
ce.c:4:5: error: expected ‘;’ before ‘return’
     return 0;
     ^~~~~~
=> 0
algon@/home/algon/msh/test $ cat error
ce.c: In function ‘main’:
ce.c:4:5: error: expected ‘;’ before ‘return’
     return 0;
     ^~~~~~
=> 0
algon@/home/algon/msh/test $ vim test.c
=> 0
algon@/home/algon/msh/test $ gcc test.c
=> 0
algon@/home/algon/msh/test $ ./a.out    
stdout
stderr
=> 0
algon@/home/algon/msh/test $ ./a.out > out >! err
=> 0
algon@/home/algon/msh/test $ cat out
stdout
=> 0
algon@/home/algon/msh/test $ cat err
stderr
=> 0

サブシェルの実行

algon@/home/algon/msh/test $ (cat | sort | uniq >= result) < data1
=> 0
algon@/home/algon/msh/test $ cat result
a
aa
aaa
=> 0

バックグラウンド実行

ジョブ管理機能は実装出来ていないため、簡易的なもの(フォアグラウンドで実行したりすることは出来ない)

algon@/home/algon/msh/test $ sleep 3; echo finished &
[run on the background]
=> 0
algon@/home/algon/msh/test $ finished

条件実行

algon@/home/algon/msh/test $ gcc ce.c && echo "ok"
ce.c: In function ‘main’:
ce.c:4:5: error: expected ‘;’ before ‘return’
     return 0;
     ^~~~~~
=> 1
algon@/home/algon/msh/test $ gcc test.c && echo "ok"
ok
=> 0
algon@/home/algon/msh/test $ gcc ce.c || echo "error"
ce.c: In function ‘main’:
ce.c:4:5: error: expected ‘;’ before ‘return’
     return 0;
     ^~~~~~
error
=> 0

シェル組み込みコマンド

cd

引数に-を指定すると直前にいたディレクトリに移動する。引数を省略すると$HOMEの指すディレクトリに移動する。

algon@/home/algon/msh/test $ cd ..
=> 0
algon@/home/algon/msh $ cd -
=> 0
algon@/home/algon/msh/test $ cd
=> 0
algon@/home/algon $ 

alias / unalias

「コマンド名 + 引数」をまとめるだけの簡易的なもの

algon@/home/algon/msh/test $ alias hello = "echo hello"
=> 0
algon@/home/algon/msh/test $ hello 
hello
=> 0
algon@/home/algon/msh/test $ unalias hello
=> 0
algon@/home/algon/msh/test $ hello
error: `hello` not found.

type

引数に指定したコマンドが外部コマンドなのか組み込みコマンドなのか、エイリアスなのかを表示する。

algon@/home/algon/msh/test $ type cd
`cd` is a builtin function.
=> 0
algon@/home/algon/msh/test $ type ls
/bin/ls
=> 0
algon@/home/algon/msh/test $ type hello
`hello` not found.
=> 0
algon@/home/algon/msh/test $ alias hello = "echo hello"
=> 0
algon@/home/algon/msh/test $ type hello
`hello` is an alias of `echo hello`
=> 0

exit

シェルを終了する。

algon@/home/algon/msh/test $ exit
good bye.

export / var / unset

algon@/home/algon/msh/test $ export HOGE = "hoge"
=> 0
algon@/home/algon/msh/test $ sh 
$ echo $HOGE
hoge
$ 
=> 0
algon@/home/algon/msh/test $ var xxx = 123  
=> 0
algon@/home/algon/msh/test $ echo $xxx
123
=> 0
algon@/home/algon/msh/test $ unset xxx
=> 0
algon@/home/algon/msh/test $ echo $xxx

=> 0

reload-path

$PATH内のコマンドを再検索する。

変数展開

algon@/home/algon/msh/test $ var msg = "hello"
=> 0
algon@/home/algon/msh/test $ echo $msg
hello
=> 0
algon@/home/algon/msh/test $ echo "${msg} world"
hello world
=> 0

コマンド置換

algon@/home/algon/msh/test $ echo run on $(uname)
run on Linux
=> 0
algon@/home/algon/msh/test $ echo nest $(echo is also $(echo supported))
nest is also supported
=> 0

開発の流れ

前提

  • シェルがどうやって動いているのかすらちゃんと理解出来ていない状態
  • Rustからシステムコールを呼びたい→nixというクレートを使うことにした

調査

  • パイプやリダイレクトがどうやって実装されているのか分からない状態なのでstraceコマンドを使って調べる
  • リダイレクトはファイルをopenしてdup2で設定している
  • パイプはpipe()でパイプのファイルディスクリプタを作成した後、dup2で繋いでいる
  • サブシェルはシェルからforkした新しいシェルのプロセス上で実行される
  • どういう流れで処理していけばいいのかが大体分かった

単一コマンドを実行出来るようにする

  • forkしてexecvすればよくて、ググるとコードがいろいろ出てくる
  • manを読みながら書いてみる
  • main関数が3つ目の引数を受け取れるの知らなかった……
  • Rustで書いて実行してみる→動く
  • 当たり前だけどちょっと感動

文法を定義する

  • 構文解析rust-pegでやることに
  • なんとなくPEGで構文を定義してみる
    • これが意外に難しい
    • かなり時間を掛けてなんとか定義できた(っぽい)
  • パイプをPipe(com_a, Pipe(com_b, com_c))みたいな感じで表すことにした
    • 木構造で書いてトラバースしながらforkすればいいなと思っていたが、実は作成したパイプを閉じる処理を行うのが面倒くさいということに後で気付く

ひたすら実装

  • 構文解析できてしまえばあとは実装するだけ
  • ひたすら書く
  • パイプ完成
  • 実はpipeのcloseを忘れていて「前のプロセスが終了したのに後ろのプロセスが終わらない」ような状態になる
    • 調べてみるとpipeが閉じられるときにEOFが送られるが、複数開いていたためEOFが送られず、後ろのプロセスが待ち続ける状態になっていた
    • ちゃんとcloseしたら動くようになった
    • パイプ周りの管理難しい
  • リダイレクトも実装
    • openでファイルを開いて繋ぐだけ
    • openに渡すフラグで挙動が変わる
      • O_EXCLを渡すとファイルが存在する場合にエラーになる
      • O_TRUNCを渡すと上書き
      • O_APPENを渡すと追記
      • O_CREATとかO_WRONLYとかを一緒に指定する
  • $PATHディレクトリ内のコマンドを呼べるようにした
    • 「ファイル名→パス」のテーブルを持っておいて、コマンド実行時にそれを参照する
  • 組み込み関数を実装
    • さっきのテーブルを改造
    • cdとかtypeとかを実装
  • コマンド置換を実装
    • パイプを作ってサブシェルの出力をそこに書き込む
    • パイプの入力側から読んで文字列として埋め込む
  • エイリアスを実装
    • 根本的な問題があり、簡易的な展開(コマンド名 + 引数)しかできない
  • このあたりでコマンドラインの扱いに問題があることに気付く
    • 例えばbashは、コマンドラインの変数埋め込みやコマンド置換などの展開処理を最初に行って、出来上がった文字列を空白で分割してコマンドラインを構成している
    • これを自分のシェルでは、最初に単語に分割してからいろいろやってるのでエイリアスがちゃんとエイリアスできない……
    • 変数展開とかコマンド置換も同様で、いろいろだめだなとなる
  • 作り直そうかと思ったが、実装が難しそうだしレポート提出の締切も近いのでここは割り切って、仕様ということにしてしまう
  • 環境変数・シェル変数が使えるようになった
  • 条件演算子を追加

    • どうでもいいけど、シェルの&&||は、終了コードを数値とみなして考えるとC言語と逆でちょっとおもしろい
  • Ctrl-cで死なないようにシグナル周りを設定

    • シェルのプロセスはそのままで、実行中のプロセスは終了して欲しい
    • nixのSigActionでSigIgnを指定すると何故か子プロセスが終了しない
    • ハンドラとして何もしない関数を指定すると意図した挙動になった(謎い)
    • シグナル周りはちゃんと理解出来ている気がしないので後で勉強したい

大体完成

  • いろいろ微調整して時間切れなのでとりあえずレポートを書いて提出

まとめ

  • Rust最高!
  • 動くと楽しいね

ブログに競プロのレーティングを表示するようにした(その2)

以前の記事でプログのサイドバーに競プロのレーティング(と色)を表示するjavascriptを紹介しました。 意外にも多くの方に使って頂けているようで嬉しいです。

algon-320.hatenablog.com

以前紹介したスクリプトではAtCoderのレーティング取得がYQLに依存していましたが、 残念ながらYQLは2019年1月でサービス終了してしまいました。 それに伴って、AtCoderのレーティング取得ができなくなっていました。

この問題に対応するために、簡易的なAPIサーバー的なもの(Kyopro-Ratingsと命名)を作成し、Heroku上で動かすことにしました。

デモ

機能

旧バージョンと同じです。

  • レーティング
  • 色付け
  • ユーザーページへのリンク

Kyopro-Ratings

Heroku上にレーティング取得用のサーバーを設置しました。サーバー側でレーティングを取得して、jsonでフロント側に送っています。

github.com

スクレイピングしている関係上、高頻度でリクエストが来た場合にエラーを返すようになっています。とりあえず200ms以内に複数のリクエストが来た場合に弾くようにしました。

ソースコード

こちらをサイドバーなどに設置しています。適当に改変して使ってください。
(htmlのtwitter・AOJの部分、jsのatcoder_user, codeforces_user, topcoder_algorithm_userの部分を自分のユーザー名に書き換えてください。)

なお、予告なくサーバーを停止するなどして動かなくなるかもしれませんので、その点はご了承ください。

<p>
  Twitter : <a id="twitter" href="https://twitter.com/algon_320" target="_blank"
    style="text-decoration:none;font-weight:bold;color:black;">@algon_320</a><br>
  AtCoder : <a id="atcoder_rating" target="_blank" style="text-decoration:none;font-weight:bold;">loading</a><br>
  Codeforces : <a id="codeforces_rating" target="_blank" style="text-decoration:none;font-weight:bold;">loading</a><br>
  TopCoder SRM : <a id="topcoder_algorithm_rating" target="_blank" style="text-decoration:none;font-weight:bold;">loading</a><br>
  AOJ : <a id="aoj" href="http://judge.u-aizu.ac.jp/onlinejudge/user.jsp?id=algon#1" target="_blank"
    style="text-decoration:none;font-weight:bold;color:black;">algon</a><br>
</p>

<script type="text/javascript">
  (function () {
    class User {
      constructor(service, handle) {
        this.service = service;
        this.handle = handle;
        this.rating = 0;
        this.color = '#000';  // デフォルトの色
      }
    }
    class Service {
      constructor(name, url) {
        this.name = name;
        this.url = url;
      }
    }

    let atcoder            = new Service('atcoder',            'https://atcoder.jp/user/');
    let codeforces         = new Service('codeforces',         'http://codeforces.com/profile/');
    let topcoder_algorithm = new Service('topcoder_algorithm', 'https://www.topcoder.com/members/');

    let atcoder_user            = new User(atcoder,            'algon');
    let codeforces_user         = new User(codeforces,         'algon_320');
    let topcoder_algorithm_user = new User(topcoder_algorithm, 'algon_320');

    let accounts = [atcoder_user, codeforces_user, topcoder_algorithm_user];

    // ユーザーページへのリンクのみ
    function set_html_without_rating(user) {
      let a = document.getElementById(user.service.name + '_rating');
      a.href = user.service.url + user.handle;
      a.innerHTML = user.handle;
      a.setAttribute('style', 'text-decoration:none;font-weight:bold;color:' + user.color);
    }
    // ユーザーページへのリンク + レーティング表示 + 色
    function set_html(user) {
      let a = document.getElementById(user.service.name + '_rating');
      a.href = user.service.url + user.handle;
      a.innerHTML = user.handle + ' (' + user.rating.toString() + ')';
      a.setAttribute('style', 'text-decoration:none;font-weight:bold;color:' + user.color);
    }

    function fetch_ratings() {
      let query_str = '';
      accounts.forEach(user => {
        query_str += user.service.name + "=" + user.handle + '&';
      });

      function error() {
        accounts.forEach(user => set_html_without_rating(user));
      }
      let xhr = new XMLHttpRequest();
      xhr.open('GET', 'https://kyopro-ratings.herokuapp.com/json?' + query_str, true);
      xhr.onload = function (e) {
        if (xhr.readyState === 4) {
          if (xhr.status === 200) {
            json = JSON.parse(xhr.responseText);
            // console.log(json);
            if ('error' in json) {
              error();
            } else {
              accounts.forEach(user => {
                let service_name = user.service.name;
                if (json[service_name]['status'] == 'success') {
                  user.rating = json[service_name]['rating'];
                  user.color = json[service_name]['color'];
                  set_html(user);
                } else {
                  set_html_without_rating(user);
                }
              });
            }
          }
        }
      };
      xhr.onerror = function (e) { error(); };
      xhr.ontimeout = function (e) { error(); };
      xhr.timeout = 10000;
      xhr.send(null);
    }
    fetch_ratings();
  })();
</script>

はてなブログの場合、管理画面のデザイン→サイドバー→カスタマイズから設置することが出来ます。

Lyft Level 5 Challenge 2018 - Final Round (Open Div. 1) C. Optimal Polygon Perimeter

問題

http://codeforces.com/contest/1074/problem/C

解法

マンハッタン距離での周囲の長さなので、選んだ多角形を囲むような(面積最小の)長方形の周囲の長さになります。よって、k=4以上のケースは自明で、n点を囲むような長方形の周長です。

問題はk=3のケースですが、「最左・最上」、「最左・最下」、「最右・最上」、「最右・最下」を固定して、それぞれについて残り1点をすべて試せば最大の周長が求まります。
(証明を書こうとしたけど上手く書けなかった&面倒になったのでeditorialを見てください(おい))

提出コード

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define INSEG(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void PSUM(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        // #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int n;
    cin >> n;
    vector<int> x(n), y(n);
    REP(i, n) cin >> x[i] >> y[i];
    auto mxx = max_element(ALL(x));
    auto mnx = min_element(ALL(x));
    auto mxy = max_element(ALL(y));
    auto mny = min_element(ALL(y));

    int ans = 0;
    for (auto itrx = begin(x), itry = begin(y); itrx != end(x); ++itrx, ++itry) {
        if (itrx != mnx && itry != mny) chmax(ans, abs(*itrx - *mnx) + abs(*itry - *mny));
        if (itrx != mnx && itry != mxy) chmax(ans, abs(*itrx - *mnx) + abs(*itry - *mxy));
        if (itrx != mxx && itry != mny) chmax(ans, abs(*itrx - *mxx) + abs(*itry - *mny));
        if (itrx != mxx && itry != mxy) chmax(ans, abs(*itrx - *mxx) + abs(*itry - *mxy));
    }

    vector<int> ansv;
    ansv.push_back(ans * 2);
    if (n >= 4) {
        ans = *mxx - *mnx + *mxy - *mny;
        vector<int> tmp(n - 4 + 1, ans * 2);
        ansv.insert(end(ansv), ALL(tmp));
    }
    cout << ansv << endl;
    return (0^_^0);
}

Lyft Level 5 Challenge 2018 - Final Round (Open Div. 1) B. Intersecting Subtrees

問題

http://codeforces.com/contest/1074/problem/B

解法

クエリの上限は5回ですが、2回で求まります。

まず、yの中から適当なラベルを選んで、自分の木での位置を質問します。この頂点をSとして、Sとxの頂点との距離が最小になる点をPとします。Pの位置の相手のラベルを質問して、これがyに含まれていればPが答えです。そうでなければ共有点はありません。

Pの求め方ですが、Sがxの部分木中に含まれれば、P=Sです。そうでない場合、適当に根を決めると、xの部分木はSの下側か上側にあることになります。

ここで、根付き木上でxの中で一番上にある点をT、xの中で部分木にSを含む頂点のうち一番下にあるものをB(存在するなら)とおくと、Bが存在するならP=Bで、そうでないならP=Tです。

xの部分木がSの上側にあるケースのイメージ
f:id:algon_320:20181108225630p:plain

xの部分木がSの下側にあるケースのイメージ
f:id:algon_320:20181108225637p:plain

提出コード

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define INSEG(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void PSUM(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        // #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

// in, out: 0-indexed
int ask(char type, int x) {
    cout << type << " " << x + 1<< endl;
    int y;
    cin >> y;
    if (y == -1) exit(0);
    return y - 1;
}
// in: 0-indexed
void answer(int v) {
    cout << "C " << v + 1 << endl;
}
signed main() {
    int Q;
    cin >> Q;
    while (Q--) {
        int n;
        cin >> n;
        vector<vector<int>> g(n);
        REP(i, n - 1) {
            int a, b;
            cin >> a >> b;
            a--, b--;
            g[a].pb(b);
            g[b].pb(a);
        }

        int k1;
        cin >> k1;
        vector<int> x(k1);
        cin >> x; FORE(i, x) i--;
        sort(ALL(x));

        int k2;
        cin >> k2;
        vector<int> y(k2);
        cin >> y; FORE(i, y) i--;
        sort(ALL(y));

        vector<bool> color(n);
        FORE(i, x) color[i] = true;

        int S = ask('B', y[0]);
        if (color[S]) {
            answer(S);
            continue;
        }

        int T = -1;
        auto findT = [&](auto f, int v, int p) -> void {
            if (color[v] && T == -1) T = v;
            FORE(w, g[v]) {
                if (w == p) continue;
                f(f, w, v);
            }
        };
        findT(findT, 0, -1);

        int B = -1;
        auto dfs = [&](auto f, int v, int p) -> bool {
            if (v == S) return true;
            bool found = false;
            FORE(w, g[v]) {
                if (w == p) continue;
                bool res = f(f, w, v);
                if (res && color[v] && B == -1) B = v;
                found |= res;
            }
            return found;
        };
        dfs(dfs, 0, -1);

        if (B != -1) {
            if (binary_search(ALL(y), ask('A', B))) {
                answer(B);
            } else {
                cout << "C -1" << endl;
            }
        } else {
            if (binary_search(ALL(y), ask('A', T))) {
                answer(T);
            } else {
                cout << "C -1" << endl;
            }
        }
    }
    return (0^_^0);
}

インタラクティブな問題では#define endl "\n"してはいけません...

Lyft Level 5 Challenge 2018 - Final Round (Open Div. 1) A. The Tower is Going Home

問題

http://codeforces.com/contest/1074/problem/A

解法

以下y軸平行な境界線を"縦線"、x軸平行な境界線を"横線"と呼びます。

方針としては、左からいくつの縦線を消すかを固定して、その時に横線をいくつ消す必要があるかを考えます。 (縦線については最も左にある縦線より右側に侵入することは出来ないので左から連続で消すことを考えればよい)

横線について、同じy座標にある別の境界と端点を共有しないという制約より、x1が1でないものについては無視して良いことが分かります。(端点を共有しない⇔x1が1でない境界についてx1-1の部分を通過出来るので)

縦線を左からk本消すことにすると、x1=1の横線のうち、k+1本目の縦線と交わるものを消せばよいことが分かります。 このような横線がl本あるとすると、k+lの最小値が答えになります。 k+1本目の縦線と交わる横線の個数は、横線を右端でソートしておけば二分探索で求まります。

提出コード

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define INSEG(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void PSUM(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int n, m;
    cin >> n >> m;
    vector<int> x(n);
    cin >> x;
    vector<int> y;
    REP(i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        if (a != 1) continue;
        y.push_back(b);
    }
    x.push_back(1'000'000'000);
    m = SZ(y), n = SZ(x);
    sort(ALL(x));
    sort(ALL(y));

    int ans = INF;
    REP(i, n) {
        int cnt = end(y) - lower_bound(ALL(y), x[i]);
        chmin(ans, i + cnt);
    }
    cout << ans << endl;
    return (0^_^0);
}