题解 P4515 【[COCI2009-2010#6] XOR】

· · 题解

这里介绍一种复杂度更优（理论复杂度 O(n^3\log n)）的方法。

不知道大家有没有做过这道题，它的做法就是在等腰直角三角形的场景下应用扫描线。我们在 x 轴上做一条扫描线，并只求如下场景上的值：

  1. 有一个三角形撞上了扫描线

  2. 扫描线中某两个三角形不再相交

  3. 有一个三角形离开了扫描线

其中(1)是很好处理的；(2)(3)可以合并处理，如下代码给出了求下一个特殊时刻的算法：

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) 地差分更新求得。这里为了方便直接暴力更新了。

此部分代码：

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，卡掉容斥的异端算法）

总代码：

#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;
}