样例都没过
查看原帖
样例都没过
467328
BLePb楼主2022/1/20 11:01
#include<bits/stdc++.h>
using std::max;
using std::min;
using std::sort;

#define re register int
#define ls rt<<1
#define rs rt<<1|1
#define mid ((l+r)>>1)
#define int long long
const int N=100004;
int n,q,mi,ma;
struct cal{
	char op;
	int x;
}p[N];
struct dt{
	int x,num,ans;
}a[N];
int maxn[N<<2],minn[N<<2],add[N<<2],mul[N<<2],ad[N<<2],set[N<<2];

bool cmp(dt x,dt y)
{
	return x.x<y.x;
}
bool cmp1(dt x,dt y)
{
	return x.num<y.num;
}
int read()
{
	int x=0,f=1;char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c))
	{
		x=(x<<3)+(x<<1)+c-'0';
		c=getchar();
	}
	return x*f;
}
void pushup(int rt)
{
	maxn[rt]=max(maxn[ls],maxn[rs]);
	minn[rt]=min(minn[ls],minn[rs]);
}
void build(int l,int r,int rt)
{
	if(l==r)
	{
		maxn[rt]=minn[rt]=a[l].x;
		return;
	}
	mul[rt]=1;
	build(l,mid,ls);
	build(mid+1,r,rs);
	pushup(rt);
}
void udp(int rt,int l,int r,int k)
{
	add[rt]+=k;
	maxn[rt]+=k;
	minn[rt]+=k;
}
void udc(int rt,int l,int r,int k)
{
	mul[rt]*=k;
	add[rt]*=k;
	ad[rt]*=k;
	maxn[rt]*=k;
	minn[rt]*=k;
}
void uda(int rt,int l,int r,int k)
{
	minn[rt]+=a[l].num*k;
	maxn[rt]+=a[r].num*k;
	ad[rt]+=k;
}
void uds(int rt,int l,int r,int k)
{
	minn[rt]=maxn[rt]=k;
	mul[rt]=1;
	ad[rt]=add[rt]=0;
	set[rt]=k;
}
void pushdown(int rt,int l,int r)
{
	if(set[rt])
	{
		uds(ls,l,mid,set[rt]);
		uds(rs,mid+1,r,set[rt]);
		set[rt]=0;
	}
	if(mul[rt]>1)
	{
		udc(ls,l,mid,mul[rt]);
		udc(rs,mid+1,r,mul[rt]);
		mul[rt]=1;
	}
	if(add[rt])
	{
		udp(ls,l,mid,add[rt]);
		udp(rs,mid+1,r,add[rt]);
		add[rt]=0;
	}
	if(ad[rt])
	{
		uda(ls,l,mid,ad[rt]);
		uda(rs,mid+1,r,ad[rt]);
		ad[rt]=0;
	}
}
void gmin(int rt,int l,int r)
{
	if(maxn[rt]<mi)
	{
		uds(rt,l,r,mi);
		return ;
	}
	if(l==r) return ;
	pushdown(rt,l,r);
	gmin(ls,l,mid);
	if(minn[rs]<mi) gmin(rs,mid+1,r);
	pushup(rt);
}
void gmax(int rt,int l,int r)
{
	if(minn[rt]>ma)
	{
		uds(rt,l,r,ma);
		return ;
	}
	if(l==r) return ;
	pushdown(rt,l,r);
	gmax(rs,mid+1,r);
	if(maxn[ls]>ma) gmax(ls,l,mid);
	pushup(rt);
}
void gset(int rt,int l,int r)
{
	if(l==r)
	{
		a[l].ans=minn[rt];
		return ;
	}
	pushdown(rt,l,r);
	gset(ls,l,mid);
	gset(rs,mid+1,r);
}
void write(int x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9)
		write(x/10);
	putchar(x%10+'0');
}

signed main()
{
	n=read(),mi=read(),ma=read();
	for(re i=1;i<=n;i++)
		p[i].op=getchar(),p[i].x=read();
	q=read();
	for(re i=1;i<=q;i++)
		a[i].x=read(),a[i].num=i;
	sort(a+1,a+1+q,cmp);
	build(1,q,1);
	for(re i=1;i<=q;i++)
	{
		switch(p[i].op)
		{
			case '+':
				udp(1,1,q,p[i].x);
				break;
			case '-':
				udp(1,1,q,-p[i].x);
				break;
			case '*':
				udc(1,1,q,p[i].x);
				break;
			case '@':
				uda(1,1,q,p[i].x);
				break;
		}
		gmin(1,1,q);
		gmax(1,1,q);
	}
	sort(a+1,a+1+q,cmp1);
	gset(1,1,q);
	for(re i=1;i<=q;i++)
		write(a[i].ans),putchar('\n');
	return 0;
}

蒟蒻已经DEBUG了一个多小时,再DE下去头发会被揪没的......

2022/1/20 11:01
加载中...