Four-Russian 模板

Aaron_Romeo · 2025-03-03 19:43:27 · 算法·理论

namespace frs
{
    template<typename T, T calc(T, T)>
    class Four_Russian
    {
        private :
        int N, B;
        std :: vector<T> a;
        std :: vector<std :: vector<T>> ans, pre, suf;
        public :
        void init(int n)
        {
            N = n - 1, B = std :: sqrt(n);
            a = std :: vector<T>(N + 1);
            ans = std :: vector<std :: vector<T>>(N / B + 1, std :: vector<T>(N / B + 1));
            pre = suf = std :: vector<std :: vector<T>>(N / B + 1, std :: vector<T>(B + 1));
        }
        T & operator [] (const int &x) {return a[x - 1];}
        void build()
        {
            for (int i = 0; i <= N / B; i ++ )
            {
                int up = std :: min(B - 1, N - i * B);
                pre[i][0] = a[i * B]; for (int j = 1; j <= up; j ++ ) pre[i][j] = calc(pre[i][j - 1], a[i * B + j]);
                suf[i][up] = a[i * B + up]; for (int j = up - 1; j >= 0; j -- ) suf[i][j] = calc(a[i * B + j], suf[i][j + 1]);
                ans[i][i] = pre[i][up];
            }
            for (int i = 0; i <= N / B; i ++ )
                for (int j = i + 1; j <= N / B; j ++ )
                    ans[i][j] = calc(ans[i][j - 1], ans[j][j]);
        }
        T query(int l, int r)
        {
            assert(l <= r);
            int x = -- l / B, y = -- r / B;
            if (x == y) {T res = a[l]; for (int i = l + 1; i <= r; i ++ ) res = calc(res, a[i]); return res;}
            T res = suf[x][l - x * B]; if (y - x > 1) res = calc(res, ans[x + 1][y - 1]); res = calc(res, pre[y][r - y * B]);
            return res;
        }
    };
}