題意

有一個平面直角坐標系，總共 $n$ 個操作，每個操作有兩種：

• 給定正整數 $x_0,y_0,x_1,y_1$ 表示一條線段的兩個端點。你需要在平面上加入這一條線段，第 $i$ 條被插入的線段的標號為 $i$。
• 給定正整數 $k$，問與直線 $x=k$? 相交的線段中，交點的縱坐標最大的線段的編號。

解法

需要用到線段樹的一個變體：李超線段樹。我們將操作轉化一下：

• 加入一個一次函數，定義域為 $[l,r]$（這個一次函數畫出的線段，左端點橫坐標為 $l$，右端點橫坐標為 $r$）；
• 給定 $k$，在所有 $l\le k\le r$ 的一次函數中，找到在 $x=k$ 處取值最大的那個函數（意思就是在橫坐標為 $k$、垂直于 $y$ 軸的直線上，找到 $y$ 坐標最高的交點）。

來看一個例子：

因為我們總是取 $y$ 坐標最高的交點作為答案，所以真正取到答案的部分長這樣：

• 圖中黑色部分即為答案。

那如何在線段樹上維護這個東西呢？我們考慮線段樹上被兩條線段完全覆蓋的一個部分為 $[l,r]$ 的節點的情況：

• 圖中紅藍色為兩個一次函數的圖像、橙色為對答案有貢獻的部分、深灰色為 $mid=?\frac{l+r}{2}?$、淺灰色為轉折點。李超線段樹的每個節點都會維護當前區間中優勢最大的線段（圖中紅色的線段），因而李超線段樹需要標記永久化。

其中，紅色線段（記為 $g$）先被加入，顯然整個線段在當時就是最優的；藍色線段（記為 $f$）然后被加入。此時深紅色的部分沒有受到影響，$g$ 仍然優勢最大；但淺藍色部分答案改變。我們將其分為兩個子區間（而 $mid$ 左右的區間另稱為左/右區間），可以發現一定有一個子區間被左或右區間完全包含（淺藍色被右區間包含），即在兩條線段中，肯定有一條線段只可能成為左或右區間的答案（$f$ 只可能成為右區間最優的線段）。

我們不妨令，在 $mid$ 處 $f$ 不如 $g$ 優（反之交換兩條線段即可），則：

• 若在左端點處 $f$ 更優，那么 $f$ 和 $g$ 會在左半區間中產生交點，$f$ 只有在左區間才可能優于 $g$，于是遞歸到左兒子中進行下傳；
• 反之，若在右端點處 $f$ 更優，那么交點在右半區間中產生，遞歸到右兒子進行下傳（圖中的情況）；
• 如果左右端點 $g$ 都更優，那么 $f$ 不可能成為答案，不需要下傳（即 $g$ 整個在 $f$?? 的上方）。

當交點正好就在 $mid$ 上時，我們直接將其歸入 $mid$ 上 $f$ 不如 $g$ 優的情況。這樣我們就完成了對完全覆蓋的區間的修改。對于其他部分覆蓋的區間直接遞歸左右兒子解決即可。對于查詢操作，將自己的答案與左右兒子取個 $\min$ 返回。

因為每次修改操作都需要遞歸左右兒子，所以加線段的復雜度是 $O({\log }^{2}n)$ 的。

代碼

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int maxm = 40000;
struct Line {double k,b;
} L[maxn]; int cnt;
void addLine(int x0,int y0,int x1,int y1) {// 加入一條線段if (x0 == x1) L[++ cnt] = Line {0,max(y0,y1) * 1.0};else {double X = x1 - x0, Y = y1 - y0;L[++ cnt].k = Y / X, L[cnt].b = y0 - Y / X * x0;}
}
const double eps = 1e-9;
namespace LiChaoSegmentTree {#define lson l,mid,rt << 1#define rson mid + 1,r,rt << 1 | 1double K(int u,int d) {return L[u].b + L[u].k * d;}int check(double X,double Y) {return X - Y > eps ? 1 : Y - X > eps ? -1 : 0;}int ans[(maxm << 2) + 5];void color(int l,int r,int rt,int u) {int mid = l + r >> 1;int cM = check(K(u,mid), K(ans[rt],mid)); // 計算中點誰占優勢if (cM == 1 || (cM == 0 && u < ans[rt])) // 總是令新線段不如舊線段優swap(u,ans[rt]); // 把自己更新好int cL = check(K(u,l),K(ans[rt],l));int cR = check(K(u,r),K(ans[rt],r));// 選擇新線段可能更新的區域遞歸if (cL == 1 || (cL == 0 && u < ans[rt])) color(lson,u);if (cR == 1 || (cR == 0 && u < ans[rt])) color(rson,u);}int nowl,nowr;void modify(int l,int r,int rt,int u) {if (nowl <= l && r <= nowr)return color(l,r,rt,u);int mid = l + r >> 1;if (nowl <= mid) modify(lson,u);if (mid < nowr) modify(rson,u);}struct Answer { // 返回的答案int id; double val;bool operator<(const Answer &oth) const {int c = check(val,oth.val);return c == -1 ? 1 : c == 1 ? 0 : id > oth.id;}Answer(int X = 0,double Y = 0.0) { id = X, val = Y; }};int now;Answer query(int l,int r,int rt) { // 標記永久化，所以一路上需要不斷地和自己的值取 maxif (l == r) return Answer{ans[rt],K(ans[rt],now)};int mid = l + r >> 1; Answer res(ans[rt],K(ans[rt],now));if (now <= mid) return max(query(lson),res);else return max(query(rson),res);}
} using namespace LiChaoSegmentTree;
int n,tmp;
const int P = 39989, Q = 1e9;
int chg(int X,int p) { return (X + tmp - 1 + p) % p + 1;
}
int main() {scanf("%d",&n);for (int i = 1,op,x0,x1,y0,y1,x;i <= n;i ++) {scanf("%d",&op);if (op == 1) {scanf("%d%d%d%d",&x0,&y0,&x1,&y1);x0 = chg(x0,P), x1 = chg(x1,P), y0 = chg(y0,Q), y1 = chg(y1,Q);if (x0 > x1) swap(x0,x1), swap(y0,y1);nowl = x0, nowr = x1;addLine(x0,y0,x1,y1);modify(1,maxm,1,cnt); } else {scanf("%d",&x), x = now = chg(x,P);printf("%d\n",tmp = query(1,maxm,1).id);}} return 0;
}