线性做法

先观察一下：

不妨按 $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$ 就能合并计算
$d_0,b_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

CPP

#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;
}

题解：P5579 [PA 2015] Siano

文章操作

线性做法

相关推荐

评论

题解：P5579 [PA 2015] Siano