AOJ 2405 Sister Ports

AOJ 2405 Sister Ports

概要

円周上に1~Nの点があり、隣同士に辺が張ってある。さらに円の内部にも辺がM本張ってあり、それらは交差していない。マッチングの個数を線形で求めよ。(二乗でも通るらしい？)

解法

とりあえずこの類は1とNの間で切り離して直線にし、区間の問題にする。(このとき、Nと1を結ぶ辺も区間になる)
区間の両端を使うかどうかで状態数４のDPっぽいことをする。ちなみに計算量はMにだけ依存してます。
区間を右端の昇順・同じなら左端の降順でソートし、順番に処理する。
今見てる区間内に含まれる区間たちを合体させ、それを包む。まだ合体させてない区間たちはstack的に管理するといい。
実装は遷移の部分を慎重にやらないとhogeる。

#include<cstdio>
#include<algorithm>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

const int MX = 50005, mod = 1000003;

int n, m;
P p[MX];
ll d[4][MX]; int di, dl[MX], dr[MX];

int main(){
  int a, l, r;
  while(1){
    scanf("%d%d",&n,&m);
    if(!n) break;
    rep(i,m){
      scanf("%d%d",&l,&r);
      if(l > r) swap(l,r);
      p[i] = P(r,-l);
    }
    p[m++] = P(n,-1);
    sort(p,p+m);
    di = 0;
    rep(i,m){
      l = -p[i].se; r = p[i].fi;
      while(di > 1){
        if(dl[di-2] < l) break;
        a = dl[di-1] - dr[di-2] & 1;
        rep(j,4){
          d[j][di] = (d[j&2][di-2]*d[(j&1)|(!a<<1)][di-1]+
                d[(j&2)|1][di-2]*d[(j&1)|(a<<1)][di-1])%mod;
        }
        rep(j,4) d[j][di-2] = d[j][di];
        dr[di-2] = dr[di-1];
        di--;
      }
      if(di > 0 && dl[di-1] >= l){
        a = ((dl[di-1] - l & 1)<<1) + (r - dr[di-1] & 1);
        d[0][di] = d[a][di-1];
        d[1][di] = d[a^1][di-1];
        d[2][di] = d[a^2][di-1];
        d[3][di] = (d[a][di-1]+d[a^3][di-1])%mod;
        rep(j,4) d[j][di-1] = d[j][di];
        dl[di-1] = l; dr[di-1] = r;
      } else {
        if(r - l & 1){
          d[0][di] = 1;
          d[1][di] = 0;
          d[2][di] = 0;
          d[3][di] = 2;
        } else {
          d[0][di] = 0;
          d[1][di] = 1;
          d[2][di] = 1;
          d[3][di] = 0;
        }
        dl[di] = l; dr[di] = r;
        di++;
      }
    }
    printf("%lld\n",d[3][0]);
  }
  return 0;
}