广州个性化网站建设,门户网站建设工作方案,python语言是什么,wordpress网站如何引流问题 D: [Heoi2013]Segment 时间限制: 4 Sec 内存限制: 256 MB 题目描述 要求在平面直角坐标系下维护两个操作#xff1a; 1.在平面上加入一条线段。记第i条被插入的线段的标号为i。 2.给定一个数k,询问与直线 x k相交的线段中#xff0c;交点最靠上的线段的编号。 输… 问题 D: [Heoi2013]Segment 时间限制: 4 Sec 内存限制: 256 MB 题目描述 要求在平面直角坐标系下维护两个操作 1.在平面上加入一条线段。记第i条被插入的线段的标号为i。 2.给定一个数k,询问与直线 x k相交的线段中交点最靠上的线段的编号。 输入 第一行一个整数n表示共n 个操作。 接下来n行每行第一个数为0或1。 若该数为 0则后面跟着一个正整数 k表示询问与直线 x ((k lastans–1)%399891)相交的线段中交点包括在端点相交的情形最靠上的线段的编号其中%表示取余。若某条线段为直线的一部分则视作直线与线段交于该线段y坐标最大处。若有多条线段符合要求输出编号最小的线段的编号。 若该数为 1则后面跟着四个正整数 x0, y0, x 1, y 1表示插入一条两个端点为 ((x0lastans-1)%399891,(y0lastans-1)%10^91)和((x 1lastans-1)%399891,(y1lastans-1)%10^91) 的线段。 其中lastans为上一次询问的答案。初始时lastans0。 输出 对于每个 0操作输出一行包含一个正整数表示交点最靠上的线段的编号。若不存在与直线相交的线段答案为0。 样例输入 6 1 8 5 10 8 1 6 7 2 6 0 2 0 9 1 4 7 6 7 0 5 样例输出 2 0 3 提示 对于100%的数据1 ≤ n ≤ 10^5 , 1 ≤ k, x0, x1 ≤ 39989, 1 ≤ y0 ≤ y1 ≤ 10^9。 其实这道题就是个板子李超线段树。这个板子就是为了解决这个问题只不过板子太难了而已汗颜 就题论算法把李超线段树用来处理向一个区间加有斜率的线段之后判断某位置权值最大的线段是哪条之类的问题。而最重要的是多了的insert函数。当分到的区间已属于这条线段覆盖的区间是就要进行更神奇的操作了去比较当前节点所存的最优线段。先附上代码。 void insert(int l,int r,int x,int k)
{if(!t[x].h)t[x].hk;if(cmp(t[x].h,k,l))swap(t[x].h,k);if(lr||a[t[x].h].ka[k].k)return;int mid(lr)/2;double g(double)(a[t[x].h].b-a[k].b)/(a[k].k-a[t[x].h].k);if(gl||gr)return;if(gmid)insert(l,mid,x*2,t[x].h),t[x].hk;else insert(mid1,r,x*21,k);
} 因为比较分为两种情况完全压制和在区间内有交点。完全压制不动或直接修改后返回就好了。而对于相交的就必须求出交点根据交点的位置其实也就是判断那条线段在交点那一边处于优势去修改子区间。 对于这段代码理解还是有点困难本蒟蒻太水自己口胡。。要把本区间右侧较大的线段置成本区间最优我也不是太懂为什么。。望神犇来解释若不懂手动模拟一下过程即可。 还要注意一些细节直线斜率是否存在以及两条线是否平行。。RE到死 #includecstdio
#includecstring
#includecstdlib
#includeiostream
#includealgorithm
#define N 101000
#define ll long long
using namespace std;
struct node
{int l,r,id;double k,b;
}a[N];
struct tree{int l,r,h;}t[50000*4];
int n,m;
void build(int l,int r,int x)
{t[x].ll;t[x].rr;if(lr){t[x].h0;return;}int mid(lr)/2;build(l,mid,x*2);build(mid1,r,x*21);
}
bool cmp(int x,int y,double l)
{if(!x)return 1;double l1a[x].k*la[x].b,l2a[y].k*la[y].b;return l1!l2?l1l2:xy;
}
int q(int k,int x)
{if(t[x].lt[x].r)return t[x].h;int mid(t[x].lt[x].r)/2,tmp;if(kmid)tmpq(k,x*2);else tmpq(k,x*21);return cmp(t[x].h,tmp,k)?tmp:t[x].h;
}
void insert(int l,int r,int x,int k)
{if(!t[x].h)t[x].hk;if(cmp(t[x].h,k,l))swap(t[x].h,k);if(lr||a[t[x].h].ka[k].k)return;int mid(lr)/2;double g(double)(a[t[x].h].b-a[k].b)/(a[k].k-a[t[x].h].k);if(gl||gr)return;if(gmid)insert(l,mid,x*2,t[x].h),t[x].hk;else insert(mid1,r,x*21,k);
}
void c(int k,int x)
{if(t[x].la[k].lt[x].ra[k].r){insert(t[x].l,t[x].r,x,k);return;}int mid(t[x].lt[x].r)/2;if(a[k].lmid)c(k,x*2);if(a[k].rmid)c(k,x*21);
}
int main()
{scanf(%d,n);int x1,x2,y1,y2,z,ans0;build(1,50000,1);while(n--){scanf(%d,z);if(z0){scanf(%d,x1);x1(x1ans-1)%399891;//outx1endl;ansq(x1,1);printf(%d\n,ans);}else{m;scanf(%d%d%d%d,x1,y1,x2,y2);x1(x1ans-1)%399891;x2(x2ans-1)%399891;y1(y1ans-1)%10000000001;y2(y2ans-1)%10000000001;//coutx1 x2 y1 y2endl;if(x1x2)swap(x1,x2),swap(y1,y2);if(x1x2)a[m].k0,a[m].bmax(y1,y2);else{a[m].k(double)(y1-y2)/(x1-x2);a[m].b(double)y1-a[m].k*x1;}a[m].lx1;a[m].rx2;a[m].idm;c(m,1);}}
} 转载于:https://www.cnblogs.com/QTY2001/p/7632656.html
