Description

给定 \(n\) 条鱼，每条鱼有长度和颜色。你可以选出若干条鱼，需要满足最大长度小于最小长度的两倍。定义两种养鱼方案不同仅当它们三种颜色之一的出现次数不同，求不同的养鱼方案数。

对于 \(100\%\) 的数据，\(1\leq n\leq 5\times 10^5\)。

Solution

先按长度排序，然后双指针，找出所有极长合法子区间。设一个极长合法子区间红、绿、蓝三种颜色的鱼分别有 \(R,G,B\) 条，则三种颜色出现次数为 \((x,y,z)\) 且 \(x\leq R,y\leq G,z\leq B\) 的方案是合法的，因为你可以去掉一些鱼。

问题转化为给定一些 \((0\sim x,0\sim y,0\sim z)\) 的立方体，求体积并。

先对 \(z\) 那维扫描线，问题变成二维矩阵求面积并。乍一看十分不可做，但问题的关键在于下界为 \((0,0,0)\)。观察发现，面积并一定为阶梯型。

于是将其变为一维的序列，\(x\) 为下标，\(y\) 为值，根据上文的结论，序列单调不升。每次加入矩阵即将 \([1,x]\) 的值对 \(y\) 取 \(\max\)。可以以 \(x\) 为 \(R\)，找出第一个值 \(< y\) 的位置作为 \(L\)，将 \([L,R]\) 全部赋值为 \(y\)。

使用线段树二分容易在 \(\log n\) 的时间内完成一次加入，但我们可以用珂朵莉树更简单地完成。由于 \(R\) 已知，只需向左枚举删除的区间直到区间的值 \(\geq y\) 为止。其实，也可以用 set 只维护右端点，也十分简便。

时间复杂度 \(\mathcal{O}(n\log n)\)。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
namespace Milkcat {
	typedef long long LL;
    typedef pair<LL, char> pic;
	const int N = 1e6 + 5;
	struct node {
        LL l, r; mutable LL v;
        node(int L, int R = -1, int V = 0): l(L), r(R), v(V) {}
        bool operator < (const node& o) const { return l < o.l; }
        int size() const { return r - l + 1; }
    };
    typedef set<node>::iterator IT;
    LL n, ans, now, col[N]; pic a[N];
    vector<node> vec; set<node> s;
    IT split(int pos) {
        IT it = s.lower_bound(node(pos));
        if (it != s.end() && it->l == pos) return it;
        int L = (-- it)->l, R = it->r, V = it->v;
        s.erase(it), s.insert(node(L, pos - 1, V));
        return s.insert(node(pos, R, V)).first;
    }
    void assign(LL r, LL val = 0) {
        LL l = 0;
        for (IT it = prev(split(r + 1)); it->v < val; -- it) {
        	l = it->l, now -= it->v * it->size();
			if (it == s.begin()) break;
		}
		if (!l) return;
		IT itr = split(r + 1), itl = split(l);
		s.erase(itl, itr), s.insert(node(l, r, val)), now += val * (r - l + 1);
    }
    int main() {
    	cin >> n;
    	for (int i = 1; i <= n; i ++)
    		cin >> a[i].fi >> a[i].se;
    	sort(a + 1, a + 1 + n);
    	for (int l = 1, r = 0; l <= n; col[a[l].se] --, l ++) {
    		while (r + 1 <= n && a[r + 1].fi < a[l].fi * 2) r ++, col[a[r].se] ++;
    		vec.emplace_back(col['R'] + 1, col['G'] + 1, col['B'] + 1);
		}
		sort(vec.begin(), vec.end()), reverse(vec.begin(), vec.end());
		vec.push_back(node(0, 0, 0)), s.insert(node(1, n + 1, 0));
		for (int i = 0; i + 1 < vec.size(); i ++) {
			int x = vec[i].r, y = vec[i].v;
			assign(x, y), ans += now * (vec[i].l - vec[i + 1].l);
		}
		cout << ans - 1 << '\n';
        return 0;
    }
}
int main() {
	freopen("memory.in", "r", stdin);
	freopen("memory.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
    int T = 1;
    while (T --) Milkcat::main();
    return 0;
}