题解：P5579 [PA 2015] Siano

401rk8 · 2025-08-08 18:52:26 · 题解

线性做法

先观察一下：

• 不妨按 a_i 从小到大排序
• 高度始终是单增的，每次收割一段后缀

到这里可以用线段树二分做到 \log

• 对于这次要割的草（b_0+a_i(d-d_0)\ge b），设上次被割的时间 d_0、高度 b_0，这次会被割 a_i(d-d_0)+(b_0-b)。d_0,b_0 相同时只需知道 \sum a_i,\sum a_i^0 就能合并计算

用栈维护 (a,d_0,b_0)，记 a_1 为栈中下一个 a，表示上次被割时间 d_0、高度 b_0 的草满足 a\le a_i<a_1，容易在值域上前缀和求出对应的 \sum a_i,\sum a_i^0

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx;
typedef long long LL;
#define int LL
#define For(i,x,y,...) for(int i=(x),##__VA_ARGS__;i<=(y);++i)
#define rFor(i,x,y,...) for(int i=(x),##__VA_ARGS__;i>=(y);--i)
#define Rep(i,x,y,...) for(int i=(x),##__VA_ARGS__;i<(y);++i)
#define pb emplace_back
#define sz(a) int((a).size())
#define all(a) (a).begin(),(a).end()
#define mem(a,x,n) memset(a,x,sizeof(*a)*((n)+2))
typedef vector<int> Vi;
auto ckmax=[](auto &x,auto y) { return x<y ? x=y,true : false; };
auto ckmin=[](auto &x,auto y) { return y<x ? x=y,true : false; };
template<typename T=int>T read() { T x; cin>>x; return x; }
sfmt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r) { return uniform_int_distribution<LL>(l,r)(mt); }

const int mod = 998244353;
struct mint {
    int x; mint(int x=0):x(x<0?x+mod:x<mod?x:x-mod){}
    mint& operator += (const mint &y) { x=x+y.x<mod?x+y.x:x+y.x-mod; return *this; }
    mint& operator -= (const mint &y) { x=x<y.x?x-y.x+mod:x-y.x; return *this; }
    mint& operator *= (const mint &y) { x=x*y.x%mod; return *this; }
    friend mint operator + (mint x,const mint &y) { return x+=y; }
    friend mint operator - (mint x,const mint &y) { return x-=y; }
    friend mint operator * (mint x,const mint &y) { return x*=y; }
    friend mint operator ^ (mint x,int y) { mint z=1;for(;y;y>>=1,x*=x)if(y&1)z*=x;return z; }
};  mint inv(mint x) { return x ^ mod-2; }

const int N = 1e6+9;
int n,m,cnt[N],sum[N];

void MAIN() {
    cin>>n>>m; For(i,1,n) ++cnt[read()];
    rFor(i,1e6,1) sum[i] = sum[i+1] + i * cnt[i], cnt[i] += cnt[i+1];
    vector<tuple<int,int,int>> stk; stk.pb(1,0,0);
    while( m-- ) {
        int d,b; cin>>d>>b;
        int ans = 0;
        for(int a1 = 1e6+1; ; ) {
            if( stk.empty() ) { stk.pb(1,d,b); break; }
            auto [a,d0,b0] = stk.back();
            if( b0+a*(d-d0) >= b ) { // 整个区间都被割
                ans += (sum[a]-sum[a1]) * (d-d0) + (b0-b) * (cnt[a]-cnt[a1]);
                a1 = a;
                stk.pop_back();
                continue;
            }
            a = (b-b0) / (d-d0) + 1; // >= a 的会被割
            ans += (sum[a]-sum[a1]) * (d-d0) + (b0-b) * (cnt[a]-cnt[a1]);
            stk.pb(a,d,b);
            break;
        }
        cout<<ans<<'\n';
        // for(auto [a,d,b] : stk) cerr<<a<<" "<<d<<" "<<b<<'\n'; cerr<<"---\n";
    }
} signed main() {
#ifdef FS
    freopen("in","r",stdin); freopen("out","w",stdout);
#endif
    ios::sync_with_stdio(0);cin.tie(0);
    int lft=1; while( lft-- ) {
        MAIN();
    }
    return 0;
}