B题题解

· · 题解

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

前置知识：二分查找，差分，以及一些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;
}//抄袭题解是不好的习惯哦