题解 P4515 【[COCI2009-2010#6] XOR】
xtx1092515503
2020-11-02 11:04:54
这里介绍一种复杂度更优（理论复杂度 $O(n^3\log n)$）的方法。
不知道大家有没有做过[这道题](https://www.luogu.com.cn/problem/P3219)，它的做法就是在等腰直角三角形的场景下应用**扫描线**。我们在 $x$ 轴上做一条扫描线，并只求如下场景上的值：
1. 有一个三角形撞上了扫描线
2. 扫描线中某两个三角形不再相交
3. 有一个三角形离开了扫描线
其中(1)是很好处理的；(2)(3)可以合并处理，如下代码给出了求下一个特殊时刻的算法：
```cpp
int nex(){
int mn=0x3f3f3f3f;
for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)if(p[j].second>p[i].first)mn=min(mn,p[j].second-p[i].first);
return mn;
}
```
求特殊时刻扫描线上的有效长度，可以通过 $O(n\log n)$ 将扫描线上东西离散化后，$O(n^2)$ 地暴力异或更新或者 $O(n)$ 地差分更新求得。这里为了方便直接暴力更新了。
此部分代码：
```cpp
int calc(){
v.clear();
for(int i=1;i<=m;i++)v.push_back(p[i].first),v.push_back(p[i].second);
sort(v.begin(),v.end()),v.resize(unique(v.begin(),v.end())-v.begin());
for(int i=0;i+1<v.size();i++)occ[i]=false;
for(int i=1;i<=m;i++){
int x=lower_bound(v.begin(),v.end(),p[i].first)-v.begin(),y=lower_bound(v.begin(),v.end(),p[i].second)-v.begin();
for(int j=x;j<y;j++)occ[j]^=1;
}
int ret=0;
for(int i=0;i+1<v.size();i++)if(occ[i])ret+=v[i+1]-v[i];
return ret;
}
```
两个特殊时刻间的面积，可以直接通过梯形面积公式求出。
时间复杂度 $O(n^3\log n)$，因为最多有 $O(n^2)$ 个特殊时间，每个特殊时间的有效长度需要 $O(n\log n)$ 地求出。
（所以明显本题可以被加强到 $n=100$，卡掉容斥的异端算法）
总代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
int x,y1,y2;
friend bool operator <(const node &u,const node &v){return u.x<v.x;}
}a[20];
pair<int,int>p[20];
vector<int>v;
bool occ[100];
int nex(){
int mn=0x3f3f3f3f;
for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)if(p[j].second>p[i].first)mn=min(mn,p[j].second-p[i].first);
return mn;
}
int calc(){
v.clear();
for(int i=1;i<=m;i++)v.push_back(p[i].first),v.push_back(p[i].second);
sort(v.begin(),v.end()),v.resize(unique(v.begin(),v.end())-v.begin());
for(int i=0;i+1<v.size();i++)occ[i]=false;
for(int i=1;i<=m;i++){
int x=lower_bound(v.begin(),v.end(),p[i].first)-v.begin(),y=lower_bound(v.begin(),v.end(),p[i].second)-v.begin();
for(int j=x;j<y;j++)occ[j]^=1;
}
int ret=0;
for(int i=0;i+1<v.size();i++)if(occ[i])ret+=v[i+1]-v[i];
return ret;
}
void nex(int x){
for(int i=1;i<=m;i++)p[i].second-=x;
int len=0;
for(int i=1;i<=m;i++)if(p[i].first!=p[i].second)p[++len]=p[i];
m=len;
}
long long res;
int main(){
// freopen("I.in","r",stdin);
// freopen("A.out","w",stdout);
scanf("%d",&n);
for(int i=1,x,y,z;i<=n;i++)scanf("%d%d%d",&x,&y,&z),a[i].x=x,a[i].y1=y,a[i].y2=y+z;
sort(a+1,a+n+1);
for(int i=1,las=0,laslen=0;;){
if(!m&&i>n)break;
int delta=nex();
if(i<=n)delta=min(delta,a[i].x-las);
nex(delta);
int now=calc();
if(las!=0)res+=1ll*delta*(now+laslen),las+=delta;
else las=delta;
if(i<=n&&a[i].x<=las)p[++m]=make_pair(a[i].y1,a[i].y2),i++,laslen=calc();
else laslen=now;
}
printf("%lld.%d\n",res>>1,(res&1)?5:0);
return 0;
}
```