#1088267 (C++17) No.1698 Face to Face

提出ソース
結果

問題	No.1698 Face to Face
コンテスト
ユーザー	Zhang Letao
提出日時	2025-05-24 16:10:29
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	557 ms / 5,000 ms
コード長	10,843 bytes
コンパイル時間	2,517 ms
コンパイル使用メモリ	211,624 KB
実行使用メモリ	222,072 KB
最終ジャッジ日時	2025-05-24 16:10:47
合計ジャッジ時間	16,134 ms
ジャッジサーバーID （参考情報）	judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 45
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

namespace IO {
	const int maxn = 1 << 20;
	
	char ibuf[maxn], *iS, *iT, obuf[maxn], *oS = obuf;

	inline char gc() {
		return (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++) : *iS++);
	}

	template<typename T = int>
	inline T read() {
		char c = gc();
		T x = 0;
		bool f = 0;
		while (c < '0' || c > '9') {
			f |= (c == '-');
			c = gc();
		}
		while (c >= '0' && c <= '9') {
			x = (x << 1) + (x << 3) + (c ^ 48);
			c = gc();
		}
		return f ? ~(x - 1) : x;
	}
	
	inline int reads(char *s) {
		char c = gc();
		int len = 0;
		while (isspace(c)) {
			c = gc();
		}
		while (!isspace(c)) {
			s[len++] = c;
			c = gc();
		}
		return len;
	}

	inline void flush() {
		fwrite(obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	
	struct Flusher {
		~Flusher() {
			flush();
		}
	} AutoFlush;

	inline void pc(char ch) {
		if (oS == obuf + maxn) {
			flush();
		}
		*oS++ = ch;
	}

	template<typename T>
	inline void write(T x) {
		static char stk[64], *tp = stk;
		if (x < 0) {
			x = ~(x - 1);
			pc('-');
		}
		do {
			*tp++ = x % 10;
			x /= 10;
		} while (x);
		while (tp != stk) {
			pc((*--tp) | 48);
		}
	}
	
	template<typename T>
	inline void writesp(T x) {
		write(x);
		pc(' ');
	}
	
	template<typename T>
	inline void writeln(T x) {
		write(x);
		pc('\n');
	}
}

using IO::read;
using IO::reads;
using IO::write;
using IO::pc;
using IO::writesp;
using IO::writeln;

const int maxn = 100100;
const int logn = 20;

int n, a[maxn], b[maxn], p[maxn], lsa[maxn], rsa[maxn], lsb[maxn], rsb[maxn], ib[maxn], c[maxn], ia[maxn], ip[maxn], ic[maxn];
int stk[maxn], top, ans[maxn];

int la[maxn], ra[maxn], lb[maxn], rb[maxn], st1[maxn], ed1[maxn], st2[maxn], ed2[maxn], tim, fa[logn][maxn], fb[logn][maxn];
pii f1[logn][maxn], f2[logn][maxn];

inline pii qmax(pii f[logn][maxn], int l, int r) {
	int k = __lg(r - l + 1);
	return max(f[k][l], f[k][r - (1 << k) + 1]);
}

void dfs(int u) {
	st1[u] = ++tim;
	la[u] = ra[u] = u;
	if (lsa[u]) {
		dfs(lsa[u]);
		la[u] = la[lsa[u]];
	}
	if (rsa[u]) {
		dfs(rsa[u]);
		ra[u] = ra[rsa[u]];
	}
	ed1[u] = tim;
}

void dfs2(int u) {
	st2[u] = ++tim;
	lb[u] = rb[u] = u;
	if (lsb[u]) {
		dfs2(lsb[u]);
		lb[u] = lb[lsb[u]];
	}
	if (rsb[u]) {
		dfs2(rsb[u]);
		rb[u] = rb[rsb[u]];
	}
	ed2[u] = tim;
}

int rt[maxn], ls[maxn * 20], rs[maxn * 20], val[maxn * 20], nt;

int build(int l, int r) {
	int rt = ++nt;
	if (l == r) {
		return rt;
	}
	int mid = (l + r) >> 1;
	ls[rt] = build(l, mid);
	rs[rt] = build(mid + 1, r);
	return rt;
}

int update(int rt, int l, int r, int x) {
	int u = ++nt;
	ls[u] = ls[rt];
	rs[u] = rs[rt];
	val[u] = val[rt] + 1;
	if (l == r) {
		return u;
	}
	int mid = (l + r) >> 1;
	if (x <= mid) {
		ls[u] = update(ls[u], l, mid, x);
	} else {
		rs[u] = update(rs[u], mid + 1, r, x);
	}
	return u;
}

int query(int u, int v, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) {
		return val[v] - val[u];
	}
	int mid = (l + r) >> 1, res = 0;
	if (ql <= mid) {
		res += query(ls[u], ls[v], l, mid, ql, qr);
	}
	if (qr > mid) {
		res += query(rs[u], rs[v], mid + 1, r, ql, qr);
	}
	return res;
}

inline int calc(int u, int v) {
	return query(rt[st1[u] - 1], rt[ed1[u]], 1, n, st2[v], ed2[v]);
}

inline void upd(int l, int r, int x) {
	if (l > r) {
		return;
	}
	ans[l] += x;
	ans[r + 1] -= x;
}

struct DSU {
	int fa[maxn];
	bool vis[maxn];
	
	int find(int x) {
		return fa[x] == x ? x : fa[x] = find(fa[x]);
	}
	
	inline void init() {
		for (int i = 1; i <= n; ++i) {
			fa[i] = i;
		}
	}
} D1, D2;

inline void upd1(int u, int k, int o) {
	int x = la[u];
	int y = D2.find(x);
	if (D2.vis[y] && lb[y] < la[u] && rb[y] < ra[u]) {
		ans[k] += min(rb[y] - la[u] + 1, calc(u, y)) * o;
	}
	x = ra[u];
	y = D2.find(x);
	if (D2.vis[y] && la[u] < lb[y] && ra[u] < rb[y]) {
		ans[k] += min(ra[u] - lb[y] + 1, calc(u, y)) * o;
	}
}

inline void upd2(int u, int k, int o) {
	int x = lb[u];
	int y = D1.find(x);
	if (D1.vis[y] && la[y] < lb[u] && ra[y] < rb[u]) {
		ans[k] += min(ra[y] - lb[u] + 1, calc(y, u)) * o;
	}
	x = rb[u];
	y = D1.find(x);
	if (D1.vis[y] && lb[u] < la[y] && rb[u] < ra[y]) {
		ans[k] += min(rb[u] - la[y] + 1, calc(y, u)) * o;
	}
}

namespace SGT {
	int sa[maxn << 6], sb[maxn << 6], sab[maxn << 6], ls[maxn << 6], rs[maxn << 6], nt;
	
	inline void init() {
		mems(sa, 0);
		mems(sb, 0);
		mems(sab, 0);
		mems(ls, 0);
		mems(rs, 0);
		nt = 0;
	}
	
	inline void pushup(int x) {
		sa[x] = sa[ls[x]] + sa[rs[x]];
		sb[x] = sb[ls[x]] + sb[rs[x]];
		sab[x] = sab[ls[x]] + sab[rs[x]] + sa[ls[x]] * sb[rs[x]];
	}
	
	void update1(int &rt, int l, int r, int x, int y) {
		if (!rt) {
			rt = ++nt;
		}
		if (l == r) {
			sa[rt] += y;
			sab[rt] += sb[rt] * y;
			return;
		}
		int mid = (l + r) >> 1;
		(x <= mid) ? update1(ls[rt], l, mid, x, y) : update1(rs[rt], mid + 1, r, x, y);
		pushup(rt);
	}
	
	void update2(int &rt, int l, int r, int x, int y) {
		if (!rt) {
			rt = ++nt;
		}
		if (l == r) {
			sb[rt] += y;
			sab[rt] += sa[rt] * y;
			return;
		}
		int mid = (l + r) >> 1;
		(x <= mid) ? update2(ls[rt], l, mid, x, y) : update2(rs[rt], mid + 1, r, x, y);
		pushup(rt);
	}
	
	int merge(int u, int v, int l, int r) {
		if (!u || !v) {
			return u | v;
		}
		if (l == r) {
			sa[u] += sa[v];
			sb[u] += sb[v];
			sab[u] = sa[u] * sb[u];
			return u;
		}
		int mid = (l + r) >> 1;
		ls[u] = merge(ls[u], ls[v], l, mid);
		rs[u] = merge(rs[u], rs[v], mid + 1, r);
		pushup(u);
		return u;
	}
}

vector<pii> md[maxn];
int tr[maxn];

void dfs3(int u) {
	for (int v : {lsb[u], rsb[u]}) {
		if (!v) {
			continue;
		}
		dfs3(v);
		tr[u] = SGT::merge(tr[u], tr[v], 1, n);
	}
	SGT::update2(tr[u], 1, n, ic[st2[u]], 1);
	for (pii p : md[u]) {
		SGT::update1(tr[u], 1, n, st1[p.fst], p.scd);
		if (ed1[p.fst] < n) {
			SGT::update1(tr[u], 1, n, ed1[p.fst] + 1, -p.scd);
		}
	}
	upd(b[u], b[fb[0][u]] - 1, SGT::sab[tr[u]]);
}

void dfs4(int u) {
	for (int v : {lsa[u], rsa[u]}) {
		if (!v) {
			continue;
		}
		dfs4(v);
		tr[u] = SGT::merge(tr[u], tr[v], 1, n);
	}
	SGT::update2(tr[u], 1, n, c[st1[u]], 1);
	for (pii p : md[u]) {
		SGT::update1(tr[u], 1, n, st2[p.fst], p.scd);
		if (ed2[p.fst] < n) {
			SGT::update1(tr[u], 1, n, ed2[p.fst] + 1, -p.scd);
		}
	}
	upd(a[u], a[fa[0][u]] - 1, SGT::sab[tr[u]]);
}

void solve() {
	n = read();
	for (int i = 1; i <= n; ++i) {
		a[i] = read();
		ia[a[i]] = i;
	}
	for (int i = 1; i <= n; ++i) {
		b[i] = read();
		ib[b[i]] = i;
	}
	a[0] = b[0] = n + 1;
	for (int i = 1; i <= n; ++i) {
		int k = top;
		while (k && a[stk[k]] < a[i]) {
			--k;
		}
		if (k) {
			rsa[stk[k]] = i;
		}
		if (k < top) {
			lsa[i] = stk[k + 1];
		}
		stk[top = (++k)] = i;
	}
	int rt1 = stk[1];
	top = 0;
	for (int i = 1; i <= n; ++i) {
		int k = top;
		while (k && b[stk[k]] < b[i]) {
			--k;
		}
		if (k) {
			rsb[stk[k]] = i;
		}
		if (k < top) {
			lsb[i] = stk[k + 1];
		}
		stk[top = (++k)] = i;
	}
	int rt2 = stk[1];
	tim = 0;
	dfs(rt1);
	tim = 0;
	dfs2(rt2);
	for (int i = 1; i <= n; ++i) {
		p[i] = read();
		ip[p[i]] = i;
	}
	for (int i = 1; i <= n; ++i) {
		f1[0][i] = mkp(a[i], i);
		f2[0][i] = mkp(b[i], i);
	}
	for (int j = 1; (1 << j) <= n; ++j) {
		for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
			f1[j][i] = max(f1[j - 1][i], f1[j - 1][i + (1 << (j - 1))]);
			f2[j][i] = max(f2[j - 1][i], f2[j - 1][i + (1 << (j - 1))]);
		}
	}
	for (int i = 1; i <= n; ++i) {
		c[st1[i]] = st2[ib[p[a[i]]]];
	}
	for (int i = 1; i <= n; ++i) {
		ic[c[i]] = i;
	}
	rt[0] = build(1, n);
	for (int i = 1; i <= n; ++i) {
		rt[i] = update(rt[i - 1], 1, n, c[i]);
	}
	for (int i = 1; i <= n; ++i) {
		if (lsa[i]) {
			fa[0][lsa[i]] = i;
		}
		if (rsa[i]) {
			fa[0][rsa[i]] = i;
		}
		if (lsb[i]) {
			fb[0][lsb[i]] = i;
		}
		if (rsb[i]) {
			fb[0][rsb[i]] = i;
		}
	}
	for (int j = 1; j <= 18; ++j) {
		for (int i = 1; i <= n; ++i) {
			fa[j][i] = fa[j - 1][fa[j - 1][i]];
			fb[j][i] = fb[j - 1][fb[j - 1][i]];
		}
	}
	D1.init();
	D2.init();
	for (int k = 1; k <= n; ++k) {
		int u = ia[k];
		if (lsa[u]) {
			upd1(lsa[u], k, -1);
			D1.fa[lsa[u]] = u;
		}
		if (rsa[u]) {
			upd1(rsa[u], k, -1);
			D1.fa[rsa[u]] = u;
		}
		upd1(u, k, 1);
		D1.vis[u] = 1;
		u = ib[k];
		if (lsb[u]) {
			upd2(lsb[u], k, -1);
			D2.fa[lsb[u]] = u;
		}
		if (rsb[u]) {
			upd2(rsb[u], k, -1);
			D2.fa[rsb[u]] = u;
		}
		upd2(u, k, 1);
		D2.vis[u] = 1;
	}
	for (int i = 1; i <= n; ++i) {
		if (p[a[i]] == b[i]) {
			upd(1, min(a[i], b[i]) - 1, 1);
		}
		int u = i;
		for (int j = 18; ~j; --j) {
			if (fb[j][u]) {
				int v = fb[j][u];
				if (!(st2[v] <= st2[ib[p[a[i]]]] && st2[ib[p[a[i]]]] <= ed2[v])) {
					u = v;
				}
			}
		}
		if (!(st2[u] <= st2[ib[p[a[i]]]] && st2[ib[p[a[i]]]] <= ed2[u])) {
			u = fb[0][u];
		}
		upd(b[u], a[i] - 1, 1);
		u = i;
		for (int j = 18; ~j; --j) {
			if (fa[j][u]) {
				int v = fa[j][u];
				if (!(st1[v] <= st1[ia[ip[b[i]]]] && st1[ia[ip[b[i]]]] <= ed1[v])) {
					u = v;
				}
			}
		}
		if (!(st1[u] <= st1[ia[ip[b[i]]]] && st1[ia[ip[b[i]]]] <= ed1[u])) {
			u = fa[0][u];
		}
		upd(a[u], b[i] - 1, 1);
	}
	for (int u = 1; u <= n; ++u) {
		int v = qmax(f2, la[u], ra[u]).scd;
		if (b[v] < a[u]) {
			for (int j = 18; ~j; --j) {
				if (fb[j][v] && b[fb[j][v]] < a[u]) {
					v = fb[j][v];
				}
			}
			upd(max(a[u], b[v]), min(a[fa[0][u]], b[fb[0][v]]) - 1, calc(u, v));
			v = fb[0][v];
		}
		if (b[v] <= a[fa[0][u]] - 1) {
			int w = v;
			for (int j = 18; ~j; --j) {
				if (fb[j][w] && b[fb[j][w]] <= a[fa[0][u]] - 1) {
					w = fb[j][w];
				}
			}
			upd(max(a[u], b[w]), min(a[fa[0][u]], b[fb[0][w]]) - 1, calc(u, w));
			if (w != v) {
				md[v].pb(u, 1);
				md[w].pb(u, -1);
			}
		}
	}
	dfs3(rt2);
	mems(tr, 0);
	for (int i = 1; i <= n; ++i) {
		vector<pii>().swap(md[i]);
	}
	for (int u = 1; u <= n; ++u) {
		int v = qmax(f1, lb[u], rb[u]).scd;
		if (lb[u] == la[v] && ra[v] == rb[u]) {
			upd(max(a[v], b[u]), min(a[fa[0][v]], b[fb[0][u]]) - 1, -calc(v, u));
		}
		if (a[v] < b[u]) {
			for (int j = 18; ~j; --j) {
				if (fa[j][v] && a[fa[j][v]] < b[u]) {
					v = fa[j][v];
				}
			}
			upd(max(a[v], b[u]), min(a[fa[0][v]], b[fb[0][u]]) - 1, calc(v, u));
			v = fa[0][v];
		}
		if (a[v] <= b[fb[0][u]] - 1) {
			int w = v;
			for (int j = 18; ~j; --j) {
				if (fa[j][w] && a[fa[j][w]] <= b[fb[0][u]] - 1) {
					w = fa[j][w];
				}
			}
			upd(max(a[w], b[u]), min(a[fa[0][w]], b[fb[0][u]]) - 1, calc(w, u));
			if (w != v) {
				md[v].pb(u, 1);
				md[w].pb(u, -1);
			}
		}
	}
	SGT::init();
	dfs4(rt1);
	for (int i = 1; i <= n; ++i) {
		ans[i] += ans[i - 1];
		writeln(ans[i]);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}
yukicoder

結果

ソースコード
