XCPC wiki - 二分、分治

三分法求凸函数最值

求类似开口朝上的二次函数的最小值：

auto check = [&](int mid) {
    // 计算...
    return /* f(mid) */;
};

int lt = /* 下界 */, rt =  /* 上界 */ + 1;        // 切记+1
while (lt < rt) {
    int lm = lt + (rt - lt) / 3, rm = lt + (rt - lt) * 2 / 3;
    if (check(lm) < check(rm)) lt = lm + 1;
    else rt = rm;
}
// now lt = rt
cout << "The function reaches its minimum value of "
     << check(lt) << " at " << lt << '\n';

求类似开口朝下的二次函数的最大值，只需将 if 中的小于号改成大于号。

2024 杭电多校 3011 - 抓拍

[[…/contests/2024杭电多校/2024-07-26：2024“钉耙编程”中国大学生算法设计超级联赛（3）#3011 - 抓拍|2024-07-26：2024“钉耙编程”中国大学生算法设计超级联赛（3）]]

题意$n$ 个点初始位于$(x_i, y_i)$，以每秒$1$ 米的速度向东南西北中某一方向移动。在非负整数时间时，用矩形将所有点覆盖。无限长的时间内，求矩形最小周长。

思路 注意到答案有凸性，三分答案，时间复杂度$\Theta(n\log n)$。

struct node {
    ll x, y;
    int dx, dy;
} a[N];

void eachT() {
    int n = read();
    for (int i = 1; i <= n; ++i) {
        a[i].x = read(), a[i].y = read();
        char c; do c = getchar(); while (c != 'N' && c != 'S' && c != 'E' && c != 'W');
        if (c == 'W') a[i].dx = -1, a[i].dy = 0;
        if (c == 'S') a[i].dx = 0, a[i].dy = -1;
        if (c == 'N') a[i].dx = 0, a[i].dy = 1;
        if (c == 'E') a[i].dx = 1, a[i].dy = 0;
    }

    ll lt = 0, rt = 2e9;
    auto check = [&](ll t) {
        ll xmax = -INF, ymax = -INF, xmin = INF, ymin = INF;
        for (int i = 1; i <= n; ++i) {
            chmax(xmax, a[i].x + t * a[i].dx);
            chmax(ymax, a[i].y + t * a[i].dy);
            chmin(xmin, a[i].x + t * a[i].dx);
            chmin(ymin, a[i].y + t * a[i].dy);
        }
        return xmax - xmin + ymax - ymin << 1;
    };
    while (lt < rt) {
        int lm = lt + (rt - lt) / 3, rm = lt + (rt - lt) * 2 / 3;
        if (check(lm) > check(rm)) lt = lm + 1;
        else rt = rm;
    }
    printf("%lld\n", check(lt));
}

本题的$\Theta(1)$ 方法是，找$8$ 个决策点：

void chmax(ll& a, ll b) { if (a < b) a = b; return; }
void chmin(ll& a, ll b) { if (a > b) a = b; return; }
const ll INF = 2e12;
ll ans = INF;
ll topN = -INF, topS = -INF, botN = INF, botS = INF;
ll lefW = INF, lefE = INF, ritW = -INF, ritE = -INF;
ll topb = -INF, botb = INF, lefb = INF, ritb = -INF;

void check(ll t) {
    ll xmin = std::min(lefW - t, std::min(lefE + t, lefb));
    ll xmax = std::max(ritE + t, std::max(ritW - t, ritb));
    ll ymin = std::min(botS - t, std::min(botN + t, botb));
    ll ymax = std::max(topN + t, std::max(topS - t, topb));
    ll res = xmax - xmin + ymax - ymin << 1;
    ans = std::min(ans, res);
    return;
}

void check(int a, int b) {
    if (a > b) a += b, b = a + 1 >> 1, a >>= 1;
    if (a < 0) a = 0;
    if (b < 0) b = 0;
    return check(a), check(b);
}

void eachT() {
    for (int n = read(); n--; ) {
        ll x = read(), y = read();
        char c; do c = getchar(); while (c != 'N' && c != 'S' && c != 'E' && c != 'W');

        if (c == 'E' || c == 'W') {
            chmax(topb, y), chmin(botb, y);
            if (c == 'E') chmin(lefE, x), chmax(ritE, x);
            if (c == 'W') chmin(lefW, x), chmax(ritW, x);
        }
        else if (c == 'N' || c == 'S') {
            chmax(ritb, x), chmin(lefb, x);
            if (c == 'N') chmin(botN, y), chmax(topN, y);
            if (c == 'S') chmin(botS, y), chmax(topS, y);
        }
    }

    check(topS - topb, topb - topN);
    check(botb - botN, botS - botb);
    check(ritW - ritb, ritb - ritE);
    check(lefb - lefE, lefW - lefb);

    printf("%lld\n", ans);
}

二分法求单调函数最值

CF1996F. Bomb

void eachT() {
    int n = read(), k = read();
    vector<int> a(n), b(n);
    for (auto& it : a) it = read();
    for (auto& it : b) it = read();

    int l = 1, r = 1e9 + 1, m = -1;
    auto check = [&](int x) {
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            cnt += (a[i] < x) ? 0 : (a[i] - x) / b[i] + 1;
            if (cnt > k) return 0;
        }
        return 1;
    };
    while (l < r) check(m = l + r >> 1) ? r = m : l = m + 1;

    ll res = 0;
    int x = l;
    for (int i = 0; i < n; ++i) {
        ll num = (a[i] < x) ? 0 : (a[i] - x) / b[i] + 1;
        res += num * a[i] - 1ll * num * (num - 1) / 2 * b[i];
        a[i] -= num * b[i];
        k -= num;
    }

    if (k > n) k = n;
    sort(a.begin(), a.end(), greater<>());
    for (int i = 0; i < k; ++i) {
        if (a[i] > 0) res += a[i];
    }
    printf("%lld\n", res);
}

VJwin3B - Rental Service S - UPSOLVE

题意 给出一些牛，可以将牛租出获得收益，每个邻居只能租一头牛，且租不同的牛的租金是固定的已经给出，也可以卖牛奶给商铺获得收益，每个商铺有最大购买量，单价已经给出，问这个收益的最大值。

思路 把产量少的租出，且租给出价高的，剩下产量高的卖出，卖给单价高的商铺。枚举分界线。

const ll N = 1e6 + 7;
ll a[N], sa[N], c[N], sc[N], sb[N], sbb[N];
struct node {
	ll p, a;
	bool operator < (const node&b) const { return p > b.p; }
} b[N];

void eachT() {
	int n = read(), m = read(), r = read();  // 牛 商店 邻居
	for (int i = 1; i <= n; ++i) a[i] = read();
	for (int i = 1; i <= m; ++i) b[i].a = read(), b[i].p = read();
	for (int i = 1; i <= r; ++i) c[i] = read();
	sort(a + 1, a + n + 1, greater<>());
	sort(b + 1, b + m + 1);
	sort(c + 1, c + r + 1, greater<>());
	for (int i = 1; i <= n; ++i) sa[i] = sa[i - 1] + a[i];
	for (int i = 1; i <= m; ++i) sb[i] = sb[i - 1] + b[i].a; //前i个商店所需容量总和
	for (int i = 1; i <= m; ++i) sbb[i] = sbb[i - 1] + b[i].a * b[i].p; //刚好满足前i个商店可获得的利润
	for (int i = 1; i <= r; ++i) sc[i] = sc[i - 1] + c[i];
	ll ans = 0;
	auto sell = [&](int t) {
		int p = lower_bound(sb + 1, sb + m + 1, sa[t]) - sb;
		return sbb[p - 1] + (sa[t] - sb[p - 1]) * b[p].p;
	};
	auto rent = [&](int t) {
		return sc[t];
	};
	for (int i = max(0, n - m); i <= min(r, n); ++i) {
		ans = max(ans, sell(n - i) + rent(i));
	}
	printf("%lld\n", ans);
}

基于单调性，可以省略二分：

const ll N = 1e6 + 7;
ll a[N], sa[N], c[N], sc[N], sb[N], sbb[N];
struct node {
	ll p, a;
	bool operator < (const node& b) const { return p > b.p; }
} b[N];

void eachT() {
	int n = read(), m = read(), r = read();  // 牛 商店 邻居
	for (int i = 1; i <= n; ++i) a[i] = read();
	for (int i = 1; i <= m; ++i) b[i].a = read(), b[i].p = read();
	for (int i = 1; i <= r; ++i) c[i] = read();
	sort(a + 1, a + n + 1, greater<>());
	sort(b + 1, b + m + 1);
	sort(c + 1, c + r + 1, greater<>());
	for (int i = 1; i <= r; ++i) sc[i] = sc[i - 1] + c[i];
	ll ans = 0, sumsell = 0;
	for (int i = 1, mj = 1; i <= n; ++i) {
		ll eachsell = 0;
		ll left = a[i];
		while (left >= b[mj].a && mj <= m) {
			eachsell += b[mj].a * b[mj].p;
			left -= b[mj].a;
			++mj;
		}
		eachsell += left * b[mj].p;
		b[mj].a -= left;
		sumsell += eachsell;
		ans = max(ans, sumsell + sc[n - i]);
	}
	printf("%lld\n", ans);
}

VJwin1H - 跳石头 - UPSOLVE

题意 最多移走一些石头，使最短跳跃距离最大。

思路 对最短跳跃距离二分。这是由于，答案对于最短跳跃距离有单调性，单调性在于，如果调大跳跃距离，需要移走的石头会增加，反之减小。那么，如果需要移走的数量大于期望值，就调小跳跃距离，并可以将这个距离重新定义为二分上界，如果需要移走的数量小于期望值，就重新定义二分下界。剩下相等的情况，当前最短跳跃距离已经複合题意，因为要找最短跳跃距离的最大值，只要增大跳跃距离接着搜索，也即重新定义二分下界，所以等号并与后者。

const ll maxN = 5e4 + 7;
int a[maxN];
int n, m;

bool half(int x) { // 目前嘗試的距離
	int now = 0, cnt = 0; // 移走的數量
	for (int i = 0; i <= n; ++i) {
		if (a[i] - now < x) ++cnt; // 兩個石頭的距離小於期望值，移走石頭
		else now = a[i]; // 跳過去
	}
	return cnt <= m; // 需要移走的數量大於期望值就不滿足條件
}

void eachT() {
	int l;
	scanf("%d %d %d", &l, &n, &m);
	for (int i = 0; i < n; ++i) { scanf("%d", &a[i]); }
	int lt = 0, rt = a[n] = l;
	while (lt <= rt) {
		int mid = (lt + rt) / 2;
		if (half(mid)) lt = mid + 1;
		else rt = mid - 1;
	}
	printf("%d\n", lt - 1);
}

VJwin1J - Monthly Expense - UPSOLVE

题意 将数组划分为指定的组数，每组元素和的最大值尽可能小。

思路 依旧是二分，对每组元素和的最大值二分。这里解释等号，和上一题类似，需要二分的值尽可能小，那等号就并与减小上界的情况中。

注意 二分前，最小值务必考虑，不能草率地赋值为 0 或 1，否则例如，设置搜索值为 4，组数为 4，那么 {1,2,3,4,5} 返回的 cnt=4，即 [1,2][3][4][5]，程序认为它合题，但实际上不是。所以需要在二分前准确设置最小值，或者在判断时增加 if(a[i]>x) return 0;。

bool half(ll x) {
    int s = 0, cnt = 1;
    for (int i = 0; i < n; ++i)
        if ((s += a[i]) > x) ++cnt, s = a[i];
    return cnt > m;
}

void eachT() {
	int lt = 0, rt = 0;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; ++i) {
	    scanf("%d", &a[i]);
	    lt = max(lt, a[i]), rt += a[i];
	}
	while (lt <= rt) {
	    int mid = (lt + rt) / 2;
	    if (half(mid)) lt = mid + 1;
	    else rt = mid - 1;
	}
	printf("%d\n", lt);
}

VJwin1I - 聪明的质监员 - UPSOLVE

题意 选出一个参数$W$，在每个给定的$m$ 个区间$[l_i,r_i]$ 上计算$y=\sum\limits_{i=1}^m\Big(\sum\limits_{j=l_i}^{r_i}[w_j \ge W] \times \sum\limits_{j=l_i}^{r_i}[w_j \ge W]v_j\Big)$，使$|y-s|$ 最小。

思路 对参数参数$W$ 二分，易于判断，若$y>s$，需要增大下界，反之减小上界，不同的是，每次判断时计算$|y-s|$ 的值。

bool half(int x) {
    for (int i = 1; i <= n; ++i) {
        s1[i] = s1[i - 1] + (w[i] >= x);
        s2[i] = s2[i - 1] + (w[i] >= x) * v[i];
    } // 前缀和预处理
    ll y = 0;
    for (int i = 1; i <= m; ++i)
        y += (s1[r[i]] - s1[l[i] - 1]) * (s2[r[i]] - s2[l[i] - 1]);
    ans = min(ans, abs(y - s));
    return y > s;
}

VJwin9I - Microtransactions (hard version)

题意 每天的余额会增加一元，一种盲盒在其优惠的那一天可用一元买下，否则两元，问至少几天能买下所有盲盒。

思路 贪心：有多日优惠就拖到最后一个优惠再买。

int n, m;
ll sumneed; // 需求总数
ll daySale[maxN]; // 每天优惠的有几个
ll need[maxN]; // 需求量
std::vector<int> saleDay[maxN]; // 优惠日期

// 二分判断函数
bool half(int x) { // x天能买下
    memset(daySale, 0, sizeof daySale);
    if (x >= 2 * sumneed) return 0; // 能买下 减小上界
    for (int i = 1; i <= n; ++i) {
        auto p = std::lower_bound(saleDay[i].begin(), saleDay[i].end(), x, std::greater<ll>()); // 前x天的优惠才算数 二分找
        if (!(p == saleDay[i].end())) {
            daySale[*p] += need[i]; // 这一天需要这么多
        }
    } // 贪心：有多日优惠就拖到最后一个优惠再买

    // 以下模拟
    ll discount = 0, nowmoney = 0; // 总优惠和现有钱数
    for (int i = 1; i < maxN; ++i) { // 遍历天数
        ++nowmoney;
        discount += min(daySale[i], nowmoney);
        nowmoney -= min(daySale[i], nowmoney);
    }
    if (x >= 2 * sumneed - discount) return 0; // 能买下 减小上界
    return 1; // 不能 增大上界
}

void eachT() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &need[i]);
        sumneed += need[i]; // 没有优惠需要的钱数
    }
    while (m--) {
        int x, y;
        scanf("%d%d", &x, &y);
        saleDay[y].push_back(x); // 每个盲盒的优惠日期
    }
    for (int i = 1; i <= n; ++i) {
        std::sort(saleDay[i].rbegin(), saleDay[i].rend()); // 倒序
    }
    int lt = 1, rt = 1e9; // 二分的边界
    while (lt <= rt) { int mid = (lt + rt) / 2; if (half(mid)) lt = mid + 1; else rt = mid - 1; }
    printf("%lld\n", lt);
}

分治

假设数组的长度是 n，那么每次递归调用的时间复杂度是 $\Theta(n)$，并且递归调用的深度是 $\log_{2} n$（因为每次递归将数组分成两部分）。因此，总体时间复杂度是 $\Theta(n\log n)$。

引例 VJwin7E - a-Good String

Description

将一个字符串修改为一半（左半或右半）是 a，剩下的一半中的其中一半是 b，再剩下的一半中的其中一半是 c…… 以此类推，求最小操作次数。

Notes

因为不知道是哪一半，分别计算是左半和右半，再进行比较。

分治函数：

int solve(int l, int r, char c) {
    if (l == r) return s[l] != c;         // 叶子 长度为1的串
    int mid = (l + r) >> 1;
    
    int suml = 0;
    for (int i = l; i <= mid; ++i) suml += s[i] != c;
    suml += solve(mid + 1, r, c + 1);     // 修改左半
    
    int sumr = 0;
    for (int i = mid + 1; i <= r; ++i) sumr += s[i] != c;
    sumr += solve(l, mid, c + 1);         // 修改右半
    
    return min(suml, sumr);
}

答案即是 solve(1, n, 'a')。

前缀和处理：

for (int i = 0; i < 26; ++i) {
    for (int j = 1; j <= n; ++j)
        pre[j][i] = pre[j - 1][i] + (s[j] == 'a' + i);
}

分治函数相应地改为

int solve(int l, int r, int c) {
    if (l == r) return s[l] != 'a' + c;   // 叶子 长度为1的串
    int mid = (l + r) >> 1;

    int suml = (mid - l + 1) - (pre[mid][c] - pre[l - 1][c]);
    suml += solve(mid + 1, r, c + 1);     // 修改左半

    int sumr = (r - mid) - (pre[r][c] - pre[mid][c]);
    sumr += solve(l, mid, c + 1);         // 修改右半

    return min(suml, sumr);
}

Code

#include <iostream>
#include <algorithm>
const int N = 1e6 + 7;
string s;
int pre[N][30];   // 统计每类字母的个数

int solve(int l, int r, int c) {
    if (l == r) return s[l] != 'a' + c;   // 叶子 长度为1的串
    int mid = (l + r) >> 1;

    int suml = (mid - l + 1) - (pre[mid][c] - pre[l - 1][c]);
    suml += solve(mid + 1, r, c + 1);     // 修改左半

    int sumr = (r - mid) - (pre[r][c] - pre[mid][c]);
    sumr += solve(l, mid, c + 1);         // 修改右半

    return min(suml, sumr);
}

void eachT() {
    int n;
    cin >> n >> s;
    s = ' ' + s;
    for (int i = 0; i < 26; ++i) {
        for (int j = 1; j <= n; ++j)
            pre[j][i] = pre[j - 1][i] + (s[j] == 'a' + i);
    }
    cout << solve(1, n, 0) << '\n';
}

int main() {
	int T;
	cin >> T;
	while (T--) eachT();
	return 0;
}

CF1696D. Permutation Graph

题意 给出一个$1$ 到$n$ 的排列。对于$1\le i < j\le n$ ，记$\operatorname{mn}(i,j)$ 为$\min\limits_{k=i}^j a_k$，记$\operatorname{mx}(i,j)$ 为$\max\limits_{k=i}^j a_k$ 。

有一张$n$ 个点的无向图，点的编号为$1$ 到$n$。对于每一对整数$1\le i<j\le n$ ，如果同时满足$\operatorname{mn}(i,j)=a_i$ 且$\operatorname{mx}(i,j)=a_j$ ，或同时满足$\operatorname{mn}(i,j)=a_j$ 和$\operatorname{mx}(i,j)=a_i$，那么就在$i$ 和$j$ 之间连一条长度为$1$ 的边。

求从$1$ 到$n$ 的最短路。

思路 如果能注意到，一定有一条边是整个数组的最大值连向最小值，并且这一条边一定会走，这道题就做完了。

int n = read();
vector<int> a(n + 1), pos(n + 1);
for (int i = 1; i <= n; ++i) {
	a[i] = read();
	pos[a[i]] = i;
}
RMQ rmq(a);
auto solve = [&](auto&& solve, int l, int r) -> int {
	if (l == r) return 0;
	int mx = rmq.getmax(l, r), mn = rmq.getmin(l, r);
	int L = min(pos[mx], pos[mn]), R = max(pos[mx], pos[mn]);
	return solve(solve, l, L) + 1 + solve(solve, R, r);
};
printf("%d\n", solve(solve, 1, n));

VJwin3I - 铺设道路

选择一些连续的数，使其减少 1，至减为 0 止。求操作次数最小值。

int n = read();
vector<int> a(n);
for (int i = 0; i < n; ++i) a[i] = read();
auto dfs = [&](auto&& self, int l, int r, int done) -> int {
	if (l >= r) return 0;
	int mid = l;
	for (int i = l; i < r; ++i) {
		if (a[i] < a[mid]) mid = i;
	}
	return (a[mid] - done)
		+ self(self, l, mid, a[mid])
		+ self(self, mid + 1, r, a[mid]);
};
printf("%d\n", dfs(dfs, 0, n, 0));

UPD 线性方法：右边的大数会在左边的小数减少时同步减少，那么对每个大数，只需要做和它左边的小数的差值那么多。

int n = read();
int now = 0, lst = 0, sum = 0;
for (int i = 1; i <= n; ++i) {
	now = read();
	sum += now > lst ? now - lst : 0;
	lst = now;
}
printf("%d\n", sum);

	### [2023 CCPC 深圳 F. 一道好题](https://cpc.csgrandeur.cn/csgoj/problemset/problem?pid=1237)

题意 初始为 0 的序列，两种操作，一是给值为$x$ 的数$+1$，二是给下标为$x$ 的数$+1$，至多$20000$ 次操作得到目标序列。$n,a_{i} \leqslant 1000$。
00
思路 对操作分治，则操作一每个数至多$\log n$ 次，操作二至多$n$ 次，总次数是$\Theta(n\log n)$ 的。

int n;
cin >> n;

vector<int> a(n);
for (int i = 0; i < n; ++i) {
	cin >> a[i];
}

vector<pair<int, int>> res;
auto dfs = [&](auto&& self, int l, int r) -> void {  // 刚开始进循环时，所有值域范围为[l,r)的 a[i]值均为 l 
	if (r - l < 2) return;
	int mid = l + r >> 1;
	for (int i = 0; i < n; ++i) {   // 将目标值较大的a[i]凸出
		if (mid <= a[i] && a[i] < r) {
			res.push_back({ 2, i + 1 });
		}
	}
	for (int i = l + 1; i < mid; ++i) {  // 将所有较大的a[i]变成mid
		res.push_back({ 1, i });
	}
	self(self, l, mid);
	self(self, mid, r);
};
dfs(dfs, 0, n + 1);

cout << res.size() << "\n";
for (auto& [a, b] : res) {
	cout << a << " " << b << "\n";
}

CDQ 分治

归并排序求逆序对

ll merge_sort(vector<int>& a) {
	auto solve = [&](auto&& self, int L, int R) -> ll {
		if (R - L <= 1) return 0ll;
		int m = L + R >> 1;
		ll res = self(self, L, m) + self(self, m, R);
		vector<int> b;
		int l = L, r = m;
		while (l < m && r < R) {
			if (a[l] <= a[r]) b.push_back(a[l++]);
			else b.push_back(a[r++]), res += m - l;
		}
		while (l < m) b.push_back(a[l++]);
		while (r < R) b.push_back(a[r++]);
		copy(b.begin(), b.end(), a.begin() + L);
		return res;
	};
	return solve(solve, 0, a.size());
}

迭代器版本也不错：

using it = vector<int>::iterator;
ll merge_sort(it L, it R) {
    if (distance(L, R) <= 1) return 0;
    it m = L + (R - L) / 2;
    ll res = merge_sort(L, m) + merge_sort(m, R);
    vector<int> b;
    it l = L, r = m;
    while (l < m && r < R) {
        if (*l <= *r) b.push_back(*l++);
        else b.push_back(*r++), res += m - l;
    }
    while (l < m) b.push_back(*l++);
    while (r < R) b.push_back(*r++);
    copy(b.begin(), b.end(), L);
    return res;
}

三维偏序

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 200010;

struct node {
	int x, y, z, ans, w;
};

struct BIT {
	int t[N];
	void update(int p, int x) {
		while (p < N) t[p] += x, p += p & -p;
	}
	int query(int p) {
		int res = 0;
		while (p >= 1) res += t[p], p -= p & -p;
		return res;
	}
	int query(int l, int r) {
		return query(r) - query(l - 1);
	}
} t;

int main() {
	int n, k;
	cin >> n >> k;

    vector<node> b(n);
	for (int i = 0; i < n; i++) {
		cin >> b[i].x >> b[i].y >> b[i].z;
	}
	sort(b.begin(), b.end(), [&](const node& u, const node& v) {
		return u.x == v.x ? u.y == v.y ? u.z < v.z : u.y < v.y : u.x < v.x;
	});

    vector<node> a;
	for (int i = 0, cnt = 0; i < n; i++) {
		cnt++;
		if (b[i].x != b[i + 1].x || b[i].y != b[i + 1].y || b[i].z != b[i + 1].z) {
            a.push_back(b[i]);
            a.back().w = cnt;
			cnt = 0;
		}
	}

    auto cdq = [&](auto&& self, int L, int R) -> void {
        if (R - L < 2) return;
        int mid = (L + R) >> 1;
        self(self, L, mid);
        self(self, mid, R);
        sort(a.begin() + L, a.begin() + mid, [&](const node& u, const node& v) {
            return u.y == v.y ? u.z < v.z : u.y < v.y;
        });
        sort(a.begin() + mid, a.begin() + R, [&](const node& u, const node& v) {
            return u.y == v.y ? u.z < v.z : u.y < v.y;
        });
        int l = L, r = mid;
        while (r < R) {
            while (l < mid && a[l].y <= a[r].y) {
                t.update(a[l].z, a[l].w);
                l++;
            }
            a[r].ans += t.query(a[r].z);
            r++;
        }
        while (l > L) {
            l--;
            t.update(a[l].z, -a[l].w);
        }
    };
	cdq(cdq, 0, a.size());

	vector<int> res(n);
	for (int i = 0; i < a.size(); i++) {
		res[a[i].ans + a[i].w - 1] += a[i].w; // res[x]储存f[i]=x的个数，x就等于i的答案加上它重复的个数（可以取等）减去本身
	}
	for (int i = 0; i < n; i++) {
		cout << res[i] << "\n";
	}

	return 0;
}