自动搬运

查看原文

来自洛谷，原作者为

	chrhaa THE DEFECT SLAYS THE SPIRE

搬运于2025-08-24 22:55:39，当前版本为作者最后更新于2024-02-27 09:29:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

数据结构题

考虑到 $b$ 的数据范围极大，先离散化。

因为贡献是 $3^{a-1}$，所以一定测试用例越平均越好（感性理解）。发现约束条件是针对前缀的，那么有一个显然的贪心，即在平均分布的情况下，测试用例多的日子尽量靠前。

定每天准备 $a_i$ 个测试用例，那么有 $a_i \geq a_{i+1}$，画成条状图，就是一个向左上延伸的台阶。对于第 $i$ 个要求，若当前状态尚未满足，则一定要增加 $m_i$ 前的 $a_i$ 值，由于特殊的贡献方式，更新$a_i$值时一定要先增加较小的 $a_i$，形象一点说，就是往这个台阶里倒水。而增加了前面的 $a_i$，后面就可以去掉若干，同理是把台阶从上至下切掉一部分。

区间赋值，区间和查询，最长值相等区间长度，即可用线段树维护，以下是一份丑陋的代码。

#include<stdio.h>
const int N=200005;
const int M=4000005;
const int K=1000000;

#define ll long long
const ll P=1000000007;

inline ll Q(ll x,ll y=P-2,ll z=1){
	for(;y;y>>=1,x=x*x%P)
	(y&1)&&(z=z*x%P);return z;
}

bool t[M];
int lb[M],rb[M];
ll lf[M],rf[M];
ll sm[M],lz[M];

#define ls (x<<1)
#define rs (x<<1|1)

inline void tag(int x,int l,int r,ll v){
	sm[x]=(r-l+1)*v;
	lb[x]=rb[x]=r-l+1;
	lf[x]=rf[x]=v;
	lz[x]=v;
}

inline void pushdown(int x,int l,int r){
	if(lz[x]>=0){
		int mid=(l+r)>>1;
		tag(ls,l,mid,lz[x]);
		tag(rs,mid+1,r,lz[x]);
		lz[x]=-1;
	}
}

inline void pushup(int x,int l,int r){
	sm[x]=sm[ls]+sm[rs];
	lf[x]=lf[ls];
	rf[x]=rf[rs];
	lb[x]=(t[ls]&&rf[ls]==lf[rs])?(lb[ls]+lb[rs]):lb[ls];
	rb[x]=(t[rs]&&rf[ls]==lf[rs])?(rb[rs]+rb[ls]):rb[rs];
	t[x]=(lb[x]==r-l+1);
}

void build(int x,int l,int r){
	sm[x]=0;
	lz[x]=-1;
	lb[x]=rb[x]=r-l+1;
	lf[x]=rf[x]=0;
	t[x]=1;
	
	if(l<r){
		int mid=(l+r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
	}
}

void update(int x,int l,int r,int L,int R,ll v){
	if(L>R||r<L||l>R) return ;
	if(L<=l&&r<=R){
		tag(x,l,r,v);
		return ;
	}
	
	int mid=(l+r)>>1;
	pushdown(x,l,r);
	update(ls,l,mid,L,R,v);
	update(rs,mid+1,r,L,R,v);
	pushup(x,l,r);
}

ll query(int x,int l,int r,int L,int R){
	if(L>R||r<L||l>R) return 0;
	if(L<=l&&r<=R) return sm[x];
	
	int mid=(l+r)>>1;
	pushdown(x,l,r);
	return query(ls,l,mid,L,R)+query(rs,mid+1,r,L,R); 
}

int queryl(int x,int l,int r,int p){
	if(l==r)
	return 1;
	
	int mid=(l+r)>>1;
	pushdown(x,l,r);
	
	if(p<=mid) return queryl(ls,l,mid,p);
	else{
		int res=queryl(rs,mid+1,r,p);
		
		if(res==p-mid&&rf[ls]==lf[rs])
		return res+rb[ls];
		else return res;
	}
}

int queryr(int x,int l,int r,int p){
	if(l==r)
	return 1;
	
	int mid=(l+r)>>1;
	pushdown(x,l,r);
	
	if(p<=mid){
		int res=queryr(ls,l,mid,p);
		
		if(res==mid-p+1&&rf[ls]==lf[rs])
		return res+lb[rs];
		else return res;
	}else return queryr(rs,mid+1,r,p);
}

int n,m;
ll ans,a,b,c,tmp;

void calc(int x,ll y,ll f)
{(y>0)&&(ans=(ans+P+Q(3,y-1)*f*(ll)x%P)%P);}

signed main(){
	int i,x,p,y;
	scanf("%d",&n);
	build(1,1,K);
	
	for(i=1;i<=n;i++){
		scanf("%d%lld",&m,&b);
		a=query(1,1,K,m,m);
		b-=query(1,1,K,1,m);
		p=m;
		
		if(b<=0)
		goto END;
		
		tmp=b;
		
		while(b>0&&p>0){
			x=queryl(1,1,K,p);
			p-=x;
			x=m-p;
			calc(x,a,-1);
			y=int(b%(ll)x);
			
			if(p>0){
				c=query(1,1,K,p,p);
				
				if((c-a)*(ll)x<b){
					b-=(c-a)*(ll)x;
					calc(x,c,1);
					a=c;
				}else{
					a+=b/(ll)x;
					calc(y,a+1,1);
					update(1,1,K,p+1,p+y,a+1);
					calc(x-y,a,1);
					update(1,1,K,p+y+1,p+x,a);
					b=0;
				}
			}else{
				a+=b/(ll)x;
				calc(y,a+1,1);
				update(1,1,K,1,y,a+1);
				calc(x-y,a,1);
				update(1,1,K,y+1,x,a);
			}
		}
		
		b=tmp;
		p=m+1;
		
		if(p<=K)
		a=query(1,1,K,p,p);
		
		while(b>0&&p<=K){
			x=queryr(1,1,K,p);
			p+=x;
			x=p-m-1;
			calc(x,a,-1);
			y=int(b%(ll)x);
			
			if(p<=K){
				c=query(1,1,K,p,p);
				
				if((a-c)*(ll)x<b){
					b-=(a-c)*(ll)x;
					calc(x,c,1);
					a=c;
				}else{
					a-=b/(ll)x;
					calc(y,a-1,1);
					update(1,1,K,p-y,p-1,a-1);
					calc(x-y,a,1);
					update(1,1,K,p-x,p-y-1,a);
					b=0;
				}
			}else if(a*(ll)x>=b){
				a-=b/(ll)x;
				calc(y,a-1,1);
				update(1,1,K,p-y,p-1,a-1);
				calc(x-y,a,1);
				update(1,1,K,p-x,p-y-1,a);
			}else update(1,1,K,m+1,K,0);
		}
		
		END:;
		printf("%lld\n",ans);
	}return 0;
}