题解 P6106【Ynoi2010 Self Adjusting Top Tree】
一个不需要平衡树的做法。
先将线段分为两类：
只考虑第一种情况，第二种情况翻转坐标系后再做一遍即可。
将询问差分成四个右上角为
- 整个线段都在矩形内，即
x_2\leq x,y_2\leq y 。 - 与矩形上边界相交。
- 与矩形右边界相交。
第一部分是一个二维偏序，扫描线
第二三部分是同理的，我们只考虑第二部分。
按 set 维护所有 set 直接维护。
考虑如何处理一个询问，在 set 中二分出它所对应的前缀，这个前缀的线段上边界相交。
贡献的处理是简单的，化一下式子可以知道是两个求和的形式。问题在于如何定位出这些线段。
由于线段不相交，那么一定存在一个排列线段的顺序，使得对于每个时刻 set 中的元素在这个排列中的位置都是递增的。
不妨先做一遍扫描线，在插入、删除线段时都让相邻线段之间从左至右连一条有向边，这样可以建立出一张 DAG，这个 DAG 的拓扑序即为一个满足条件的排列。
接下来就好办了，找到前缀所对应的拓扑序最大的线段（也就是 set 中的最后一个与上边界相交的），直接查询一个拓扑序上的前缀和即可。
时间复杂度
实际上实现的时候只有第一遍扫描线需要 set，第二遍所需的所有信息都可以在第一遍就处理出来。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
const int M=1e6+5;
const double eps=1e-8;
double dis(double x,double y) {
return sqrt(x*x+y*y);
}
double cross(double x1,double y1,double x2,double y2) {
return x1*y2-x2*y1;
}
struct segment {
int x1,y1,x2,y2;
double len() {
return dis(x2-x1,y2-y1);
}
}a[2][N],b[N];
double get(segment a,double y) {
if (a.y1==a.y2) {
return a.x1;
}
return (y-a.y1)/(a.y2-a.y1)*(a.x2-a.x1)+a.x1;
}
bool check(segment a,segment b) {
if (a.x1==a.x2&&a.y1==a.y2&&b.x1<=a.x1&&a.x2<=b.x2&&b.y1<=a.y1&&a.y2<=b.y2&&abs(cross(a.x1-b.x1,a.y1-b.y1,a.x1-b.x2,a.y1-b.y2))<eps) {
return 0;
}
if (b.x1==b.x2&&b.y1==b.y2&&a.x1<=b.x1&&b.x2<=a.x2&&a.y1<=b.y1&&b.y2<=a.y2&&abs(cross(b.x1-a.x1,b.y1-a.y1,b.x1-a.x2,b.y1-a.y2))<eps) {
return 0;
}
double y=max(a.y1,b.y1);
return get(a,y)<get(b,y);
}
struct bit {
int n;
double t[M];
void send(int _n) {
n=_n;
for (int i=1;i<=n;i++) {
t[i]=0;
}
}
void add(int x,double y) {
for (;x<=n;x+=x&-x) {
t[x]+=y;
}
}
double query(int x) {
double res=0;
for (;x;x&=x-1) {
res+=t[x];
}
return res;
}
}t0,t1,tt;
int n,m,p[N],que[N],tmp;
struct cmp {
bool operator ()(const int &u,const int &v) const {
return check(a[tmp][u],a[tmp][v]);
}
};
vector<int>ins[M];
struct Query {
int x,f,id,pos;
};
vector<Query>q[M];
double ans[N];
vector<int>e[N];
int deg[N],pos[N];
void add_edge(int u,int v) {
e[u].emplace_back(v);
deg[v]++;
}
void solve(int n,segment *a,bool flag) {
for (int i=1;i<=n;i++) {
e[i].clear();
deg[i]=0;
}
for (int i=1;i<=1e6;i++) {
ins[i].clear();
q[i].clear();
}
for (int i=1;i<=n;i++) {
ins[a[i].y1].emplace_back(i);
ins[a[i].y2].emplace_back(-i);
}
for (int i=1;i<=m;i++) {
q[b[i].y2].emplace_back((Query){b[i].x2,1,i,0});
q[b[i].y2].emplace_back((Query){b[i].x1,-1,i,0});
q[b[i].y1].emplace_back((Query){b[i].x2,-1,i,0});
q[b[i].y1].emplace_back((Query){b[i].x1,1,i,0});
}
set<int,cmp>S;
for (int i=1;i<=1e6;i++) {
for (int j:ins[i]) {
if (j>0) {
auto now=S.insert(j).first;
if (now!=S.begin()) {
add_edge(*prev(now),j);
}
if (++now!=S.end()) {
add_edge(j,*now);
}
} else {
j=-j;
auto now=S.find(j);
if (now!=S.begin()&&next(now)!=S.end()) {
add_edge(*prev(now),*next(now));
}
S.erase(now);
}
}
for (auto &[x,f,id,pos]:q[i]) {
a[0]=(segment){x,i,x,i};
set<int,cmp>::iterator now;
if (flag) {
now=S.upper_bound(0);
} else {
now=S.lower_bound(0);
}
if (now!=S.begin()) {
pos=*--now;
}
}
}
int h=1,t=0;
for (int i=1;i<=n;i++) {
if (!deg[i]) {
que[++t]=i;
}
}
while (h<=t) {
int now=que[h];
p[now]=h++;
for (int to:e[now]) {
if (!--deg[to]) {
que[++t]=to;
}
}
}
tt.send(1e6);
t0.send(1e6);
t1.send(1e6);
for (int i=1;i<=1e6;i++) {
for (int j:ins[i]) {
if (j>0) {
t0.add(p[j],a[j].y1*(a[j].len()/(a[j].y2-a[j].y1)));
t1.add(p[j],a[j].len()/(a[j].y2-a[j].y1));
} else {
j=-j;
t0.add(p[j],-a[j].y1*(a[j].len()/(a[j].y2-a[j].y1)));
t1.add(p[j],-a[j].len()/(a[j].y2-a[j].y1));
if (flag) {
tt.add(a[j].x2,a[j].len());
}
}
}
for (auto [x,f,id,pos]:q[i]) {
if (flag) {
ans[id]+=f*tt.query(x);
}
if (pos) {
ans[id]+=f*(i*t1.query(p[pos])-t0.query(p[pos]));
}
}
}
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0);
cout.precision(10),cout.setf(ios::fixed);
cin>>n;
double sum=0;
int n1=0,n2=0;
for (int i=1;i<=n;i++) {
segment p;
cin>>p.x1>>p.y1>>p.x2>>p.y2;
sum+=p.len();
if (p.x1>p.x2) {
swap(p.x1,p.x2);
swap(p.y1,p.y2);
}
if (p.y1<p.y2) {
a[0][++n1]=p;
} else {
a[1][++n2]=p;
}
}
cin>>m;
for (int i=1;i<=m;i++) {
cin>>b[i].x1>>b[i].y1>>b[i].x2>>b[i].y2;
}
tmp=0;
solve(n1,a[0],1);
for (int i=1;i<=n;i++) {
swap(a[0][i].x1,a[0][i].y1);
swap(a[0][i].x2,a[0][i].y2);
}
for (int i=1;i<=m;i++) {
swap(b[i].x1,b[i].y1);
swap(b[i].x2,b[i].y2);
}
solve(n1,a[0],0);
for (int i=1;i<=n;i++) {
swap(a[0][i].x1,a[0][i].y1);
swap(a[0][i].x2,a[0][i].y2);
}
for (int i=1;i<=m;i++) {
swap(b[i].x1,b[i].y1);
swap(b[i].x2,b[i].y2);
}
tmp=1;
for (int i=1;i<=n;i++) {
a[1][i].y1=1e6+1-a[1][i].y1;
a[1][i].y2=1e6+1-a[1][i].y2;
}
for (int i=1;i<=m;i++) {
b[i].y1=1e6+1-b[i].y1;
b[i].y2=1e6+1-b[i].y2;
swap(b[i].y1,b[i].y2);
}
solve(n2,a[1],1);
for (int i=1;i<=n;i++) {
swap(a[1][i].x1,a[1][i].y1);
swap(a[1][i].x2,a[1][i].y2);
}
for (int i=1;i<=m;i++) {
swap(b[i].x1,b[i].y1);
swap(b[i].x2,b[i].y2);
}
solve(n2,a[1],0);
for (int i=1;i<=n;i++) {
swap(a[1][i].x1,a[1][i].y1);
swap(a[1][i].x2,a[1][i].y2);
}
for (int i=1;i<=m;i++) {
swap(b[i].x1,b[i].y1);
swap(b[i].x2,b[i].y2);
}
for (int i=1;i<=m;i++) {
cout<<ans[i]/sum<<"\n";
}
return 0;
}