旋转扫描线

**旋转扫描线** lxl ppt 里讲的太怪了。 我们认为对于 $n$ 个点，关于它们的有效半平面中**有效斜率的**数量级不超 $O(n ^ 2)$，这是一个结论。 几何角度理解：将 $k$ 从 $-\infty$ 到 $\infty$ 单增，每个点确定一条斜率为 $k$ 的直线。此时截距的增长和且仅和一个点的横坐标有关，则对每个点确定的直线，存在一个临界 $k$ 满足当斜率超过 $k$ 时一个点确定直线的截距恒大于另一个点确定直线的截距。故有效斜率数量不超 $O(n ^ 2)$。 序列角度：在 $k$ 单增的过程中维护每个点确定直线按照截距从小到大排序的位置关系，每个点对贡献 $O(1)$ 次交换，则需要的临界斜率数量级不超 $O(n ^ 2)$。 [己酸集合](https://uoj.ac/problem/553) 我们分块，维护每 $B$ 个点在斜率为 $k$ 时按照 $y - xk$ 的动态排序结果，可以理解成截距，显然任意一个半平面在当前的体现形式都是一个前缀/后缀。 我们先 $O(B^2)$ 预处理出每个点对分界的斜率（解不等式 $y_1 - x_1k \leq y_2 - x_2k$），然后每次暴力 swap 数组对应位置，查询半平面即通过二分确定当前的前缀点集。 不要直接用 $k$ 排序，用向量或者 atan2 来比斜率都好啊！某个 sb 因为此题用 $k$ 排序而后面一题精度就炸了。 时间复杂度 $O(n \sqrt {m \log n})$。 [CTS 2022 袜子](https://www.luogu.com.cn/problem/P8261) [detailed sol](https://www.luogu.com.cn/blog/eulogized/solution-p8261) 这里主要还是讲一些理解。 数颜色，感觉血压直接上来了。 不妨还是套用先前的做法，我们发现分块时点本身是不带顺序（即他不是序列概念而是集合概念），那我们不妨先按照颜色排序！然后再套路分块。 然后感觉就清晰很多了，维护半平面下每个块第一种颜色，最后一种颜色数量以及颜色平方和即可对所有询问做半群合并。 但是如果要直接 swap 就得写线段树，这个常数一看就很大！ 我们再仔细思考我们的旋转扫描线。发现我们本质是按照当前的截距排序的，那么我们肯定可以做到一次 swap 两个相邻的点，因为如果是跨越了点的交换那么说明中间的点肯定不能保持原本关于被交换点的相对位置，一定不会晚于两个交换点进行与两个点的交换。 我们初始化时令 $k = -\infty$，则按照 $x$ 从小到大排，假设 $k$ 增到了最终状态，即我们的目标状态，我们若按照冒泡排序的方法交换肯定可以做到正确交换；我们在最外层按照 $k$ 排序的基础上内层再套上 $x,y$ 作为第二关键字和第三关键字进行排序。即可保证当 $k$ 相同时所有的交换是相邻的；同时发现 $k$ 不相同是不影响正确性的。 时间复杂度 $O(n \sqrt {m \log n})$。 交换相邻位置修改信息我想就不用再教了，这里破例放一下代码，块长没调。 ```cpp /* 我们直接分块维护就行了，每次分成三个段算就行了。 假的。 每次交换都是交换相邻的？谔谔！ */ #include "bits/stdc++.h" using namespace std; #define int ll #define ll long long const int Len = 1e6 + 5 , B = 1000; int n,m; struct P { int x,y;int c;int id; P(){x = y = c = id = 0;} P(int X,int Y,int C,int ID){x = X , y = Y , c = C , id = ID;} bool operator < (const P &Ano) const {return x < Ano.x || (x == Ano.x && y < Ano.y);} }a[Len],b[Len];int pos[Len],len;//第 x 个点当前指的位置 bool cmp(P x,P y){return x.c < y.c || (x.c == y.c && x < y);} struct PP { int x,y; PP(){x = y = 0;} PP(int X,int Y){x = X , y = Y;} inline void clr(){x = y = 0;} inline ll operator * (const PP &Ano) const {return 1ll * x * Ano.y - 1ll * y * Ano.x;} inline PP operator - (const PP &Ano) const {return PP(x - Ano.x , y - Ano.y);} }; struct EPL { PP a,b;int x,y;double c; EPL(){a.clr() , b.clr() , x = y = 0 , c = 0;} EPL(PP A,PP B,int X,int Y,double C){a = A , b = B , x = X , y = Y , c = C;} bool operator < (const EPL &Ano) const {return c < Ano.c || (c == Ano.c && x < Ano.x) || (c == Ano.c && x == Ano.x && y < Ano.y);} }lo[Len]; struct Q { int id,op,a,b,c,ov;double d; Q(){id = op = a = b = c = ov = d = 0;} Q(int ID,int OP,int A,int B,int C,int OV,double D){id = ID , op = OP , a = A , b = B , c = C , ov = OV , d = D;} bool operator < (const Q &Ano) const {return d < Ano.d;} }ql[2][Len];int le[2]; int col[Len],prec[Len],prel[Len],prer[Len],tos[Len]; ll pres[Len],sufs[Len]; int sufc[Len],sufl[Len],sufr[Len]; struct info { int x,z;ll y; info(){x = z = y = 0;} info(int X,ll Y,int Z){x = X , y = Y , z = Z;} }Pt[Len]; int lc,rc,plc,prc;inline ll m2(int x){return 1ll * x * x;} inline int bs(EPL x,Q y) { if(x.c < y.d) return -1; else if(x.c == y.d) return 0; return 1; } inline void sp(int x,int y) { //pres,prec,prel,prer if(b[pos[x]].c != b[pos[y]].c) swap(prec[pos[x]] , prec[pos[y]]) , swap(sufc[pos[x]] , sufc[pos[y]]); swap(b[pos[x]] , b[pos[y]]); pres[pos[x]] = pres[pos[x] - 1] + m2(prec[pos[x]]) - m2(prec[pos[x]] - 1) , prel[pos[x]] = prel[pos[x] - 1] , prer[pos[x]] = prer[pos[x] - 1]; if(b[pos[x]].c == lc) prel[pos[x]] = prec[pos[x]]; if(b[pos[x]].c == rc) prer[pos[x]] = prec[pos[x]]; pres[pos[y]] = pres[pos[y] - 1] + m2(prec[pos[y]]) - m2(prec[pos[y]] - 1) , prel[pos[y]] = prel[pos[y] - 1] , prer[pos[y]] = prer[pos[y] - 1]; if(b[pos[y]].c == lc) prel[pos[y]] = prec[pos[y]]; if(b[pos[y]].c == rc) prer[pos[y]] = prec[pos[y]]; sufs[pos[y]] = sufs[pos[y] + 1] + m2(sufc[pos[y]]) - m2(sufc[pos[y]] - 1) , sufl[pos[y]] = sufl[pos[y] + 1] , sufr[pos[y]] = sufr[pos[y] + 1]; if(b[pos[y]].c == lc) sufl[pos[y]] = sufc[pos[y]]; if(b[pos[y]].c == rc) sufr[pos[y]] = sufc[pos[y]]; sufs[pos[x]] = sufs[pos[x] + 1] + m2(sufc[pos[x]]) - m2(sufc[pos[x]] - 1) , sufl[pos[x]] = sufl[pos[x] + 1] , sufr[pos[x]] = sufr[pos[x] + 1]; if(b[pos[x]].c == lc) sufl[pos[x]] = sufc[pos[x]]; if(b[pos[x]].c == rc) sufr[pos[x]] = sufc[pos[x]]; swap(pos[x] , pos[y]); //printf("!%d %d\n",pos[x],pos[y]); } inline void xxp(int x,int y) { if(pos[x] > pos[y]) return; for(int j = pos[y] ; j > pos[x] ; j --) { int x = tos[j] , y = tos[j - 1]; sp(y , x); swap(tos[j] , tos[j - 1]); } } inline void work(int N,int op) { sort(b + 1 , b + 1 + N);len = 0; for(int i = 1 ; i <= N ; i ++) { col[b[i].c] ++;prec[i] = col[b[i].c]; pres[i] = pres[i - 1] + m2(col[b[i].c]) - m2(col[b[i].c] - 1) , prel[i] = prel[i - 1] , prer[i] = prer[i - 1]; if(b[i].c == lc) prel[i] = col[lc]; if(b[i].c == rc) prer[i] = col[rc]; } for(int i = 1 ; i <= N ; i ++) col[b[i].c] = 0; sufc[N + 1] = sufs[N + 1] = sufl[N + 1] = sufr[N + 1] = 0; for(int i = N ; i >= 1 ; i --) { col[b[i].c] ++;sufc[i] = col[b[i].c]; sufs[i] = sufs[i + 1] + m2(col[b[i].c]) - m2(col[b[i].c] - 1) , sufl[i] = sufl[i + 1] , sufr[i] = sufr[i + 1]; if(b[i].c == lc) sufl[i] = col[lc]; if(b[i].c == rc) sufr[i] = col[rc]; }for(int i = 1 ; i <= N ; i ++) col[b[i].c] = 0; EPL rs; for(int i = 1 ; i <= N ; i ++) { for(int j = i + 1 ; j <= N ; j ++) if(b[j].x != b[i].x) { rs = EPL(PP(b[i].x , b[i].y) , PP(b[j].x , b[j].y) , i , j , 0); rs.c = atan2((rs.b - rs.a).y , (rs.b - rs.a).x); if(bs(rs , ql[op][le[op]]) >= 0) continue; lo[++ len] = rs; } } //printf("!!!?%d\n",len); sort(lo + 1 , lo + 1 + len);//for(int i = 1 ; i <= len ; i ++) printf("??!!%d %d\n",lo[i].x,lo[i].y); int j = 1;for(int i = 1 ; i <= N ; i ++) pos[i] = tos[i] = i; ll iss;int gl,gr; for(int i = 1 ; i <= le[op] ; i ++) { while(j <= len && bs(lo[j] , ql[op][i]) < 0){xxp(lo[j].x , lo[j].y);j ++;} //printf("!!!%d %d\n",i,j - 1); int l = 1 , r = N , x; if(!ql[op][i].op) { while(l < r) { int mid = (l + r + 1) >> 1; if(1ll * ql[op][i].a * b[mid].x + 1ll * ql[op][i].b * b[mid].y + ql[op][i].c < 0) l = mid; else r = mid - 1; } if(1ll * ql[op][i].a * b[1].x + 1ll * ql[op][i].b * b[1].y + ql[op][i].c >= 0) x = 0; else x = l; iss = pres[x] , gl = prel[x] , gr = prer[x]; } else { while(l < r) { int mid = (l + r) >> 1; if(1ll * ql[op][i].a * b[mid].x + 1ll * ql[op][i].b * b[mid].y + ql[op][i].c < 0) r = mid; else l = mid + 1; } if(1ll * ql[op][i].a * b[N].x + 1ll * ql[op][i].b * b[N].y + ql[op][i].c >= 0) x = N + 1; else x = r; iss = sufs[x] , gl = sufl[x] , gr = sufr[x]; } //l /*printf("!!!#%lld\n",x); if(ql[op][i].id == 1) { printf("nb%lld\n",i); if(!ql[op][i].op)for(int j = 1 ; j <= x ; j ++) printf("?%lld %lld %lld\n",b[j].x,b[j].y,b[j].c); else for(int j = x ; j <= N ; j ++) printf("?%lld %lld %lld\n",b[j].x,b[j].y,b[j].c); }*/ if(prc == lc) { //printf("1#%d %lld %d %lld %d %d\n",x,Pt[ql[op][i].id].y,Pt[ql[op][i].id].z,iss,gl,gr); Pt[ql[op][i].id].y += iss + m2(Pt[ql[op][i].id].z + gl) - m2(Pt[ql[op][i].id].z) - m2(gl); if(lc == rc) Pt[ql[op][i].id].z += gl; else Pt[ql[op][i].id].z = gr; } else { //printf("2#%d %lld %d %lld %d %d\n",x,Pt[ql[op][i].id].y,Pt[ql[op][i].id].z,iss,gl,gr); Pt[ql[op][i].id].y += iss; Pt[ql[op][i].id].z = gr; } } } inline int read() { char ch = getchar(); int x = 0, f = 1; while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while ('0' <= ch && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } inline void write(ll x) { if (x > 9) write(x / 10); putchar(x % 10 + '0'); } signed main() { //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); n = read() , m = read(); for(int i = 1 ; i <= n ; i ++) { int x = read() , y = read() , c = read(); a[i] = P(x , y , c , i); } for(int i = 1 ; i <= m ; i ++) { int a = read() , b = read() , c = read() , ov; if(b > 0) ov = -1; else ov = 1; if(b > 0) ql[0][++ le[0]] = Q(i , 0 , a , b , c , ov , 0); else ql[0][++ le[0]] = Q(i , 1 , a , b , c , ov , 0); ql[0][le[0]].d = atan2(ov * a , ov * -b); } sort(ql[0] + 1 , ql[0] + 1 + le[0]); //for(int i = 1 ; i <= le[0] ; i ++) printf("!!!%lld %lld %lld\n",ql[0][i].a,ql[0][i].b,ql[0][i].c); sort(a + 1 , a + 1 + n , cmp); //for(int i = 1 ; i <= n ; i ++) printf("!!!%.0lf %.0lf %d %d\n",a[i].x,a[i].y,a[i].c,a[i].id); for(int i = 1 ; i <= n ; i += B) { int l = i , r = min(i + B - 1 , n); lc = a[l].c , rc = a[r].c; for(int j = i ; j <= min(i + B - 1 , n) ; j ++) b[j - i + 1] = a[j]; const int LEN = min(B , n - i + 1); work(LEN , 0); plc = lc , prc = rc; } for(int i = 1 ; i <= m ; i ++) write(Pt[i].y) , putchar('\n'); return 0; } ``` [Ynoi2003 Helesta](https://www.luogu.com.cn/problem/P8529) 我觉得我的题解够详细了。不想再讲一次了。 [sol](https://www.luogu.com.cn/blog/eulogized/jing-mi-hei-an-zhong-chun-chun-yu-dong-zhi-wu-yin-kong-ju-er-mu-fou-z)