Atcoder ARC #002 D. ボードゲーム

Atcoder ARC #002 D. ボードゲーム

D: ボードゲーム - AtCoder Regular Contest 002 | AtCoder

２時間ほどかかったが自力で通したので、個人的にはARCのD（F）にしてはぬるめの考察問題だったと思う。

ボード上の２種類のコマ'o'と'x'の状態が与えられる。'o'は右に、'x'は左に向かって１歩ずつ進める。進行方向に異なるコマがあれば、それを踏み潰せる。'o'からスタートし、理想的に動いたとき、向かっている方向の端っこに先についた方が勝ちであるとき、どちらが勝つかを判定する問題。

まずサンプルケースを見ると気づくことだが、進行方向に相手のコマがないコマが存在すれば、それらの端までの距離を比較するだけで答えが出る。そうでない場合は、すべてのコマが左に'o'のみ、右に'x'のみというペアに分けられ、これらは独立に考えて良い。少し考察すると、自分のターンで動かせるところが、「o'スペース'x'」の部分だけになったときは負ける、ということがわかる。よって、できる限りこの状況に到るまでの自分にとっての余裕のようなものを最大化し、相手にとっての余裕のようなものを最小化するような動きをとればよい。さらに考察すると、動かすべきコマは、向かい合うコマのそれぞれの後ろのコマの個数の和が最も大きいものであることがわかる。なぜならば、中央のコマを動かすことで自分にとっての余裕はその後ろのコマの数だけ進むスペースを作ることができ、さらに相手が進む距離を１少なくできるので、相手にとって増やせたであろう余裕度の増加を阻止できるからである。この和を余裕度とよぶことにし、各ペアについて、余裕度がどれくらい生まれるかをカウントし、最後に比較すると答えがわかる。O(HW)。余裕度の計算はすでに解いていたC: ウサギ跳び - AtCoder Regular Contest 041 | AtCoderと似た発想だったので、すぐに実装できた。

#include "bits/stdc++.h"
using namespace std;
#define OUT(x) cout << #x << " = " << x << endl
#define rep(i, n)             for (int (i) = 0; (i) < (int)(n); (i)++)
#define rer(i, l, r)          for (int (i) = (int)(l); (i) <= (int)(r); (i)++)
#define reu(i, l, r)          for (int (i) = (int)(l); (i) < (int)(r); (i)++)
#define all(x)                (x).begin(), (x).end()
#define rall(x)               (x).rbegin(), (x).rend()
template<typename T> void pv(T a, T b) { for (T i = a; i != b; i ++) cout << *i << " "; cout << endl; }
template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; }
int in() { int x; scanf("%d", &x); return x; }
long long lin() { long long x; scanf("%lld", &x); return x; }

static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
#define int long long

signed main() { 
        int H, W;
        cin >> H >> W;
        vector<string> c(H);
        rep(i, H) cin >> c[i];
        int od = INFL, xd = INFL;
        rep(i, H) {
                rep(j, W) {
                        if (c[i][j] == 'x') { //最初に'x'がある場合は向かい合うコマがないことを意味する
                                amin(xd, j);
                                break;
                        } 
                        if (c[i][j] == 'o') break;
                }
                reverse(all(c[i])); //reverseして同様に'o'も考える
                rep(j, W) {
                        if(c[i][j] == 'o') {
                                amin(od, j);
                                break;
                        }
                        if (c[i][j] == 'x') break;
                }
                reverse(all(c[i])); //元に戻す
        }
        if (od != INFL || xd != INFL) { //どちらかが向き合ってないコマをもっていれば、答えが出る
                if (od <= xd) cout << 'o' << endl;
                else cout << 'x' << endl;
                return 0;
        }
        vector<pair<int, pair<vector<int>, vector<int>>>> P; //各ペアを格納する。<コマの総数から各コマの先頭の数(=2)を引いた数, <'o'のある座標, 'x'のある座標>>で一つのペアにする
        vector<int> opoint;
        vector<int> xpoint;
        rep(i, H) {
                rep(j, W) {
                        if (c[i][j] == '.') continue;
                        if (c[i][j] == 'o') {
                                if (!xpoint.empty()) {
                                        reverse(all(opoint)); //'o'については、中央からみて左にindexが増加するようにしておくとわかりやすい
                                        P.push_back(make_pair(opoint.size() + xpoint.size() - 2, make_pair(opoint, xpoint)));
                                        opoint.clear();
                                        xpoint.clear();
                                }
                                opoint.push_back(j);
                        } else {
                                xpoint.push_back(j);
                        }
                }                 
        }
        reverse(all(opoint)); 
        if (!xpoint.empty()) P.push_back(make_pair(opoint.size() + xpoint.size() - 2, make_pair(opoint, xpoint)));
        sort(rall(P)); //余裕度（？）で降順にソートして大きいものからコマを進める
        bool oturn = true; //最初'o'からはじめる
        int ocnt = 0, xcnt = 0; //余裕度
        for (auto i : P) {
                int l = i.second.first.front(); //'o'の先頭のコマ
                int r = i.second.second.front(); //'x'の先頭のコマ
                int d = r - l; //先頭のコマ同士の間にあるマスの数＋１
                d --;
                //mid - 1に'o'がきて、mid + 1に'x'がくるようにmid（スペースになるマスの位置）をつくる
                if (d & 1) { //奇数個のマスがあるときは、ターンは変わらない
                        int mid = (l + r) / 2;
                        reu(j, 1, i.second.first.size()) ocnt += (mid - 1) - i.second.first[j] - j;
                        reu(j, 1, i.second.second.size()) xcnt += i.second.second[j] - (mid + 1) - j;
                } else { //偶数個のときはターンが必ず変わる上に、どちらのターンから始まるかによって、先頭のコマの到達位置も変わるので注意
                        if (oturn) {
                                int mid = (l + r + 1) / 2;
                                reu(j, 1, i.second.first.size()) ocnt += (mid - 1) - i.second.first[j] - j;
                                reu(j, 1, i.second.second.size()) xcnt += i.second.second[j] - (mid + 1) - j;
                        } else {
                                int mid = (l + r) / 2;
                                reu(j, 1, i.second.first.size()) ocnt += (mid - 1) - i.second.first[j] - j;
                                reu(j, 1, i.second.second.size()) xcnt += i.second.second[j] - (mid + 1) - j;
                        }
                        oturn ^= 1;
                }
        }
        if (oturn) { //余裕度を使って動かし始めるときにどちらのターンかで最終的な答えを出す
                cout << (ocnt > xcnt ? 'o' : 'x') << endl;
        } else {
                cout << (ocnt < xcnt ? 'x' : 'o') << endl;
        }
        return 0;
}               

Atcoder AGC #009 B. Tournament

Atcoder AGC #009 B. Tournament

B: Tournament - AtCoder Grand Contest 009 | AtCoder

解いたあとに解説見たらDPでごにょごにょって書いていたが、もっとわかりやすくあっさり書けた。

n人の人が、負けたらそこで終わりのトーナメント形式で優勝を目指して戦う。番号１の人が優勝したことはわかっており、他の人が誰に負けたかという情報も与えられる。ありうるトーナメントの形のうち、深さの最小値を求める問題。まず番号１を根として、AがBに勝ったという情報から、AからBに子をつくるように木を構成してみる。そこからトーナメントの形を構成しようと考えると、相異なる親をもつ葉を同時にコスト１で削除していく操作を繰り返すことで、根以外のノードをすべて削除するまでにかかるコスト、が求める最小値に一致することが証明できる。あるノードを親としてその複数の子ノードについて考える。それら以下のノード全てを削除するためのコストはわかっているものとしてよい。それが例えば、1, 1, 1だったとすると、コストは親を削除するコストを除いて3になる。なぜなら、削除の操作は親ノードが一致する場合は同時に行えないので、１つずつ削除するしかないからである。同様に、コストが1, 2, 3である場合も3になることがわかる。なぜなら、１回目の操作でコストは0, 1, 2になり、２回目の操作で0, 0, 1になり、3回目の操作で0, 0, 0になるからである。結局、あるノードのコストがxであることを、そのノードはx秒後以降に削除できる、という条件に読み替えて、全てのノードを削除するのに何秒かかるかという問題に帰着できる。これは昇順にソートして、貪欲に調べて行くことができる。計算量はソートの部分が一番大きく、O(nlogn)。

#include "bits/stdc++.h"
using namespace std;
#define rep(i, n)             for (int (i) = 0; (i) < (int)(n); (i)++)
#define all(x)                (x).begin(), (x).end()

vector<int> g[101010];

int dfs(int s) {
        int res = 0;
        vector<int> v;
        for (auto ns : g[s]) v.push_back(dfs(ns));
        sort(all(v)); //削除コスト順にソート
        rep(i, v.size()) res = max(res + 1, v[i]);  //小さいものから見ていき、今見ているノードか、時刻＋１の大きい方をとる
        return res + 1; //親ノードを削除するコストを足す
}

signed main() { 
        int n;
        cin >> n;
        rep(i, n - 1) {
                int a;
                cin >> a;
                a --;
                g[a].push_back(i + 1);
        }
        cout << dfs(0) - 1 << endl;
        return 0;
}               

AGCのB問題はすべて埋めたので、次はC問題を埋めていく。

Atcoder ARC #022 B. 細長いお菓子

Atcoder ARC #022 B. 細長いお菓子

B: 細長いお菓子 - AtCoder Regular Contest 022 | AtCoder

数列が与えられるので、その部分列の中で、相異なる数のみを含むもので最長のものの長さを答える問題。すごくシンプルなのだけれど、少し手こずった。いまどの区間の数列を見ているのかを[l, r)として、aiについて場合分けして考える。それぞれの数が出てきたときに、その数がどこに出てきたかをpに記録する。そして、そのaiが今見ている区間からはずれているか、あるいは-1で初期化されたままであれば、区間に追加する。区間に含まれているならば、そのpが示すポインタ＋１の場所をlとしてから区間に追加する。以上を実装すると下のようになる。

#include "bits/stdc++.h"
using namespace std;
#define rep(i, n)             for (int (i) = 0; (i) < (int)(n); (i)++)
template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; }
int in() { int x; scanf("%d", &x); return x; }

signed main() { 
        int n = in();
        vector<int> p(101010, -1);
        int l = 0, ans = -1;
        rep(r, n) {
                int a = in();
                if (p[a] < l) amax(ans, r - l + 1);
                else l = p[a] + 1;
                p[a] = r;
        }
        cout << ans << endl;
        return 0;
}               

Atcoder ARC #048 D. たこ焼き屋とQ人の高橋君

Atcoder ARC #048 D. たこ焼き屋とQ人の高橋君

D: たこ焼き屋とQ人の高橋君 - AtCoder Regular Contest 048 | AtCoder

ある木と、各ノードにたこ焼き屋さんがあるかどうかの情報が与えられる。最初はノード間の移動に２秒かかるが、たこ焼き屋さんがあるノードでたこ焼きを食べれば、１秒でノード間を移動できるようになる。クエリ(s, t)が順に与えられるので、sからtまで移動するのにかかる最短の時間を求めていく、という問題。まず木なので、(s, t)の最短経路は必ず通る。たこ焼きを食べる場合は、その経路上のあるノードからたこ焼き屋さんまでの経路を通り、折り返し、もとのノードに戻り、もとの経路を進むことになるはずである。そのあるノードをx、たこ焼き屋さんをyとし、xとyの距離をd(x, y)で表すと、求める値は、min(2 * d(s, x) + 2 * d(x, y) + d(x, y) + d(x, t)) = min(d(s, t) + d(s, x) + 3 * d(x, y))である。下準備として、各ノードについて、たこ焼き屋さんまでの最短距離pを保存しておく。これは、たこ焼き屋さんのあるノードをキューにあらかじめp == 0 としながらpushしておき、そこからp == INFならば更新していく幅優先探索することで調べられる。また、様々な距離を扱うため、根付き木で考えると都合が良い。根付き木上で、ごにゃごにゃ距離を計算すると、3 * p[i] + depth[i]と3 * p[i] - depth[i]の最小値が重要になることがわかる。木の任意のパス上の頂点に書かれた数の最小値を高速で計算するために、ダブリングとdpをうまく使う（HL分解的なことをして、セグメント木にのせたりできるらしいが、それはよく知らない）。dp[i][j] := ノードiから、距離の２のj乗まで親をたどったときのその区間の最小値、をあらかじめ計算しておく。すると、log(n)で各パス上の最小値を計算できる。図なしには説明しにくいが、lca(s, t)の位置とxの位置の前後関係で場合分けをしてそれぞれ計算する。

#include "bits/stdc++.h"
using namespace std;
#define rep(i, n)             for (int (i) = 0; (i) < (int)(n); (i)++)
template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; }
 
#define maxv 101010
#define maxl 20
static const int INF = 0x3f3f3f; //大きくしすぎるとオーバーフローするので注意
 
int depth[maxv];
int dbl[maxv][maxl];
int dp[2][maxv][maxl];
vector<int> g[maxv];
 
int lca(int x, int y) {
        if (depth[x] < depth[y]) swap(x, y);
        rep(i, maxl) { 
                if ((depth[x] - depth[y]) & (1 << i)) x = dbl[x][i];
        }
        if (x == y) return x;
        for (int i = maxl - 1; i >= 0; i --) {
                if (dbl[x][i] != dbl[y][i]) {
                        x = dbl[x][i];
                        y = dbl[y][i];
                }
        }
        return dbl[x][0];
}
 
int getmin(int x, int d, int t) {　//木上において、ノードxから距離dだけ親をたどったところまでの区間の最小値をダブリングで求める
        int res = INF;
        rep(i, maxl) {
                if (d & (1 << i)) {
                        res = min(res, dp[t][x][i]);
                        x = dbl[x][i];
                }
        }
        return res;
}
 
void dfs(int v, int u, int d) {
        dbl[v][0] = u;
        depth[v] = d;
        for (auto i : g[v]) {
                if (u == i) continue;
                dfs(i, v, d + 1);
        }
}
 
signed main() { 
        int n, query;
        cin >> n >> query;
        rep(i, n - 1) {
                int a, b;
                cin >> a >> b;
                a --, b --;
                g[a].push_back(b);
                g[b].push_back(a);
        }
        string s;
        cin >> s;
        dfs(0, 0, 0);
        int p[maxv];
        rep(i, n) p[i] = INF; //最初はすべてINF
        queue<int> q;
        rep(i, n) if (s[i] == '1') {
                q.push(i);
                p[i] = 0;
        }
        while (!q.empty()) { //たこ焼き屋さんがあるところから幅優先探索
                int x = q.front(); q.pop();
                for (auto i : g[x]) if (p[i] == INF) {
                        q.push(i);
                        p[i] = p[x] + 1;
                }
        }
        rep(i, maxl - 1) rep(j, n) dbl[j][i + 1] = dbl[dbl[j][i]][i]; //ダブリングの初期化
        rep(i, n) rep(t, 2) dp[t][i][0] = p[i] * 3 + (t == 0 ? (-1) * depth[i] : depth[i]);
        rep(i, maxl - 1) rep(j, n) rep(t, 2) dp[t][j][i + 1] = min(dp[t][j][i], dp[t][dbl[j][i]][i]);
        while (query --) {
                int s, t;
                cin >> s >> t;
                s --, t --;
                int c = lca(s, t);
                int l = depth[s] - depth[c], r = depth[t] - depth[c];
                int x = getmin(s, l, 0), y = getmin(t, r, 1);
                int ans = (l + r) * 2; //寄り道しない場合
                amin(ans, l * 2 + p[c] * 3 + r); //lcaがxと一致するとき
                amin(ans, l * 2 + x + depth[c] + r); //lcaよりs側にxがあるとき
                amin(ans, l * 2 + y + r - depth[c]); //lcaよりt側にxがあるとき
                cout << ans << endl;
        }
        return 0;
}               

dpが難しい。。。。

Atcoder ARC #029 C. 高橋くんと国家

Atcoder ARC #029 C. 高橋くんと国家

C: 高橋君と国家 - AtCoder Regular Contest 029 | AtCoder

ある無向グラフが与えられる。その各辺について、それを舗装するコストと、各都市についてそこに交易所を設置するコストが与えられている。すべての都市について、その都市に交易所があるか、または舗装された道のみを経由して交易所がある都市にいけるうようにするための最小コストを求める問題。まずD: 浮気予防 - AtCoder Beginner Contest 010 | AtCoderの発想に少し近いが、２つの操作を別々に考えることが難しいときは、それらを同一のものとして考えられるようにグラフを変形することが有効な場合がある。舗装の操作は、ある２つの部分を連結にしていく操作であり、それを最小にしていきたいとなると、最小全域木のアルゴリズムとそっくりであることに気づく。そこで、ある都市に交易所を設置する操作を、その都市と、交易所を表す新たな頂点Xをその設置コストでつなぐという操作に置き換えると、同様の操作として扱える。最小全域木のアルゴリズムはUnionFindで実装した。

#include "bits/stdc++.h"
using namespace std;
#define OUT(x)                cout << #x << " = " << x << endl
#define rep(i, n)             for (int (i) = 0; (i) < (int)(n); (i)++)
#define rer(i, l, r)          for (int (i) = (int)(l); (i) <= (int)(r); (i)++)
#define reu(i, l, r)          for (int (i) = (int)(l); (i) < (int)(r); (i)++)
#define all(x)                (x).begin(), (x).end()
#define rall(x)               (x).rbegin(), (x).rend()
template<typename T> void pv(T a, T b) { for (T i = a; i != b; i ++) cout << *i << " "; cout << endl; }
template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; }
int in() { int x; scanf("%d", &x); return x; }
long long lin() { long long x; scanf("%lld", &x); return x; }

#define int long long

struct UnionFind {
        vector<int> par;
        UnionFind(int n) : par(n) { for (int i = 0; i < n; i++) par[i] = i; }
        int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
        bool same(int x, int y) { return find(x) == find(y); }
        void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; par[x] = y; }
};

signed main() { 
        int n, m;
        cin >> n >> m;
        vector<pair<int, pair<int, int>>> e;
        rep(i, n) {
                int a;
                cin >> a;
                e.push_back(make_pair(a, make_pair(0, i + 1)));  //交易所設置のコストaで、各頂点を頂点0とつなぐ
        }
        rep(i, m) {
                int a, b, c;
                cin >> a >> b >> c;
                e.push_back(make_pair(c, make_pair(a, b)));
        }
        sort(all(e));
        UnionFind uf(n + 10);
        int ans = 0;
        for (auto v : e) {
                int s = v.second.first;
                int t = v.second.second;
                if (!uf.same(s, t)) {
                        uf.unite(s, t);
                        ans += v.first;
                }
        }
        cout << ans << endl;
        return 0;
}               

CF Croc Champ 2013 - Round 1 E. Copying Data

Codeforces Croc Champ 2013 - Round 1 E. Copying Data

Problem - E - Codeforces

数列a[i]とb[i]が与えられる。これらの数列について、以下の２種類のクエリを実行していくという問題。
・aのx番目からk個をbのy番目からk個にコピーする
・b[x]を出力する
以下前者をコピーのクエリと呼ぶ。

まず、b[u]を求めるときに、その位置の数が最後にいつ変更されたか（＝その位置を含む最後のコピーのクエリはどれか）がわかれば、答えがわかりそうである。実際、そのコピーのクエリが何番目だったかがわかれば、そのクエリのx, yより、a[x + (u - y)]がb[u]に等しいことがわかる。なぜならば、そのコピーする部分の先頭がa[x]であり、u - yはその位置が先頭からどれくらい進んでいるかを表すので、a[x + u - y]がその位置にコピーされた数値に等しいのである。したがって、セグメントツリーなどをつくり、コピーのクエリがくるたびに、その区間をそのクエリが何番目であるかを上書きしていけばよい。

以下のサイトを参考にさせていただき、区間をある数で塗りつぶす実装をした。
Lazy Propagation Segment Tree

get関数はなんとなくで書いた。出力のクエリがくるごとに上記サイトのfixに相当するようなことをしている。

#include "bits/stdc++.h"
using namespace std;
#define OUT(x)                cout << #x << " = " << x << endl; 
#define rep(i, n)             for (int (i) = 0; (i) < (int)(n); (i)++)
#define rer(i, l, r)          for (int (i) = (int)(l); (i) <= (int)(r); (i)++)
#define reu(i, l, r)          for (int (i) = (int)(l); (i) < (int)(r); (i)++)
#define each(i, v)            for (auto i : v)
#define all(x)                (x).begin(), (x).end()
#define rall(x)               (x).rbegin(), (x).rend()
#define pb                    push_back
#define bp(x)                 __builtin_popcount(x)
#define mp(x, y)              make_pair((x), (y))
#define fi                    first
#define se                    second
#define setp(x)               setprecision(x)
#define mset(m, v)            memset(m, v, sizeof(m))
#define sz(x)                 (int)(x.size())
static const int INF        = 0x3f3f3f3f;
static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
static const int MOD        = 1000000007;
static const double PI      = 3.141592653589793238462643383279;

#define int                   long long

typedef vector<double>        vd;
typedef vector<string>        vs;
typedef vector<bool>          vb;
typedef vector<int>           vi;
typedef pair<int, int>        pii;
typedef vector<pii>           vpii;

template<typename T> void pv(T a, T b) { for (T i = a; i != b; i ++) cout << *i << " "; cout << endl; }
template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; }
int in() { int _x; scanf("%d", &_x); return _x; }
long long lin() {long long _x; scanf("%lld", &_x); return _x; };

struct SegmentTree {
        vector<int> lazy;
        int n;
        SegmentTree(int x) {
                n = pow(2, ceil(log2(x)));
                lazy.resize(2 * n - 1);
                for (int i = 0; i < 2 * n - 1; i ++) lazy[i] = INF;//初期化
        }
        void push(int k) {
                if (lazy[k] == INF) return;
                lazy[k * 2 + 1] = lazy[k * 2 + 2] = lazy[k];
                lazy[k] = INF;
        }
        int get(int k) {
                int res = INF;
                k += n - 1;//葉から根までを見ていき、INFじゃないものがあるたびにresを更新している。上にあるもののほうがあとで上書きされた値だからである
                if (lazy[k] != INF) res = lazy[k];
                while (k > 0) {
                        k = (k - 1) / 2;
                        if (lazy[k] != INF) res = lazy[k];
                }
                return res;
        }
        // [l, r))
        void fill(int a, int b, int val) { fill(a, b, val, 0, 0, n); }//区間[a, b)をvalで塗りつぶす
        void fill(int a, int b, int val, int k, int l, int r) {
                if (r <= a || b <= l) return;
                if (a <= l && r <= b) {
                        lazy[k] = val;
                        return;
                }
                push(k);
                int m = (l + r) / 2;
                fill(a, b, val, k * 2 + 1, l, m);
                fill(a, b, val, k * 2 + 2, m, r);
        }
};

struct Q {
        int x, y;
};

signed main() {
        int n, q;
        cin >> n >> q;
        vi a(n), b(n);
        rep(i, n) cin >> a[i];
        rep(i, n) cin >> b[i];
        SegmentTree st(n);
        vector<Q> query;
        rep(i, q) {
                int t;
                cin >> t;
                if (t == 1) {
                        int x, y, k;
                        cin >> x >> y >> k;
                        x --, y --;
                        query.pb({x, y});
                        st.fill(y, y + k, query.size() - 1); //yからk個をquery.size() - 1（＝クエリ番号）で塗りつぶす
                } else {              
                        int u;
                        cin >> u;
                        u --;
                        if (st.get(u) == INF) cout << b[u] << endl; //そのままなら、一回もその位置にはコピーされていない
                        else {
                                int q = st.get(u); //クエリ番号を取り出してクエリを復元
                                int qx = query[q].x;
                                int qy = query[q].y;
                                cout << a[qx + u - qy] << endl;
                        }
                }
        }
        return 0;
}

CF Round #271 Div.2 F. Ant colony

Codeforces Round #271 Div.2 F. Ant colony

Problem - F - Codeforces

ある数列に対するクエリに順に答えていく。クエリは[l, r]で与えられ、その区間の各数について、「その数が他のすべての数を割り切る」という条件を満たさないものの数を求める。総数はr-l+1とわかっているので、結局条件を満たすものの数を数える。

割とすぐに実装したが、最初のコードはWA。なにが間違っているのかに気づいてから、実装まではかなり時間がかかった。。。しかもかなり冗長な実装になっていると思う。。。

まずセグメント木をつくる。割と何も考えずに実装している感もあるが、４つの状態変数を持たせて実装した。具体的には、S = {f := その区間の最小値ですべての数を割り切れるかどうか？, p := その区間の最小値, cnt := 最小値の個数, candidate := すべてを割り切ることができる最小値になりうる値の候補の最大値 }とした。多分驚くほど無駄が多い 笑。

初期化は、各数tに対して、{1, t, 1, t}として、更新していく。まずcandidateは、子ノードのcandidateのgcdをとることで更新できる。次に、少なくとも一方の最小値が1であるならば、1はすべてを割り切れるので、 あとは個数のみに注目すればよいので分けて考えた。そうでないならば、pの大小を評価し、その小さい方がcandidateを割り切るならば、その数がすべてを割り切る最小値になりうるので、f = 1 とする。などといった感じで実装した。

#include "bits/stdc++.h"
using namespace std;
#define OUT(x)                cout << #x << " = " << x << endl; 
#define rep(i, n)             for (int (i) = 0; (i) < (int)(n); (i)++)
#define rer(i, l, r)          for (int (i) = (int)(l); (i) <= (int)(r); (i)++)
#define reu(i, l, r)          for (int (i) = (int)(l); (i) < (int)(r); (i)++)
#define each(i, v)            for (auto i : v)
#define all(x)                (x).begin(), (x).end()
#define rall(x)               (x).rbegin(), (x).rend()
#define pb(x)                 push_back(x)
#define bp(x)                 __builtin_popcount(x)
#define mp(x, y)              make_pair((x), (y))
#define fi                    first
#define se                    second
#define setp(x)               setprecision(x)
#define mset(m, v)            memset(m, v, sizeof(m))
#define sz(x)                 (int)(x.size())
static const int INF        = 0x3f3f3f3f;
static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
static const int MOD        = 1000000007;
static const double PI      = 3.141592653589793238462643383279;

#define int                   long long

typedef vector<double>        vd;
typedef vector<string>        vs;
typedef vector<bool>          vb;
typedef vector<int>           vi;
typedef pair<int, int>        pii;
typedef vector<pii>           vpii;

template<typename T> void pv(T a, T b) { for (T i = a; i != b; i ++) cout << *i << " "; cout << endl; }
template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; }
int in() { int _x; scanf("%d", &_x); return _x; }
long long lin() {long long _x; scanf("%lld", &_x); return _x; };

struct S {
        bool f;
        int p;
        int cnt;
        int candidate;
};

struct SegmentTree {
        vector<S> data;
        int n;
        SegmentTree(int x) {
                n = 1;
                while (n < x) n *= 2;
                data.resize(2 * n);
                for (int i = 0; i < 2 * n; i ++) data[i] = { 0, -1, -1, -1}; //初期状態
        }
        S merge(S x, S y) {
                if (x.p == -1) return y; //どちらかが一番最初の初期化状態ならば、もう一方を返す
                if (y.p == -1) return x;
                S d;
                d.candidate = __gcd(x.candidate, y.candidate); 　
                if (x.p == 1 || y.p == 1) { //少なくとも一方が1である場合
                        d.f = 1;
                        d.p = 1;
                        if (y.p != 1) d.cnt = x.cnt;
                        else if (x.p != 1) d.cnt = y.cnt;
                        else d.cnt = x.cnt + y.cnt;
                } else {
                        if (x.p > y.p) {
                                d.p = y.p;
                                d.cnt = y.cnt;
                                if (d.candidate % y.p == 0) d.f = 1;
                                else d.f = 0;
                        } else if (x.p < y.p) {
                                d.p = x.p;
                                d.cnt = x.cnt;
                                if (d.candidate % x.p == 0) d.f = 1;
                                else d.f = 0;
                        } else {
                                d.p = x.p;
                                d.cnt = x.cnt + y.cnt;
                                if (x.f && y.f) d.f = 1;
                                else d.f = 0;
                        }
                }
                return d;
        }
        // update k th element
        void update(int k, S p) {
                k += n - 1;
                data[k] = p;
                while (k > 0) {
                        k = (k - 1) / 2;
                        data[k] = merge(data[k * 2 + 1], data[k * 2 + 2]);
                }
        }
        // [l, r))
        S query(int a, int b) { return query(a, b, 0, 0, n); }
        S query(int a, int b, int k, int l, int r) {
                if (r <= a || b <= l) return { 0, -1, -1, -1};
                if (a <= l && r <= b) return data[k];
                int m = (l + r) / 2;
                return merge(query(a, b, k * 2 + 1, l, m), query(a, b, k * 2 + 2, m, r));
        }
};

signed main() { 
        int n;
        cin >> n;
        SegmentTree st(n);
        rep(i, n) {
                int t;
                cin >> t;
                st.update(i, { 1, t, 1, t}); //初期化。candidateはこの時点ではtである
        }
        int q;
        cin >> q;
        rep(i, q) {
                int l, r;
                cin >> l >> r;
                l --;
                int ant = r - l; //antの総数
                S antfreed = st.query(l, r); //条件を満たす数の個数
                if (antfreed.f) ant -= antfreed.cnt;
                cout << ant << endl;
        }
        return 0;
}