方法同lyd的书，解释细节
段与点
线段树维护的是扫描线上的段。而题目给出的是点。所以需要注意（段=点-1）这个关系。
举个栗子。查询(1,3)实际上查询的是 1 <-> 2 <-> 3 这两个线段。
无lazy优化
方法是更新的时候给$log(r-l)$个完全包含在查询里的区间更新cnt（被标记次数），不是所有，更新完了就不要往下走了。对于每个经过的区间要更新len（长度），因为他们被影响了。
不知道这是不是个优化这个动作虽然使得代码量减小了，但是思考量却增加了。
因为题目给的矩形，所以所有第二次出现的线段一定在之前是出现过的，他们是成对出现的。每个左边界造成的影响一定要等到另一个和他配对的右边界到来才会消失，并且是完全消失。也就是说每个左边界覆盖的部分至少要等到他自己的右边界到来才可能消失，期间不可能出现空洞
所以说如果遇见一个区间标记大于零的，说明之前至少有一个这么长的区间曾经覆盖过他。他所覆盖的长度一定是自己的全长。否则就从子区间更新。
整个操作在更新的时候一起完成。最后根节点的长度就是覆盖长度，省去了写查询函数。
思考一下，如果题目给的是 平行四边形 梯形 ..... 等等非矩形。那么这个方法就不可用了。需要lazy标记。
多组输入
记得每组在操作前先初始化。否则WA/TLE两开花
去重排序离散化可以用一起set完成。虽然常数大了点，但是方便啊。而且也是$nlogn$的复杂度。
#include<bits/stdc++.h>
using namespace std;
#define ls(x) (x << 1)
#define rs(x) ((x << 1) + 1)
vector< pair<double, pair< pair< double, double>, int > > > dir;
set<double> st;
unordered_map<double,int> ump;
double raw[20020];
int n;
struct SegNode{
int l,r,cnt;
double len;
#define l(x) t[x].l
#define r(x) t[x].r
#define cnt(x) t[x].cnt
#define len(x) t[x].len
}t[20020 * 8];
void build(int p, int l, int r)
{
l(p) = l; r(p) = r; cnt(p) = 0; len(p) = 0;
if(l == r){return ;}
int mid = (l + r) >> 1;
build(ls(p), l, mid);
build(rs(p), mid + 1, r);
}
void update(int p, int l, int r, int k)
{
if(l <= l(p) && r >= r(p))
{
cnt(p) += k;
len(p) = cnt(p) > 0 ? raw[r(p) + 1] - raw[l(p)] : len(ls(p)) + len(rs(p)) ;
return ;
}
int mid = (l(p) + r(p)) >> 1;
if(l <= mid) update(ls(p), l, r, k);
if(r > mid) update(rs(p), l, r, k);
len(p) = cnt(p) > 0 ? raw[r(p) + 1] - raw[l(p)] : len(ls(p)) + len(rs(p)) ;
return ;
}
void ini()
{
dir.clear();
ump.clear();
//raw.clear();
st.clear();
//memset(t,0,sizeof t);
}
int main()
{
int testcase = 0;
while(1)
{
//cin >> n;
scanf("%d", &n);
if(n == 0) return 0;
ini();
double a = 0,b = 0,c = 0,d = 0;
for(int i = 1; i <= n; i++)
{
//cin >> a >> b >> c >> d;
scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
dir.push_back({a,{{b,d},1}});
dir.push_back({c,{{b,d},-1}});
st.insert(b);st.insert(d);
}
sort(dir.begin(),dir.end());
set<double> ::iterator it;
int rk = 0;
for(it = st.begin(); it != st.end(); it ++)
{
ump[*it] = ++rk;
raw[rk] = *it;
}
build(1,1,rk-1);
double x = 0,ans = 0;
for(auto &P:dir)
{
ans += (P.first - x) * len(1);
update(1,ump[P.second.first.first],ump[P.second.first.second] - 1,P.second.second);
x = P.first;
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n",++testcase,ans);
}
}
想请教一下：len(p) = cnt(p) > 0 ? raw[r(p) + 1] - raw[l(p)] : len(ls(p)) + len(rs(p)) ;为啥r(p)要加1啊
为什么线段树开到4*20005会MLE？理论上来说开到数据范围四倍不就够了吗，（我写出来的也会MLE）而且好像不是题目数据范围的锅，甚至当rk=1100左右就会MLE
为什么我交您的代码过不了/抱头
一开始RE，把线段树的大小改为N * 8之后T了
数据好像加强了
是因为set么
不是，是因为unordered_map常数太大了，改成数组就可以了，而且cin cout效率低。代码已更新
好的谢谢大佬
请问，n <= 100，那么最多只有200个不同的纵坐标啊……为什么我这样写就段错误呢？