2 条题解

  • 0
    @ 2026-2-1 0:29:29

    使用可持久化权值线段树，对每个格子能走到的最低海拔位置开桶维护，即可完成优化。优化后的时间复杂度为 O(k2log⁡k+qlog⁡k)O(k^2 \log k + q \log k)，空间复杂度为 O(k2log⁡k)O(k^2 \log k)。

    #include <bits/stdc++.h>
using namespace std;
const int K = 250;
const int L = K + 12;
const int M = K * K + 12;
const int N = 4 * K * K + 12;
const int P = 16;
const int O = 0xffff;
const int D = 4 * K * K * P + 2 * O + 12;
const int C = 2 * K * K + 12;
pair<unsigned short, unsigned short> e[N];
pair<unsigned char, unsigned char> at[M];
unsigned short alt[L][L];
unsigned short eto[M];
int k;
int q;
int ec = 0;
int now = 0;
struct U
{
    unsigned short a[D];
    unsigned short ll[D];
    unsigned short rr[D];
    int l[D];
    int r[D];
    int roots[C];
    int ts;
    int st;
    void init(int n)
    {
        ts = n;
        st = n;
        for (int i = 1; i <= n; i++)
            rr[i] = (1 << P) - 1;
        for (int i = 1; i <= n; i++)
            roots[i] = i;
    }
    void expand(int b)
    {
        if (ll[b] == rr[b]) return;
        if (l[b] == 0)
        {
            ts++;
            a[ts] = 0;
            ll[ts] = ll[b];
            rr[ts] = (ll[b] + rr[b]) >> 1;
            l[ts] = 0;
            r[ts] = 0;
            l[b] = ts;
        }
        if (r[b] == 0)
        {
            ts++;
            a[ts] = 0;
            ll[ts] = ((ll[b] + rr[b]) >> 1) + 1;
            rr[ts] = rr[b];
            l[ts] = 0;
            r[ts] = 0;
            r[b] = ts;
        }
    }
    bool create(int x, int b)
    {
        if (ll[b] == x && rr[b] == x) return true;
        expand(b);
        int lmid = (ll[b] + rr[b]) >> 1;
        int rmid = lmid + 1;
        if (x <= lmid) return create(x, l[b]);
        if (x >= rmid) return create(x, r[b]);
    }
    bool add(int x, int y, int b, int c)
    {
        if (b != c) a[b] += a[c] + y;
        if (b == c) a[b] += y;
        if (ll[b] == x && rr[b] == x) return true;
        int lmid = (ll[b] + rr[b]) >> 1;
        int rmid = lmid + 1;
        if (x <= lmid) r[b] = r[c];
        if (x >= rmid) l[b] = l[c];
        expand(b);
        if (x <= lmid) return add(x, y, l[b], l[c]);
        if (x >= rmid) return add(x, y, r[b], r[c]);
    }
    int get(int l, int r, int b)
    {
        if (!b) return 0;
        if (l == ll[b] && r == rr[b]) return a[b];
        int lmid = (ll[b] + rr[b]) >> 1;
        int rmid = lmid + 1;
        if (r <= lmid) return get(l, r, this -> l[b]);
        if (l >= rmid) return get(l, r, this -> r[b]);
        return get(l, lmid, this -> l[b]) + get(rmid, r, this -> r[b]);
    }
};
U t;
struct T
{
	unsigned short x;
	unsigned short y;
	unsigned short a;
};
struct R
{
	unsigned short ld[M];
	unsigned short sz[M];
	unsigned short mina[M];
	void init()
	{
		for (unsigned short i = 1; i <= k * k; i++)
		{
			ld[i] = i;
			sz[i] = 1;
		}
		for (unsigned char i = 1; i <= k; i++)
			for (unsigned char j = 1; j <= k; j++)
				mina[(i - 1) * k + j] = alt[i][j];
	}
	unsigned short get(unsigned short x)
	{
		if (ld[x] == x) return x;
		ld[x] = get(ld[x]);
		return ld[x];
	}
	T mrg(int x, int y)
	{
		x = this -> get(x);
		y = this -> get(y);
		if (x == y) return (T) {O, O, O};
		unsigned short xx = sz[x];
		unsigned short yy = sz[y];
		if (xx < yy)
		{
			swap(x, y);
			swap(xx, yy);
		}
		T res;
		if (mina[x] < mina[y]) res = (T) {mina[x], mina[y], sz[y]};
		if (mina[x] > mina[y]) res = (T) {mina[y], mina[x], sz[x]};
		ld[y] = x;
		sz[x] = xx + yy;
		sz[y] = 0;
		mina[x] = min(mina[x], mina[y]);
		mina[y] = O;
		return res;
	}
};
R rt;
int main()
{
	ios::sync_with_stdio(0);
	cin >> k >> q;
	for (int i = 1; i <= k; i++)
		for (int j = 1; j <= k; j++)
			cin >> alt[i][j];
	for (int i = 0; i <= k + 1; i++)
		alt[0][i] = O;
	for (int i = 0; i <= k + 1; i++)
		alt[k + 1][i] = O;
	for (int i = 0; i <= k + 1; i++)
		alt[i][0] = O;
	for (int i = 0; i <= k + 1; i++)
		alt[i][k + 1] = O;
	for (int i = 1; i <= k; i++)
		for (int j = 1; j <= k; j++)
			at[alt[i][j]] = make_pair(i, j);
	for (int i = 0; i <= k * k - 1; i++)
	{
		int x = at[i].first;
		int y = at[i].second;
		if (alt[x][y + 1] < alt[x][y])
		{
			ec++;
			e[ec] = make_pair((x - 1) * k + y, (x - 1) * k + (y + 1));
		}
		if (alt[x][y - 1] < alt[x][y])
		{
			ec++;
			e[ec] = make_pair((x - 1) * k + y, (x - 1) * k + (y - 1));
		}
		if (alt[x + 1][y] < alt[x][y])
		{
			ec++;
			e[ec] = make_pair((x - 1) * k + y, x * k + y);
		}
		if (alt[x - 1][y] < alt[x][y])
		{
			ec++;
			e[ec] = make_pair((x - 1) * k + y, (x - 2) * k + y);
		}
	}
	rt.init();
	t.init(2 * k * k - 1);
	for (int i = 0; i <= O; i++)
		t.create(i, t.roots[2 * k * k - 1]);
	for (int i = 0; i <= O; i++)
		t.add(i, 1, t.roots[2 * k * k - 1], t.roots[2 * k * k - 1]);
	t.roots[0] = t.roots[2 * k * k - 1];
	for (int i = 1; i <= ec; i++)
	{
		T res = rt.mrg(e[i].first, e[i].second);
		if (res.a != O)
		{
			now++;
			t.add(res.y, -res.a, t.roots[2 * now - 1], t.roots[2 * now - 2]);
			t.add(res.x, res.a, t.roots[2 * now], t.roots[2 * now - 1]);
		}
		eto[alt[(e[i].first - 1) / k + 1][(e[i].first - 1) % k + 1]] = now;
	}
	for (int i = 1; i <= k * k - 1; i++)
		eto[i] = max(eto[i], eto[i - 1]);
	while (q--)
	{
		int x;
		int y;
		cin >> x >> y;
		cout << y - t.get(0, x, t.roots[2 * eto[y - 1]]) << endl;
	}
	return 0;
}
    • 0
      @ 2025-9-4 21:59:19

      随着 yy 的值从 00 增大到 k2−1k^2-1，格子与格子之间一共连上了 2k(k−1)2k(k-1) 条边，而这可以看成 2k(k−1)2k(k-1) 次加边操作。

      在开始处理询问前，我们可以用并查集将 2k(k−1)2k(k-1) 次加边操作完整地维护一遍，并对每 kk 次操作分块。在每个块中，我们需要完整地保存此时并查集的状态，以及此时每个 xx 的取值对应的答案。

      在并查集中，我们可以在每个连通块的根部记录该连通块的大小以及该连通块内的海拔。在每个 xx 的取值对应的答案时，我们只要扫描所有根部存储的信息，再结合前缀和就可以求出每个 xx 的取值对应的答案了。

      对于每次询问，我们只需要访问其 yy 值对应的那一块，并在那一块的并查集上暴力进行剩下的加边操作，在加边的同时维护最终答案相对于之前存储的答案的变化，并在输出答案后复原并查集中被修改的部分，就可以做到在线回答询问了。

      最终的时间复杂度为 O(k3+qk)O(k^3+qk)，空间复杂度为 O(k3)O(k^3)。

      #include <bits/stdc++.h>
using namespace std;
const int K = 250 + 12;
const int L = 500 + 12;
const int M = 62500 + 12;
const int N = 125000 + 12;
const int O = 0xffff;
int alt[K][K];
pair<int, int> at[M];
int eto[M];
int k, q, A;
pair<unsigned short, unsigned short> e[N];
int ec = 0;
struct Q
{
    unsigned short id;
    unsigned short ld;
    unsigned short sz;
    unsigned short mina;
};
struct R
{
    unsigned short ld[M], sz[M], ans[M], mina[M];
    stack<Q> rec;
    void init()
    {
        for (unsigned short i = 1; i <= k * k; i++)
            ld[i] = i, sz[i] = 1;
        for (unsigned char i = 1; i <= k; i++)
            for (unsigned char j = 1; j <= k; j++)
                mina[(i - 1) * k + j] = alt[i][j];
    }
    unsigned short get(unsigned short x)
    {
        if (ld[x] == x) return x;
        ld[x] = get(ld[x]);
        return ld[x];
    }
    void mrg(int x, int y)
    {
        x = this -> get(x);
        y = this -> get(y);
        if (x == y) return;
        unsigned short xx = sz[x], yy = sz[y];
        if (xx < yy)
        {
            swap(x, y);
            swap(xx, yy);
        }
        ld[y] = x;
        sz[x] = xx + yy;
        sz[y] = 0;
        mina[x] = min(mina[x], mina[y]);
        mina[y] = O;
    }
    unsigned short get_rec(unsigned short x)
    {
        rec.push((Q) {x, ld[x], sz[x], mina[x]});
        if (ld[x] == x) return x;
        ld[x] = get_rec(ld[x]);
        return ld[x];
    }
    unsigned short mrg_rec(int x, int y, int v)
    {
        x = this -> get_rec(x);
        y = this -> get_rec(y);
        if (x == y) return 0;
        unsigned short xx = sz[x], yy = sz[y];
        if (xx < yy)
        {
            swap(x, y);
            swap(xx, yy);
        }
        ld[y] = x;
        unsigned short res = 0;
        if (mina[x] <= v && mina[y] > v) res = yy;
        if (mina[x] > v && mina[y] <= v) res = xx;
        sz[x] = xx + yy;
        sz[y] = 0;
        mina[x] = min(mina[x], mina[y]);
        mina[y] = O;
        return res;
    }
    void recover()
    {
        while (!rec.empty())
        {
            Q u = rec.top();
            rec.pop();
            ld[u.id] = u.ld;
            sz[u.id] = u.sz;
            mina[u.id] = u.mina;
        }
    }
};
R rt[L];
int main()
{
    ios::sync_with_stdio(0);
    cin >> k >> q;
    for (int i = 1; i <= k; i++)
        for (int j = 1; j <= k; j++)
            cin >> alt[i][j];
    for (int i = 0; i <= k + 1; i++)
        alt[0][i] = O;
    for (int i = 0; i <= k + 1; i++)
        alt[k + 1][i] = O;
    for (int i = 0; i <= k + 1; i++)
        alt[i][0] = O;
    for (int i = 0; i <= k + 1; i++)
        alt[i][k + 1] = O;
    A = k;
    for (int i = 1; i <= k; i++)
        for (int j = 1; j <= k; j++)
            at[alt[i][j]] = make_pair(i, j);
    for (int i = 0; i <= k * k - 1; i++)
    {
        int x = at[i].first, y = at[i].second;
        if (alt[x][y + 1] < alt[x][y])
        {
            ec++;
            e[ec] = make_pair((x - 1) * k + y, (x - 1) * k + (y + 1));
        }
        if (alt[x][y - 1] < alt[x][y])
        {
            ec++;
            e[ec] = make_pair((x - 1) * k + y, (x - 1) * k + (y - 1));
        }
        if (alt[x + 1][y] < alt[x][y])
        {
            ec++;
            e[ec] = make_pair((x - 1) * k + y, x * k + y);
        }
        if (alt[x - 1][y] < alt[x][y])
        {
            ec++;
            e[ec] = make_pair((x - 1) * k + y, (x - 2) * k + y);
        }
        eto[i] = ec;
    }
    rt[0].init();
    for (int i = A, j = 1; i <= ec; i += A, j++)
    {
        rt[j] = rt[j - 1];
        for (int ii = i, jj = 1; jj <= A; ii--, jj++)
            rt[j].mrg(e[ii].first, e[ii].second);
    }
    for (int i = 0, j = 0; i <= ec; i += A, j++)
    {
        for (unsigned short ii = 1; ii <= k * k; ii++)
            if (rt[j].mina[ii] != 0xffff) rt[j].ans[rt[j].mina[ii]] += rt[j].sz[ii];
        for (unsigned short ii = 1; ii <= k * k; ii++)
            rt[j].ans[ii] += rt[j].ans[ii - 1];
    }
    for (int i = 0, j = 0; i <= ec; i += A, j++)
        for (int ii = 1; ii <= k * k; ii++)
            rt[j].get(ii);
    while (q--)
    {
        int x, y;
        cin >> x >> y;
        int z = eto[y - 1] / A;
        int ans = rt[z].ans[x];
        for (int i = z * A + 1; i <= eto[y - 1]; i++)
            ans += rt[z].mrg_rec(e[i].first, e[i].second, x);
        cout << y - ans << endl;
        rt[z].recover();
    }
    return 0;
}
      • 1

      [Sleeping Cup #2] Sleeping Bear's Honey 3

      信息

      ID
      23
      时间
      4000ms
      内存
      512MiB
      难度
      8
      标签
      递交数
      173
      已通过
      3
      上传者
      1. Language
      2. 兼容模式
      3. 主题
      2. Source Code Modified by Sleeping Cup
      3. Worker 0, 94ms
      4. Powered by Hydro v5.0.7 Community