（未完待续）

题目链接：JZOJ 3738/IOI2012, Day2, Ideal City

题目

本题有多种解法（模拟三种、正解），详情请看下一页。

题解

解法 A （直接模拟）

解法 B （另一种直接模拟）

解法 C （面对数据范围模拟）

解法 D （正解）

思路

考虑对解法 B 的更进一步的优化。

代码

代码比较长，要注意多处细节。
时间复杂度为 $\Theta(n\log _ 2n)$，预计得分 $100$ 分。

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::swap;
using std::sort;
#include<vector>
using std::vector;
typedef long long ll;
#define MOD 1000000000ll
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){//快读，无符号
    register bool flag=false;
    register char ch=getchar();
    register int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return flag?-res:res;
}
const int MAXN=100000+5;
struct Point{//定义点的类型
    int x,y;
    bool operator<(const Point &a)const{
        return (x!=a.x)?(x<a.x):(y<a.y);
    }
};
struct Node{//定义缩点后得到的节点类型
    int x,Miny,Maxy;
    vector<int> to;
    Node(void){
        return;
    }
    Node(int a,int b,int c){
        x=a,Miny=b,Maxy=c;
        return;
    }
};
int n;
ll res;
Point S[MAXN];
vector<Node> V;
void Build(void);
int weight(int);
ll DFS(int,int);
ll Calc(void);
int Solve(void);
int main(void){
    //freopen("city.in","r",stdin);
    //freopen("city.out","w",stdout);
    register int i;
    n=read();
    //scanf("%d",&n);
    for(i=1;i<=n;++i)
        S[i].x=read(),S[i].y=read();
    //scanf("%d%d",&S[i].x,&S[i].y);
    printf("%d\n",Solve());
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}
void Build(void){
    register int i,x,y,Miny,cnt,cnt1,cnt2;
    V.clear();
    sort(S+1,S+n+1);
    cnt1=1;
    while(cnt1<=n){
        x=S[cnt1].x,Miny=S[cnt1].y,y=Miny;
        for(i=cnt1+1;i<=n;++i){
            if(S[i].y==y+1)
                ++y;
            else
                break;
        }
        cnt1=i;
        V.push_back(Node(x,Miny,y));
    }
    for(cnt1=0,cnt2=1;cnt2<(int)V.size();++cnt2){
        while((V[cnt1].x+1<V[cnt2].x)||(V[cnt1].x+1==V[cnt2].x&&V[cnt1].Maxy<V[cnt2].Miny))
            ++cnt1;
        cnt=0;
        while(V[cnt1].x+1==V[cnt2].x&&V[cnt1].Miny<=V[cnt2].Maxy){
            ++cnt;
            V[cnt1].to.push_back((int)cnt2);
            V[cnt2].to.push_back((int)cnt1);
            ++cnt1;
        }
        if(cnt>0)
            --cnt1;
    }
    return;
}
ll DFS(int ID,int fa){
    register int i;
    register ll size=V[ID].Maxy-V[ID].Miny+1;
    for(i=0;i<(int)V[ID].to.size();++i)
        if(V[ID].to[i]!=fa)
            size=(size+DFS(V[ID].to[i],ID))%MOD;
    res=(res+size*(n-size))%MOD;
    return size;
}
ll Calc(void){
    Build();
    res=0;
    DFS(1,0);
    return res;
}
int Solve(void){
    register int i;
    register ll ans1,ans2;
    ans1=Calc();
    for(i=1;i<=n;++i)
        swap(S[i].x,S[i].y);
    ans2=Calc();
    return (ans1+ans2)%MOD;
}