题解：P8929 「TERRA-OI R1」别得意，小子

66xyyd · 2025-10-27 10:00:16 · 题解

题意

有一个分成 n 段的函数，每一段可能是一次函数或二次函数。有 q 次询问，每次询问类型有：询问 x=k 时函数取值；询问直线 y=k 与整段函数的交点个数。

题解

写这道题非常能锻炼二分实现的能力。

一个比较显然的想法是分开处理两类查询。首先我们可以通过二分找到 x=k 时对应到哪个函数从而求值。然后我们可以预处理出来若干 L_i,R_i,ans_i，表示在 L_i<k \le R_i 时第二类查询的答案为 ans_i。这样枚举每一段函数，计算对总答案的贡献即可。

但是直接做需要大量的分类讨论。怎么办呢？我们发现可以把分段函数进一步分割成若干单调区间，单调区间对答案的贡献非常好计算，就是一个区间加一。分类讨论如下（以下区间指的是值域上的区间）：

一次函数，设左右函数值为 f(l),f(r)，如果 b>0，分成区间 (f(l),f(r)]，否则分成区间 [f(r),f(l))。
二次函数，设左右函数值为 f(l),f(r)，顶点坐标为 (m_x,m_y)。讨论顶点是否取得到。如果 l<m_x \le r，就分成两个区间考虑，否则就是分成一个区间。如果分成两个区间，且 a>0，分成的区间是 [m_y,f(l)) 和 (m_y,f(r)]；a<0 分成的区间是 (f(l),m_y] 和 [f(r),m_y)。如果分成一个区间，且 f(l)<f(r)，分成的区间是 (f(l),f(r)]，否则是 [f(r),f(l))。

到这一步就可以把分出来的区间差分算贡献了。我的做法是：分成下界 v_1 和上界 v_2，每次查询时计算 |v_1(\le k)|-|v_2(<k)| 即可。

#include<iostream>
#include<vector>
#include<set>
#include<climits>
#include<algorithm>
using namespace std;
struct node{
    long long a,b,c;
    double l,r;//覆盖区间(l,r]
}a[2000001];
int acnt;
constexpr long double eps=1e-8;
vector<pair<pair<double,double>,int>> v;
int n,q;
//second=-1 取得到 1 取不到
pair<long double,int> v1[2000001],v2[2000001];//v1为下界 v2为上界
int cnt1,cnt2;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for(int i=1;i<=n;i++){
        int l,r,op;
        cin >> l >> r >> op;
        if(op==1){
            long long b,c;
            cin >> b >> c;
            a[++acnt]=node({0,b,c,l+0.0,r+0.0});
            if(b>0){
                v1[++cnt1]={b*l+c,1};
                v2[++cnt2]={b*r+c,-1};
            } else{
                v1[++cnt1]={b*r+c,-1};
                v2[++cnt2]={b*l+c,1};
            }

        } else{
            long long a,b,c;
            cin >> a >> b >> c;
            double mx=-b/(2.0l*a);
            long double my=c-((long double)(b)*b)/(4.0l*a);
            long double ml=((long double)(a)*l+b)*l+c,mr=((long double)(a)*r+b)*r+c;
            if(l<=mx && mx<=r){
                ::a[++acnt]=node({a,b,c,l+0.0,mx});
                ::a[++acnt]=node({a,b,c,mx,r+0.0});
                if(a>0){
                    v1[++cnt1]={my,-1};
                    v1[++cnt1]={my,1};
                    v2[++cnt2]={ml,1};
                    v2[++cnt2]={mr,-1};
                } else{
                    v2[++cnt2]={my,-1};
                    v2[++cnt2]={my,1};
                    v1[++cnt1]={ml,1};
                    v1[++cnt1]={mr,-1};
                }
            } else{
                ::a[++acnt]=node({a,b,c,l+0.0,r+0.0});
                if(ml<mr){
                    //(ml,mr]
                    v1[++cnt1]={ml,1};
                    v2[++cnt2]={mr,-1};
                } else{
                    //[mr,ml)
                    v1[++cnt1]={mr,-1};
                    v2[++cnt2]={ml,1};
                }
            }
        }
    }
    for(int i=1;i<=acnt;i++){
        v.push_back(make_pair(make_pair(a[i].l,a[i].r),i));
    }
    for(int i=1;i<=cnt2;i++){
        v2[i].second=-v2[i].second;
    }
    sort(v1+1,v1+cnt1+1);
    sort(v2+1,v2+cnt2+1);
    while(q--){
        int op;
        long long k;
        cin >> op >> k;
        if(op==1){
            int i=(--lower_bound(v.begin(),v.end(),make_pair(make_pair(k+0.0,0.0),INT_MAX)))->second;
            cout << (a[i].a*k+a[i].b)*k+a[i].c << '\n';
        } else{
            int li=((upper_bound(v1+1,v1+cnt1+1,make_pair(k+0.0l,0)))-v1);
            int ri=((lower_bound(v2+1,v2+cnt2+1,make_pair(k+0.0l,0)))-v2);
            //下界小于等于k的 - 上界小于k的
            cout << li-ri << '\n';
        }
    }
    return 0;
}