Learning Algorithms

アルゴリズムの勉強メモ

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。なにが間違っているのかに気づいてから、実装まではかなり時間がかかった。。。しかもかなり冗長な実装になっていると思う。。。

まずセグメント木をつくる。割と何も考えずに実装している感もあるが、4つの状態変数を持たせて実装した。具体的には、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;
}