网站前端培训,wordpress优化数据库缓存,良乡网站建设,网站地图在线生成器传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
实现以下两个操作#xff1a; (1)(1)(1)在平面上加入一条线段。记第iii条被插入的线段的标号为iii (2)(2)(2)给定一个数kkk#xff0c;询问与直线xkxkxk相交的线段中#xff0c;交点纵坐标最大的线段的编…传送门
文章目录题意思路题意
实现以下两个操作 (1)(1)(1)在平面上加入一条线段。记第iii条被插入的线段的标号为iii (2)(2)(2)给定一个数kkk询问与直线xkxkxk相交的线段中交点纵坐标最大的线段的编号。 n≤1e5,k,x0,x1≤39989,1≤y0,y1≤1e9n\le 1e5,k,x_0,x_1\le39989,1\le y_0,y_1 \le 1e9n≤1e5,k,x0,x1≤39989,1≤y0,y1≤1e9。
思路
复习一下李超线段树。 李超树是用来维护一次函数将线段划分为若干个段即线段树的每一个段都维护一个最优线他在当前段的midmidmid处的位置是最大值我注意李超树线段不能向上pushuppushuppushup。当然我们如果要查询区间最小值或者最大值怎么办呢我们总不能从[x1,x2][x_1,x_2][x1,x2]跑一遍每个点都查询一遍吧这样显然是不科学的我们可以发现一次函数是个单调函数我们在插入的时候顺便维护以下最小值就好了最小值一定在当前区间的端点处。
下面我们考虑这个题这个题不是维护单点最大值是多少而是问最大值的线段编号我们只需要再加一个变量维护以下编号即可注意修改一下查询函数以及判断当前区间是否存在最优段。
//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e9,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
struct Node {int l,r,flag,id; double k,b;double calc(const int pos) const {return k*posb;}int cross(const Node x) const {return floor((b-x.b)/(x.k-k));}
}tr[N2];
struct Query {int id;double val;
};void build(int u,int l,int r) {tr[u]{l,r,0,0,0,0};if(lr) return;int mid(lr)1;build(L,l,mid); build(R,mid1,r);
}void modify(int u,int l,int r,Node k) {if(k.llk.rr) {if(!tr[u].flag) { tr[u]k; }else if(k.calc(l)-tr[u].calc(l)epsk.calc(r)-tr[u].calc(r)eps) tr[u]k; else if(k.calc(l)-tr[u].calc(l)eps||k.calc(r)-tr[u].calc(r)eps) {int mid(lr)1;if(k.calc(mid)-tr[u].calc(mid)eps) swap(tr[u],k);else if(fabs(k.calc(mid)-tr[u].calc(mid))eps) {if(tr[u].idk.id) swap(tr[u],k);}if(k.cross(tr[u])-mid-eps) modify(L,l,mid,k);else modify(R,mid1,r,k);}}else {int mid(lr)1;if(k.lmid) modify(L,l,mid,k);if(k.rmid) modify(R,mid1,r,k);}
}Query query(int u,int l,int r,int x,int flag) {//if(!tr[u].flag) return {0,0}; if(lr) return {tr[u].id,tr[u].calc(x)};int mid(lr)1;double anstr[u].calc(x);int idtr[u].id;if(xmid) {Query cmpquery(L,l,mid,x,flag);if(cmp.id0) return {id,ans};if(anscmp.val) return {id,ans};else if(anscmp.val) return {min(id,cmp.id),ans};else return cmp; }else {Query cmpquery(R,mid1,r,x,flag);if(cmp.id0) return {id,ans};if(anscmp.val) return {id,ans};else if(anscmp.val) return {min(id,cmp.id),ans};else return cmp; }
}/*
double query(int u,int l,int r,int x) {//if(l1r1) printf(%.2f %.2f\n,tr[u].k,tr[u].b);if(lr) return tr[u].calc(x);int mid(lr)1;double anstr[u].calc(x);if(xmid) return max(ans,query(L,l,mid,x));else return max(ans,query(R,mid1,r,x));
}
*/int main() {
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d,n);build(1,1,50000);int ans0,id0;while(n--) {int op; scanf(%d,op);if(op0) {int x; scanf(%d,x);x(xans-1)%399891;Query nowquery(1,1,50000,x,1);printf(%d\n,ansnow.id);}else {id;int x1,x2,y1,y2;scanf(%d%d%d%d,x1,y1,x2,y2);x1(x1ans-1)%399891; x2(x2ans-1)%399891;y1(y1ans-1)%mod1; y2(y2ans-1)%mod1;if(x1x2) swap(x1,x2),swap(y1,y2);if(x1x2) modify(1,1,50000,{x1,x2,1,id,0,(double)max(y1,y2)});else {double kdouble(y1-y2)/(x1-x2);double by1-k*x1;modify(1,1,50000,{x1,x2,1,id,k,b});}}}return 0;
}
/**/
