P11989 题解

首先难度确定是就是朴素贪心，每个时刻弹出最大值可以做到

\mathcal O(n\log n)

。

但另一种等价的做法就是按

p

从大到小考虑每个怪兽，尽可能向后一直打该怪兽，用并查集维护非空段，时间复杂度

\mathcal O(n)

。

可以猜测难度在

1\sim L

的变化过程中有很多时刻变化量相同，我们生成答案关于难度的函数是

\mathcal O(n)

段的凸壳。

那么我们可以每次二分找到当前段的范围，可以做到

\mathcal O(n^2\log L)

，回答可以双指针

\mathcal O(q+L)

。

但是这无法通过，进一步观察，如果难度

k-1\to k,k\to k+1

变化量相同，那么可以猜测每种怪兽被攻击次数变化量相同，那么每个怪兽被打的次数是一次函数，我们检验的时候只要判断每个后缀中点数是否不超过后缀大小，可以直接计算出最大合法时刻，所以可以

\mathcal O(n)

求出斜率区间。

需要精细实现。

时间复杂度

\mathcal O(n^2+q+L)

。

正解是把答案拆成对每个

k

把权值看成

[p_i\ge k]

求和，变成最大匹配后用 Hall 定理刻画。

代码：

CPP

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
namespace IO {
int ow,olim=(1<<21)-100;
char buf[1<<21],*p1=buf,*p2=buf,obuf[1<<21];
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
ll read() {
	ll x=0; char c=gc();
	while(!isdigit(c)) c=gc();
	while(isdigit(c)) x=x*10+(c^48),c=gc();
	return x;
}
void flush() {
	fwrite(obuf,ow,1,stdout),ow=0;
}
void write(ll x) {
	if(!x) obuf[ow++]='0';
	else {
		int t=ow;
		for(;x;x/=10) obuf[ow++]=(x%10)^48;
		reverse(obuf+t,obuf+ow);
	}
	if(ow>=olim) flush();
}
void putc(char c) {
	obuf[ow++]=c;
	if(ow>=olim) flush();
}
#undef gc
}
const int MAXN=6005,MAXM=1e7+5;
const ll inf=2e18;
struct item {
	ll t,h,w;
}	a[MAXN];
int n,m,q,dsu[MAXN],id[MAXN];
ll f[MAXM],g[MAXN],t[MAXN],h[MAXN];
ull sg[MAXN];
int find(int x) { return dsu[x]^x?dsu[x]=find(dsu[x]):x; }
int qry(int x) {
	int y=x>>6,r=x&63;
	if(sg[y]>>r) return __builtin_ctzll(sg[y]>>r)+x;
	y=find(y+1);
	return y<<6|__builtin_ctzll(sg[y]);
}
void sol(ll k) {
	int b=(n>>6)+1;
	for(int i=0;i<=b;++i) dsu[i]=i,sg[i]=-1;
	for(int i=1;i<=n;++i) g[i]=a[i+1].t-a[i].t;
	for(int o=1,i;o<=n;++o) {
		ll c=a[i=id[o]].h*k;
		for(int x=qry(i),y;x<=n&&c;) {
			if(c>=g[x]) {
				c-=g[x],g[x]=0,sg[y=(x>>6)]^=1ll<<(x&63);
				if(!sg[y]) dsu[y]=y+1;
				x=qry(x);
			}
			else g[x]-=c,c=0;
		}
		h[i]=a[i].h*k-c;
	}
}
signed main() {
	n=IO::read(),m=IO::read(),a[n+1].t=IO::read();
	ll S=0;
	for(int i=1;i<=n;++i) a[i].t=IO::read(),a[i].h=IO::read(),a[i].w=IO::read(),S+=a[i].h*a[i].w,id[i]=i;
	sort(a+1,a+n+1,[&](auto x,auto y) { return x.t<y.t; });
	sort(id+1,id+n+1,[&](int x,int y){ return a[x].w>a[y].w; });
	for(int p=1;p<=m;) {
		sol(p),f[p]=0;
		for(int i=1;i<=n;++i) f[p]+=h[i]*a[i].w;
		ll k=0,b=0,x=m-p,y=1;
		auto upd=[&](ll u,ll v) { if((__int128)u*y<(__int128)x*v) x=u,y=v; };
		for(int i=n;i>=1;--i) {
			b+=a[i+1].t-a[i].t;
			k+=h[i]-t[i],b-=h[i];
			if(k>0) upd(b,k);
			if(h[i]-t[i]>a[i].h) upd(a[i].h*p-h[i],h[i]-t[i]-a[i].h);
			else if(h[i]-t[i]<0) upd(h[i],t[i]-h[i]);
			if(x<y) break;
		}
		ll d=x/y;
		for(int i=p+1;i<=p+d;++i) f[i]=f[i-1]+f[p]-f[p-1];
		for(int i=1;i<=n;++i) t[i]=h[i]+d*(h[i]-t[i]);
		p+=d+1;
	}
	f[m+1]=inf;
	for(int i=m;~i;--i) f[i]=min(f[i+1],S*i-f[i]);
	q=IO::read();
	for(int i=0;q--;) {
		ll z=IO::read();
		while(i<m&&f[i+1]<=z) ++i;
		IO::write(i),IO::putc('\n');
	}
	IO::flush();
	return 0;
}

文章操作

相关推荐

评论

P11989 题解