20240420 测试 笔记

$pts=22+0+0+3+23=48$

T1

题意

有 $(0,0)$ 到 $(n-1,n-1)$ 共有 $n^2$ 个点，$(0,0)$ 点是一把激光枪，可以杀死某一射线上的全部小鸟，有 $m$ 个点上没有小鸟，其他每个点上有一只鸟。你最多可以开 $k$ 枪，求最多可以杀死的鸟的数量。

$1\le n\le 4\times {10}^6$，$1\le m\le min(2500,n^2-n)$，$1\le k\le 1.6\times {10}^{13}$。

分析

$k$ 非常大，所以不能枚举每一枪最多杀死多少只鸟。

由于一枪最多只能射死 $n$ 只鸟，所以可以处理出 $f_i$ 表示一枪杀死 $i$ 只鸟的方案数。

假设下文中所有的 $gcd(x,0)=x$。先考虑 $m=0$ 的时候的方案数。容易发现如果某一枪经过 $(x,y)$，则这一枪也一定会经过 $(\frac{x}{gcd(x,y)},\frac{y}{gcd(x,y)})$，所以我们可以在 $gcd(x,y)=1$ 的 $(x,y)$ 处处理这一条射线的能杀死的小鸟数。

不难求得小鸟数为 $min(\lfloor \frac{n-1}{x}\rfloor ,\lfloor \frac{n-1}{y}\rfloor )$，即 $\lfloor \frac{n-1}{max(x,y)}\rfloor$。只需要处理出 $x>y$ 的方案数，再乘上二并加上 $x=y$ 的方案数即可。

当 $x>y$ 时，$y$ 又要与 $x$ 互质，那么 $y$ 的取值个数就是 $\phi (x)$ 个，也就是 $f_{\lfloor \frac{n-1}{x}\rfloor }\leftarrow \phi (x)$。

接着考虑飞走了若干只小鸟，如果某条能打死 $a$ 只鸟的射线上飞走了 $b$ 只鸟，那么明显 $f_a\leftarrow f_a-1$，$f_{a-b}\leftarrow f_{a-b}+1$。

Code

void solve() {
	memset(f, 0, sizeof f);
	cin >> n >> k >> m;
	for (int i = 2; i < n; i++) f[(n - 1) / i] += phi[i] * 2;
	f[n - 1] += 3;
	for (int i = 1; i <= m; i++) {
		cin >> del[i].x >> del[i].y;
		if (!del[i].x) del[i].y = 1;
		else if(!del[i].y) del[i].x = 1;
		else {
			int gcd = __gcd(del[i].x, del[i].y);
			del[i].x /= gcd;
			del[i].y /= gcd;
		}
	}
	sort(del + 1, del + m + 1, cmp);
	int tmp = 0;
	for (int i = 1; i <= m; i++) {
		tmp++;
		if (del[i].x != del[i + 1].x or del[i].y != del[i + 1].y) {
			f[(n - 1) / max(del[i].x, del[i].y)]--;
			f[(n - 1) / max(del[i].x, del[i].y) - tmp]++;
			tmp = 0;
		}
	}
	int ret = 0;
	for (int i = n - 1; i; i--) {
		if (f[i] >= k) {
			ret += i * k;
			break;
		} else ret += f[i] * i;
		k -= f[i];
	}
	cout << ret << "\n";
}

T2

题意

给出一个长度为 $n$ 的排列 $P(P_1,P_2,\dots ,Pn)$，以及 $m$ 个询问。每次询问某个区间 $[l,r]$ 中，最长的值域连续段长度。

$1\le n,m\le 5\times {10}^4$。

分析

明显向右扩展一个容易，所以采用回滚莫队。

并查集不好回滚，所以不使用。

考虑维护 $l_i$ 表示 $i$ 所在连续段的左边界，$r_i$ 表示 $i$ 所在连续段的有边界，那么只需用一个数组来记录增加前的操作，删除的时候倒着跑一遍就行了。

Code

namespace MoDui {
    int block, belong[N], tmp;
    int L[N], R[N], recnt;
    bool vis[N];
    struct REPLACE {
        int p, l, r, vis;
    } re[N];
    void init_block() {
        block = sqrt(n);
        for (int i = 1; i <= n; i++) belong[i] = (i - 1) / block + 1;
    }
    bool cmp(QUESTION x, QUESTION y) {
        return belong[x.l] != belong[y.l] ? belong[x.l] < belong[y.l] : x.r < y.r;
    }
    void addre(int x) {
        re[++recnt] = {x, L[x], R[x], vis[x]};
        vis[x] = true;
        if (vis[x - 1]) {
            re[++recnt] = {L[x - 1], L[L[x - 1]], R[L[x - 1]], vis[L[x - 1]]};
            L[x] = L[x - 1];
            R[L[x]] = x;
        }
        if (vis[x + 1]) {
            re[++recnt] = {R[x + 1], L[R[x + 1]], R[R[x + 1]], vis[R[x + 1]]};
            L[R[x + 1]] = L[x];
            R[L[x]] = R[x + 1];
            R[x] = R[x + 1];
        }
        tmp = max(tmp, R[x] - L[x] + 1);
    }
    void add(int x) {
        vis[x] = true;
        if (vis[x - 1]) {
            L[x] = L[x - 1];
            R[L[x]] = x;
        }
        if (vis[x + 1]) {
            L[R[x + 1]] = L[x];
            R[L[x]] = R[x + 1];
            R[x] = R[x + 1];
        }
        tmp = max(tmp, R[x] - L[x] + 1);
    }
    void solve() {
        sort(q + 1, q + m + 1, cmp);
        for (int i = 1; i <= n; i++)
            vis[a[i]] = 0, L[a[i]] = R[a[i]] = a[i];
        int l = 1, r = 0;
        for (int i = 1; i <= m; i++) {
            if (q[i].l >= l) {
                tmp = 0;
                for (int j = 1; j <= n; j++) vis[a[j]] = 0, L[a[j]] = R[a[j]] = a[j];
                r = belong[q[i].l] * block;
                l = r + 1;
                tmp = 1;
            }
            if (belong[q[i].l] == belong[q[i].r]) {
                int last = tmp;
                for (int j = q[i].l; j <= q[i].r; j++) add(a[j]);
                ans[q[i].id] = tmp;
                for (int j = q[i].l; j <= q[i].r; j++) vis[a[j]] = 0, L[a[j]] = R[a[j]] = a[j];
                tmp = last;
                continue;
            }
            while (r < q[i].r) add(a[++r]);
            int last = tmp;
            for (int j = q[i].l; j < l; j++) addre(a[j]);
            ans[q[i].id] = tmp;
            for (int j = recnt; j; j--) {
                int p = re[j].p;
                L[p] = re[j].l;
                R[p] = re[j].r;
                vis[p] = re[j].vis;
            }
            recnt = 0;
            tmp = last;
        }
    }
}
using namespace MoDui;

T3

题意

一个国家有 $n$ 个城市，每个城市中都有一个加油站，燃料储量为 $a_i$。有 $n-1$ 条路径，将这些城市连接成一个树形结构。假设货车的油箱是无限大的，请你算出有多少个有序数对 $(u,v)$ 满足：一个油箱燃料量初始为 $0$ 的货车，可以从城市 $u$ 出发，抵达城市 $v$。货车只能走简单路径，也就是说不能走回头路。
$1\le n\le {10}^5$，$1\le u,v\le n$，$1\le w,a_i\le {10}^9$

分析

求树上点对数目问题，明显点分治。

首先要判断这条路径是否合法。如果一条路径 $u\to v$ 经过 $rt$，那么就能被拆分成 $u\to rt$ 和 $rt\to v$ 两段。分别考虑处理这两段是否合法。

先考虑 $u\to rt$，设到某个点 $x$ 上的点权和为 $v{s}_x$，经过的边权和位 $di{s}_x$。显然对于 $u\to rt$ 路径上的每一个点 $i$，都要满足 $v{s}_u-v{s}_i\ge di{s}_u-di{s}_i$，即 $v{s}_u-di{s}_u-(v{s}_i-di{s}_i)\ge 0$，只需要维护最大的 $v{s}_i-di{s}_i$ 即可判断是否合法。

再考虑 $rt\to v$。假设走到 $rt$ 还剩 $x$ 的油，对于路径上每个点 $i$，都要满足 $x+v{s}_{fa}\ge di{s}_i$，即 $x+(v{s}_{fa}-di{s}_i)\ge 0$，维护 $v{s}_{fa}-di{s}_i$ 的最小值即可。

怎么统计答案呢？记录下来 $u\to rt$ 中剩余的油量，即 $v{s}_u-di{s}_u$，以及以空油箱从 $rt$ 出发时，到达 $v$ 时最少所剩的油量（由于这里不判断合法性，所以正负均可）。那么每一个 $(v{s}_u-di{s}_u)+(v{s}_{f{a}_v}-di{s}_v)\ge 0$ 的都是合法的方案。双指针跑即可。

Code

namespace PDC {
    int sz[N], mx[N], rt, vs[N], dis[N];
    int q1[N], p1, q2[N], p2, m1[N], n1, m2[N], n2;
    bool vis[N];
    void getrt(int u, int fa, int nodecnt) {
        sz[u] = 1;
        mx[u] = 0;
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].v;
            if (v == fa or vis[v]) continue;
            getrt(v, u, nodecnt);
            sz[u] += sz[v];
            mx[u] = max(mx[u], sz[v]);
        }
        mx[u] = max(mx[u], nodecnt - sz[u]);
        if (mx[u] < mx[rt]) rt = u;
    }
    void getdis(int u, int fa, int maxx, int minn) {
        if (vs[u] - dis[u] >= maxx) m1[++n1] = vs[u] - dis[u];
        m2[++n2] = minn;
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].v;
            if (v == fa or vis[v]) continue;
            vs[v] = vs[u] + a[v];
            dis[v] = dis[u] + edge[i].w;
            getdis(v, u, max(maxx, vs[u] - dis[u]), min(minn, vs[u] - dis[v]));
        }
    }
    void calc(int u) {
        int l;
        p1 = p2 = 0;
        vs[u] = a[u];
        dis[u] = 0;
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].v;
            if (vis[v]) continue;
            n1 = n2 = 0;
            vs[v] = vs[u] + a[v];
            dis[v] = edge[i].w;
            getdis(v, u, vs[u] - dis[u], vs[u] - dis[v]);
            sort(m1 + 1, m1 + n1 + 1);
            sort(m2 + 1, m2 + n2 + 1);
            l = 1;
            for (int i = n2; i; i--) {
                while (l <= n1 and m1[l] + m2[i] - a[u] < 0) l++;
                ans -= n1 - l + 1;
            }
            for (int i = 1; i <= n1; i++) q1[++p1] = m1[i];
            for (int i = 1; i <= n2; i++) q2[++p2] = m2[i];
        }
        ans += p1;
        sort(q1 + 1, q1 + p1 + 1);
        sort(q2 + 1, q2 + p2 + 1);
        l = 1;
        for (int i = p2; i; i--) {
            if (q2[i] >= 0) ans++;
            while (l <= p1 and q1[l] + q2[i] - a[u] < 0) l++;
            ans += p1 - l + 1;
        }
    }
    void solve(int u, int nodecnt) {
        mx[rt = 0] = oo;
        getrt(u, 0, nodecnt);
        getrt(rt, 0, nodecnt);
        vis[rt] = 1;
        calc(rt);
        for (int i = head[rt]; i; i = edge[i].next) {
            int v = edge[i].v;
            if (vis[v]) continue;
            solve(v, sz[v]);
        }
    }
}
using namespace PDC;