2018 GP of Poland G

mirror.cpp

#include <bits/stdc++.h>
const int MAXN = 100005;
using namespace std;
using lint = long long;
typedef pair<lint, lint> pi;
typedef long long lint;

struct seg{
	int x, l, r, num;
};

struct node{
	int l, r;
}pool[10000000];
int piv;

vector<pair<int, int>> EL, CL;

#define add_edge push_back
void init(int s, int e, int p){
	if(s == e) return;
	int m = (s+e)/2;
	pool[p].l = ++piv;
	pool[p].r = ++piv;
	EL.add_edge(pi(p, pool[p].l));
	EL.add_edge(pi(p, pool[p].r));
	init(s, m, pool[p].l);
	init(m+1, e, pool[p].r);
}

void add(int pos, int s, int e, int p, int cur, int v){
	if(s == e){
		EL.add_edge(pi(cur, v));
		return;
	}
	int m = (s+e)/2;
	if(pos <= m){
		pool[cur].l = ++piv;
		pool[cur].r = pool[p].r;
		EL.add_edge(pi(cur, pool[cur].l));
		EL.add_edge(pi(cur, pool[cur].r));
		add(pos, s, m, pool[p].l, pool[cur].l, v);
	}
	else{
		pool[cur].l = pool[p].l;
		pool[cur].r = ++piv;
		EL.add_edge(pi(cur, pool[cur].l));
		EL.add_edge(pi(cur, pool[cur].r));
		add(pos, m+1, e, pool[p].r, pool[cur].r, v);
	}
}

void upd(int s, int e, int ps, int pe, int p, int v){
	if(e < ps || pe < s) return;
	if(s <= ps && pe <= e){
		CL.add_edge(pi(v, p));
		return;
	}
	int pm = (ps+pe)/2;
	upd(s, e, ps, pm, pool[p].l, v);
	upd(s, e, pm+1, pe, pool[p].r, v);
}

int n, m;

void solve(vector<seg> l, vector<seg> r){
	vector<pi> ps[MAXN];
	for(auto &i : l){
		ps[i.l].push_back(pi(i.x, i.num));
	}
	int ptr = 0;
	int rt = ++piv;
	init(1, n, rt);
	for(int i=1; i<=n; i++){
		for(auto &j : ps[i]){
			int nxtrt = ++piv;
			add(j.first, 1, n, rt, nxtrt, j.second);
			rt = nxtrt;
		}
		while(ptr < r.size() && r[ptr].x == i){
			upd(r[ptr].l, r[ptr].r, 1, n, rt, r[ptr].num);
			ptr++;
		}
	}
}

vector<vector<int>> c0g;
vector<vector<int>> c1g;
vector<int> l[MAXN], r[MAXN];
bool vis[10000000];
int dis[10000000];
const int inf = 1e9;

struct qry{
	int s, e, x;
};

vector<pi> ev[MAXN];
vector<qry> qr[MAXN];
int ans[MAXN];

struct segtree{
	vector<int> pos[270000];
	vector<pi> bit[270000];
	int lim;
	void init(int n){
		for(lim = 1; lim <= n; lim <<= 1);
		for(int i=1; i<270000; i++){
			pos[i].push_back(-1);
			pos[i].push_back(inf);
		}
		for(int i=1; i<=n; i++){
			for(auto &j : ev[i]){
				for(int k=lim+j.first; k; k>>=1){
					pos[k].push_back(j.second);
				}
			}
		}
		for(int i=1; i<270000; i++){
			sort(pos[i].begin(), pos[i].end());
			pos[i].resize(unique(pos[i].begin(), pos[i].end()) - pos[i].begin());
			bit[i].resize(pos[i].size());
		}
	}
	void upd(int x, int v, int c){
		x += lim;
		while(x){
			auto l = lower_bound(pos[x].begin(), pos[x].end(), v) - pos[x].begin();
			while(l < bit[x].size()){
				bit[x][l].first += c;
				bit[x][l].second += 1ll * c * v;
				l += l & -l;
			}
			x >>= 1;
		}
	}
	pi add(pi a, pi b){
		return pi(a.first + b.first, a.second + b.second);
	}
	pi nq(int x, int v){
		auto l = lower_bound(pos[x].begin(), pos[x].end(), v + 1) - pos[x].begin() - 1;
		pi ans(0, 0);
		while(l){
			ans = add(ans, bit[x][l]);
			l -= l & -l;
		}
		return ans;
	}
	pi query(int s, int e, int l){
		s += lim;
		e += lim;
		pi ans(0, 0);
		while(s < e){
			if(s % 2 == 1) ans = add(ans, nq(s++, l));
			if(e % 2 == 0) ans = add(ans, nq(e--, l));
			s >>= 1;
			e >>= 1;
		}
		if(s == e) ans = add(ans, nq(s, l));
		return ans;
	}
}segtree;

lint solve(){
	segtree.init(n);
	lint ret = 0;
	for(int i=1; i<=n; i++) ans[i] = inf, segtree.upd(i, inf, 1);
	for(int i=1; i<=n; i++){
		for(auto &j : ev[i]){
			segtree.upd(j.first, ans[j.first], -1);
			segtree.upd(j.first, j.second, 1);
			ans[j.first] = j.second;
		}
		for(auto &j : qr[i]){
			if(j.x != inf){
				auto v = segtree.query(j.s, j.e, j.x);
				ret += v.second;
				ret += 1ll * j.x * (j.e - j.s + 1 - v.first);
			}
			else{
				auto v = segtree.query(j.s, j.e, inf - 1);
				ret += v.second;
			}
		}
	}
	return ret;
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i=1; i<=n; i++){
		l[i].push_back(0);
		l[i].push_back(n+1);
		r[i].push_back(0);
		r[i].push_back(n+1);
	}
	for(int i=0; i<m; i++){
		int x, y;
		scanf("%d %d",&x,&y);
		swap(x, y);
		l[x].push_back(y);
		r[y].push_back(x);
	}
	vector<seg> lv, rv;
	for(int i=1; i<=n; i++){
		sort(l[i].begin(), l[i].end());
		sort(r[i].begin(), r[i].end());
		for(int j=0; j<l[i].size()-1; j++){
			if(l[i][j] + 1 == l[i][j+1]) continue;
			lv.push_back({i, l[i][j] + 1, l[i][j+1] - 1, -1});
		}
		for(int j=0; j<r[i].size()-1; j++){
			if(r[i][j] + 1 == r[i][j+1]) continue;
			rv.push_back({i, r[i][j] + 1, r[i][j+1] - 1, -1});
		}
	}
	for(auto &i : lv) i.num = piv++;
	for(auto &i : rv) i.num = piv++;
	solve(lv, rv);
	solve(rv, lv);
	// so we made all graph?
	c0g.resize(piv + 1);
	c1g.resize(piv + 1);
	for(auto &i : EL){
		c0g[i.first].push_back(i.second);
	}
	for(auto &i : CL){
		c1g[i.first].push_back(i.second);
	}
	deque<int> dq;
	dq.push_back(0);
	memset(dis, 0x3f, sizeof(dis));
	dis[0] = 0;
	while(!dq.empty()){
		int x = dq.front();
		dq.pop_front();
		if(!vis[x]) vis[x] = 1;
		else continue;
		for(auto &i : c0g[x]){
			if(dis[i] > dis[x]){
				dis[i] = dis[x];
				dq.push_front(i);
			}
		}
		for(auto &i : c1g[x]){
			if(dis[i] > dis[x] + 1){
				dis[i] = dis[x] + 1;
				dq.push_back(i);
			}
		}
	}
	for(auto &k : lv){
		k.num = dis[k.num];
		if(k.num > 1e8) k.num = inf;
		ev[k.l].push_back(pi(k.x, k.num));
		ev[k.r+1].push_back(pi(k.x, inf));
	}
	for(auto &k : rv){
		k.num = dis[k.num];
		if(k.num > 1e8) k.num = inf;
		qr[k.x].push_back({k.l, k.r, k.num});
	}
	cout << solve() << endl;
}