题解 CF1942F【Farmer John's Favorite Function】

萌萌 F 题，上大分。

首先，如下定义 \(g(i)\)：

• \(g(1)=\lfloor\sqrt{a_1}\rfloor\)；
• 对于所有 \(i > 1\)，\(g(i)=\lfloor\sqrt{g(i-1)+a_i}\rfloor\)。

也就是将 \(f(i)\) 的每一步运算后都向下取整。注意到 \(\lfloor f(i)\rfloor=g(i)\) 恒成立，于是我们只需要转而求每次修改后 \(g(n)\) 的值，避免了浮点数运算。

将询问离线，对时间轴（操作序列）维护数据结构，按空间轴（序列 \(a_i\)）下标从小到大扫描线。每扫描到一个新的下标 \(i\)，需要做的操作是将每个时刻的 \(g\) 加上对应时刻修改后的 \(a_i\)，然后将每个时刻的 \(g\) 开根号下取整。因此，数据结构需要支持 \(n+q\) 次区间加操作和 \(n\) 次全局开根号下取整操作，并在最后输出每个位置的值。

可以使用势能线段树维护：每个节点维护区间最小值、最大值、区间加法标记。区间加操作是平凡的，全局开根号下取整操作直接暴力递归，直到 \(mx-mn=\lfloor\sqrt{mx}\rfloor-\lfloor\sqrt{mn}\rfloor\)，此时打区间加法标记即可。也可以使用分块等维护。

// Problem: F. Farmer John's Favorite Function
// Contest: Codeforces - CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!)
// URL: https://codeforces.com/contest/1942/problem/F
// Memory Limit: 256 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

template<int mod>
inline unsigned int down(unsigned int x) {
	return x >= mod ? x - mod : x;
}

template<int mod>
struct Modint {
	unsigned int x;
	Modint() = default;
	Modint(unsigned int x) : x(x) {}
	friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
	friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
	friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
	friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
	friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
	friend Modint operator/(Modint a, Modint b) {return a * ~b;}
	friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
	friend Modint operator~(Modint a) {return a ^ (mod - 2);}
	friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
	friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
	friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
	friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
	friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
	friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
	friend Modint& operator++(Modint& a) {return a += 1;}
	friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
	friend Modint& operator--(Modint& a) {return a -= 1;}
	friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
	friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
	friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};

const ll N = 2e5 + 5;

ll n, m, a[N], qk[N], qx[N];
vector<tuple<ll, ll>> qs[N];

inline ll mysqrt(ll x) {
    ll k = sqrtl(x);
    while(k * k > x) --k;
    while((k + 1) * (k + 1) <= x) ++k;
    return k;
}

struct SegTree {
    ll mx[N << 2], mn[N << 2], tag[N << 2];
    #define lc(u) (u << 1)
    #define rc(u) (u << 1 | 1)
    void pushup(ll u) {
        mx[u] = max(mx[lc(u)], mx[rc(u)]);
        mn[u] = min(mn[lc(u)], mn[rc(u)]);
    }
    void pushdown(ll u) {
        tag[lc(u)] += tag[u];
        tag[rc(u)] += tag[u];
        mx[lc(u)] += tag[u];
        mx[rc(u)] += tag[u];
        mn[lc(u)] += tag[u];
        mn[rc(u)] += tag[u];
        tag[u] = 0;
    }
    void rangeadd(ll u, ll l, ll r, ll ql, ll qr, ll k) {
        if(ql > qr) return;
        if(ql <= l && r <= qr) {
            tag[u] += k;
            mx[u] += k;
            mn[u] += k;
            return;
        }
        pushdown(u);
        ll mid = (l + r) >> 1;
        if(ql <= mid) rangeadd(lc(u), l, mid, ql, qr, k);
        if(qr > mid) rangeadd(rc(u), mid + 1, r, ql, qr, k);
        pushup(u);
    }
    void rangesqrt(ll u, ll l, ll r, ll ql, ll qr) {
        if(ql > qr) return;
        if(l == r) {
            mx[u] = mn[u] = mysqrt(mx[u]);
            return;
        }
        if(ql <= l && r <= qr && mx[u] - mn[u] == mysqrt(mx[u]) - mysqrt(mn[u])) {
            ll diff = mysqrt(mx[u]) - mx[u];
            tag[u] += diff;
            mx[u] += diff;
            mn[u] += diff;
            return;
        }
        pushdown(u);
        ll mid = (l + r) >> 1;
        if(ql <= mid) rangesqrt(lc(u), l, mid, ql, qr);
        if(qr > mid) rangesqrt(rc(u), mid + 1, r, ql, qr);
        pushup(u);
    }
    void print(ll u, ll l, ll r, char ENDPRINT = '\n') {
        if(l == r) {
            cout << mx[u] << ENDPRINT;
            return;
        }
        pushdown(u);
        ll mid = (l + r) >> 1;
        print(lc(u), l, mid, ENDPRINT);
        print(rc(u), mid + 1, r, ENDPRINT);
        pushup(u);
    }
    #undef lc
    #undef rc
}sgt;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, m) cin >> qk[i] >> qx[i];
    rep(i, 1, m) qs[qk[i]].emplace_back(qx[i], i);
    rep(i, 1, n) {
        ll lstval = a[i], lstkey = 1;
        for(auto [val, key] : qs[i]) {
            sgt.rangeadd(1, 1, m, lstkey, key - 1, lstval);
            lstval = val;
            lstkey = key;
        }
        sgt.rangeadd(1, 1, m, lstkey, m, lstval);
        // sgt.print(1, 1, m, ' '); cout << endl;
        sgt.rangesqrt(1, 1, m, 1, m);
        // sgt.print(1, 1, m, ' '); cout << endl;
    }
    sgt.print(1, 1, m);
    return 0;
}