自动搬运

查看原文

来自洛谷，原作者为

	MCRS_lizi 神，不惧死亡！

搬运于2025-08-24 22:43:50，当前版本为作者最后更新于2022-12-11 10:56:45，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

自己给自己出毒瘤题，自己挖的坑花了三四天才填上（悲）

前置知识：二分查找，差分，以及一些STL的的小工具。

题目意思应该讲的还算明白，就直接来讲思路了。

第一个询问很简单，我们只需要二分查找对应区间，再把值代进去计算即可，这里不过多赘述，有问题可以去看代码。

难在第二个询问，由于询问的值最大可能在 $10^9$，并且与函数交点还不一定是个整点，导致处理非常棘手。

这个时候，我们发现，如果函数的值域是一段连续，单调的区间，我们便可以拿出大法宝------差分。只需要在这段的头尾打标记即可。但是 longlong 范围的值域使得正常的差分根本行不通，即使将区间限定在询问对应的区间也不是内存和时间所允许的。

但是这道题目一共就 $2\times 10^5$ 个函数，打的标记数量是十分有限的，意思上如果用朴素的差分，中间会有大量相同且无意义的元素。

这就是说，我们维护的差分数组仅需存储要打标记的点，而其他元素的询问只需要二分查找就可以实现，而这时我们就可以用到一个非常方便的小玩意------ map。

之后就是打标记的问题了。

一次函数很简单，头尾打一下标记就可以了。恶心就在二次函数，我们需要将其按对称轴拆分成两段连续区间打标记，但是二次函数顶点不一定是整点，这就需要一些精密的思考，巧妙的运算，浮点数的熟练应用和恶心至极的分类讨论（这就是困扰我三四天的部分）。

总之大体思路就是这样，具体可以看一下代码和注释，时间复杂度 $O(n\log n)$。

CODE:

#include<bits/stdc++.h>
#define int long long//不开 longlong 见祖宗
using namespace std;
const int N=200010;
const double e=1e-9;//浮点数必备的精度控制
int n,q,val[N<<2],num[N<<2],tot,cnt;
map<int,int> p,used;
struct fun
{
	int l,r,op,a,b,c;
}a[N];
inline int f(register int p,register int x)//求取函数值
{
	if(a[p].op==1)
	{
		return a[p].a*x+a[p].b;
	}
	else
	{
		return a[p].a*x*x+a[p].b*x+a[p].c;
	}
}
inline int query1(register int x)//直接二分查找对应区间
{
	register int l=1,r=n,mid;
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(a[mid].l>=x)
		{
			r=mid-1;
		}
		else if(a[mid].r<x)
		{
			l=mid+1;
		}
		else
		{
			break;
		}
	}
	return f(mid,x);
}
inline void upd(register int x,register int tp)//打标记函数
{
	if(!used[x])
	{
		used[x]=1;
		val[++tot]=x;
	}
	p[x]+=tp;
}
inline void line(register int ll,register int rr,register int x)//给一段连续函数区间打标记的
{
	register int l=f(x,ll),r=f(x,rr);
	if(l>r)
	{
		l--;
		swap(l,r);
	}
	else
	{
		l++;
	}
	upd(l,1),upd(r+1,-1);
}
inline void tag(register int x)//给第x个函数打标记
{
	register int aa=a[x].a,bb=a[x].b,cc=a[x].c;
	if(a[x].op==1)
	{
		line(a[x].l,a[x].r,x);//一次函数直接打
	}
	else
	{
		long double mid=-1.0*bb/(2*aa);//对称轴
		register int top=ceil(a[x].a*mid*mid+a[x].b*mid+a[x].c);//顶点向上取整
		if(mid<=a[x].l||mid-e>a[x].r||bb%(2*aa)==0&&-bb/(2*aa)==a[x].l)//如过对称轴不在区间内，视作一次函数处理。
		{
			line(a[x].l,a[x].r,x);
		}
		else if(top<=f(x,a[x].l)&&aa<0||top>=f(x,a[x].l)&&aa>0)//如果顶点与左端点为同一级别，特殊处理
		{
			if(aa<0)
			{
				upd(f(x,a[x].r),1),upd(top,-1);
			}
			else
			{
				upd(f(x,a[x].r)+1,-1),upd(top,1);
			}
		}
		else
		{
			
			if(aa<0)//开口向下
			{
				int tp=-2;
				if(fabs(a[x].a*mid*mid+a[x].b*mid+a[x].c-(long double)top)<=e)//这个很关键，如果顶点是整点那么交在这里只有一个交点而不是两个
				{
					upd(top+1,-1);
					tp++;
				}
				upd(top,tp),upd(f(x,a[x].l)+1,1),upd(f(x,a[x].r),1);
			}
			else//开口向上
			{
				int tp=2;
				if(fabs(a[x].a*mid*mid+a[x].b*mid+a[x].c-(long double)top)<=e)//和上面一样
				{
					upd(top+1,1);
					tp--;
				}
				upd(top,tp),upd(f(x,a[x].l),-1),upd(f(x,a[x].r)+1,-1);
			}
		}
	}
}
inline int query2(register int x)//求取交点数
{
	return num[upper_bound(val+1,val+tot+2,x)-val-1];//STL真好用
}
signed main()
{
	scanf("%lld%lld",&n,&q);
	for(register int i=1;i<=n;i++)
	{ 
    	scanf("%lld%lld%lld%lld%lld",&a[i].l,&a[i].r,&a[i].op,&a[i].a,&a[i].b);
		if(a[i].op==2)
		{
			scanf("%lld",&a[i].c);
		}
		tag(i);
	}
	sort(val+1,val+tot+1);//排序方便二分
	val[tot+1]=1e18;//这个很关键，不加的话upper_bound有时会找不到结果。
	for(register int i=1;i<=tot;i++)
	{
		num[i]=p[val[i]]+num[i-1];//还原差分数组
	}
	while(q--)
	{
		register int op,x;
		scanf("%lld%lld",&op,&x);
		if(op==1)
		{
			printf("%lld\n",query1(x));
		}
		else
		{
			printf("%lld\n",query2(x));
		}
	}
 	return 0;
}//抄袭题解是不好的习惯哦