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

题意

有一个分成

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)|

即可。

CPP

#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;
}

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

文章操作

题意

题解

相关推荐

评论

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