【CF429E】Points and Segments

题面

https://www.luogu.org/problem/CF429E

题解

拆点$+$欧拉回路。

我没看懂为什么有的人可以点数是$2n$级别，反正我的是$3n$级别。。。。

#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 100500
#define ri register int
using namespace std;

int n,cc=-1;
int l[N],r[N],dct[N<<2],du[N<<2];
bool vis[N<<2];
vector<int> ed[N<<2],to,vv;

inline int read() {
  int ret=0,f=0; char ch=getchar();
  while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
  while (ch>='0' && ch<='9') ret*=10,ret+=(ch-'0'),ch=getchar();
  return f?-ret:ret;
}

void add_edge(int u,int v) {
  ++cc; to.push_back(v); vv.push_back(0); ed[u].push_back(cc); du[u]++;
  ++cc; to.push_back(u); vv.push_back(0); ed[v].push_back(cc); du[v]++;
}

void euler(int x) {
  vis[x]=1;
  for (ri i=0;i<ed[x].size();i++) {
    int e=ed[x][i];
    if (!vv[e]) {
      vv[e]=1; vv[1^e]=2;
      euler(to[e]);
    }
  }
}

int main() {
  int tn=n=read();
  for (ri i=1;i<=n;i++) {
    l[i]=read(); r[i]=read();
    l[i]*=2; r[i]*=2;
    if (r[i]<l[i]) swap(l[i],r[i]);
    dct[3*i-2]=l[i]-1; dct[3*i-1]=l[i]; dct[3*i]=r[i];
  }
  sort(dct+1,dct+3*n+1);
  n=unique(dct+1,dct+3*n+1)-dct-1;
  for (ri i=1;i<=tn;i++) {
    l[i]=lower_bound(dct+1,dct+n+1,l[i]-1)-dct;
    r[i]=lower_bound(dct+1,dct+n+1,r[i])-dct;
    add_edge(l[i],r[i]);
  }
  for (ri i=1;i<n;i++) if (du[i]&1) add_edge(i,i+1);
  for (ri i=1;i<=n;i++) if (!vis[i]) euler(i);
  for (ri i=0;i<2*tn;i+=2) {
    if (vv[i]==2) putchar('0'); else putchar('1');
    putchar(' ');
  }
  return 0;
}