CF1677E Tokitsukaze and Beautiful Subsegments

CF1677E Tokitsukaze and Beautiful Subsegments

好题.

对于区间最大值,Consider monotonic stack maintenance,记一个数 $a_i$ The first number on the left and right that is larger than him is $L_i$ 和 $R_i$.

则对于区间 $[l,r]$ 满足 $L_i<l\le r<R_i$,有 ${\max }_{k=l}^r{a}_k=a_i$.

对于每个 $a_i$,We can try to determine the range of the left endpoint of the interval $[L,R]$,初始 $L=L_i+1$,$R=L_i$.

接着,枚举 $a_i$ 的因数 $x,y$,判断是否 $L_i<po{s}_x,po{s}_y\le i$,i.e. in range,然后更新 $R=\min (po{s}_x,po{s}_y)$,总时间复杂度 $\mathcal{O}(\sum \sqrt{a_i})$.

Then enumerate the right endpoints of the interval,Calculate the product of $a_i$ 的数的位置,判断是否在范围内,更新 $R$,记录.

This is recorded $(L,R,r)$,表示右端点为 $r$,左端点为 $[L,R]$ The interval is beautiful.

考虑扫描线,将询问离线,右端点升序,Put the right endpoint as $i$ All triples of are added to the segment tree,i.e. interval plus $1$.

时间复杂度 $\mathcal{O}(n^2\log n)$.

考虑优化,每次枚举 $[i,R_i]$ 和 $[L_i,i]$ Medium length is small,记录三元组,This way the time complexity is amortized $\mathcal{O}(n{\log }^{2}n)$.

#include<bits/stdc++.h>

using namespace std;

#define int long long
typedef long long ll;

#define ha putchar(' ')
#define he putchar('\n')

inline int read() {
    
	int x = 0, f = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
    
		if (c == '-')
			f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9')
		x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return x * f;
}

inline void write(ll x) {
    
	if (x < 0) {
    
		putchar('-');
		x = -x;
	}
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + 48);
}

const int _ = 1e6 + 10;

int n, q, s[_], t, a[_], pos[_], L[_], R[_], sz[_ << 2], tag[_ << 2], tr[_ << 2], as[_];

struct abc {
    
	int l, r, id;
} qr[_];

bool cmp(abc a, abc b) {
    
	return a.r < b.r;
}

bool cmp2(abc a, abc b) {
    
	return a.l > b.l;
}

vector<pair<int, int>> d[_], d2[_];

void build(int o, int l, int r) {
    
	sz[o] = (r - l + 1), tr[o] = tag[o] = 0;
	if (l == r) return;
	int mid = (l + r) >> 1;
	build(o << 1, l, mid), build(o << 1 | 1, mid + 1, r);
}

void pushdown(int o) {
    
	if (tag[o]) {
    
		tr[o << 1] += sz[o << 1] * tag[o];
		tr[o << 1 | 1] += sz[o << 1 | 1] * tag[o];
		tag[o << 1] += tag[o];
		tag[o << 1 | 1] += tag[o];
		tag[o] = 0;
	}
}

void upd(int o, int l, int r, int L, int R, int k) {
    
	if (L <= l && r <= R) {
    
		tr[o] += sz[o] * k, tag[o] += k;
		return;
	}
	pushdown(o);
	int mid = (l + r) >> 1;
	if (L <= mid) upd(o << 1, l, mid, L, R, k);
	if (R > mid) upd(o << 1 | 1, mid + 1, r, L, R, k);
	tr[o] = tr[o << 1] + tr[o << 1 | 1];
}

int qry(int o, int l, int r, int L, int R) {
    
	if (L <= l && r <= R) return tr[o];
	pushdown(o);
	int mid = (l + r) >> 1, res = 0;
	if (L <= mid) res = qry(o << 1, l, mid, L, R);
	if (R > mid) res += qry(o << 1 | 1, mid + 1, r, L, R);
	tr[o] = tr[o << 1] + tr[o << 1 | 1];
	return res;
}

signed main() {
    
	n = read(), q = read();
	for (int i = 1; i <= n; ++i) a[i] = read(), pos[a[i]] = i;
	t = 0;
	for (int i = 1; i <= n; ++i) {
    
		while (t > 0 && a[s[t]] < a[i]) t--;
		L[i] = s[t];
		s[++t] = i;
	}
	t = 0, s[0] = n + 1;
	for (int i = n; i >= 1; --i) {
    
		while (t > 0 && a[s[t]] < a[i]) t--;
		R[i] = s[t];
		s[++t] = i;
	}
	for (int i = 1; i <= q; ++i)
		qr[i].l = read(), qr[i].r = read(), qr[i].id = i;
	for (int i = 1; i <= n; ++i) {
    
		int l, r;
		if (R[i] - i <= i - L[i]) {
    
			r = L[i];
			for (int j = 1; j * j <= a[i]; ++j) {
    
				if (a[i] % j != 0) continue;
				int fx = pos[j], fy = pos[a[i] / j];
				if (fx == fy) continue;
				if (fx > fy) swap(fx, fy);
				if (fx > L[i] && fy <= i) r = max(r, fx);
			}
			for (int j = i; j < R[i]; ++j) {
    
				if (a[i] % a[j] == 0) {
    
					int nw = a[i] / a[j];
					if (pos[nw] == j) continue;
					if (pos[nw] > L[i] && pos[nw] < j) {
    
						r = max(r, pos[nw]);
						r = min(r, i);
					}
				}
				if (L[i] < r) d[j].push_back({
    L[i] + 1, r});
			}
		} else {
    
			l = R[i];
			for (int j = 1; j * j <= a[i]; ++j) {
    
				if (a[i] % j != 0) continue;
				int fx = pos[j], fy = pos[a[i] / j];
				if (fx == fy) continue;
				if (fx > fy) swap(fx, fy);
				if (fy < R[i] && fx >= i) l = min(l, fy);
			}
			for (int j = i; j > L[i]; --j) {
    
				if (a[i] % a[j] == 0) {
    
					int nw = a[i] / a[j];
					if (pos[nw] == j) continue;
					if (pos[nw] > j && pos[nw] < R[i]) {
    
						l = min(l, pos[nw]);
						l = max(l, i);
					}
				}
				if (l < R[i]) d2[j].push_back({
    l, R[i] - 1});
			}
		}
	}
	sort(qr + 1, qr + q + 1, cmp);
	build(1, 1, n);
	int k = 1;
	for (int i = 1; i <= n; ++i) {
    
		for (auto v : d[i]) upd(1, 1, n, v.first, v.second, 1);
		for (; qr[k].r == i && k <= q; ++k)
			as[qr[k].id] += qry(1, 1, n, qr[k].l, qr[k].r);
	}
	sort(qr + 1, qr + q + 1, cmp2);
	build(1, 1, n);
	k = 1;
	for (int i = n; i >= 1; --i) {
    
		for (auto v : d2[i]) upd(1, 1, n, v.first, v.second, 1);
		for (; qr[k].l == i && k <= q; ++k)
			as[qr[k].id] += qry(1, 1, n, qr[k].l, qr[k].r);
	}
	for (int i = 1; i <= q; ++i) write(as[i]), he;
	return 0;
}