一、题目
校长有一个体积为 \(x\) 的大套子,现在有 \(n\) 条人类,如果套子的体积严格大于人类的体积 \(y\),那么校长就会把这个人类装在套子里,套子的体积就会增加 \(y\)
有下列三种可能的时间:
- 校长得到了一个大小为 \(x\) 的套子,他想让套子的大小至少变成 \(y\),如果可以输出步数,否则输出 \(-1\)
- 新来了一条体积为 \(y\) 的人类
- 离开了一条体积为 \(y\) 的人类
\(n\leq 3\cdot 10^5,q\leq 10^5\)
二、解法
贪心的做法是每次套能套的最大人类,但暴力进行此过程显然会 \(\tt T\)
这个东西也不是很好维护,所以要想一些在线的做法,我们想要让套的次数是 \(\tt log\) 级的,所以我们一次套多点呗。具体来说我们套到能套一个更大的人类为止,那么这样做两次可以让套子大小翻倍。
对于所有小于 \(x\) 的人类,我们把它们都放在权值线段树上,每次在线段树上二分一段后缀即可,时间复杂度 \(O(n\log^2n)\)
难点是实现细节,二分的时候如果我们要套人类,直接把这个节点的信息清零,以后不访问信息被清零的节点即可(不需要打标记),但是因为询问独立所以我们要回退,拿个栈记录一下我们所有在线段树上的修改即可。
三、总结
对于这类在线处理的增量型问题,考虑怎样才能只做 \(\log n\) 次。
#pragma GCC optimize(2)
#include <cstdio>
#include <stack>
#include <map>
using namespace std;
#define ll long long
#define int long long
const int N = 13000005;
const ll up = 1e12;
ll read()
{
ll x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
ll n,m,sum[N],num[N];int rt,ls[N],rs[N],fa[N];
ll cnt,ans,x,y,rm;map<ll,ll> mp;
struct node{ll x,y,z;};stack<node> bk;
void upload(int x)
{
sum[x]=sum[ls[x]]+sum[rs[x]];
num[x]=num[ls[x]]+num[rs[x]];
fa[ls[x]]=fa[rs[x]]=x;
}
void ins(int &x,ll l,ll r,ll id,ll f)
{
if(!x) x=++cnt;
num[x]+=f;
sum[x]+=f*id;
if(l==r) return ;
ll mid=(l+r)>>1;
if(mid>=id) ins(ls[x],l,mid,id,f);
else ins(rs[x],mid+1,r,id,f);
}
void add(int &i,ll l,ll r)
{
if(l>=x || !sum[i] || !i || rm<=0) return ;
if(l==r)
{
ll tmp=min((rm+l-1)/l,num[i]);
rm-=tmp*l;x+=tmp*l;ans+=tmp;
bk.push(node{i,sum[i],num[i]});
sum[i]-=tmp*l;num[i]-=tmp;
return ;
}
ll mid=(l+r)>>1;
if(r<=x && sum[i]<=rm)
{
rm-=sum[i];x+=sum[i];ans+=num[i];
bk.push(node{i,sum[i],num[i]});
sum[i]=num[i]=0;
return ;
}
add(rs[i],mid+1,r);
add(ls[i],l,mid);
upload(i);
}
void work()
{
ans=0;
while(x<y)
{
map<ll,ll>::iterator it=mp.lower_bound(x);
ll to=y-1;
if(it!=mp.end()) to=min(to,it->first);
rm=to-x+1;
add(rt,1,up);
if(rm>0) break;
}
while(!bk.empty())
{
ll t=bk.top().x;
sum[t]=bk.top().y;
num[t]=bk.top().z;
while(t!=rt)
{
t=fa[t];
upload(t);
}
bk.pop();
}
if(x<y) puts("-1");
else printf("%lld\n",ans);
}
signed main()
{
freopen("fish.in","r",stdin);
freopen("fish.out","w",stdout);
n=read();
for(ll i=1;i<=n;i++)
{
ll x=read();mp[x]++;
ins(rt,1,up,x,1);
}
m=read();
while(m--)
{
ll op=read();x=read();
if(op==2)
{
mp[x]++;
ins(rt,1,up,x,1);
}
if(op==3)
{
mp[x]--;
if(!mp[x]) mp.erase(x);
ins(rt,1,up,x,-1);
}
if(op==1)
{
y=read();work();
}
}
}