跳至主要內容

鬼子进村

33DAI2024年12月25日大约 7 分钟

O(n) 查询

暴力

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50000;
int n, m;
int a[MAXN + 5]; // 1 表示被摧毁了，0 表示没被摧毁
stack<int> st;	 // 记录摧毁的房子
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	a[0] = 1;
	a[n + 1] = 1;
	while (m--)
	{
		char op;
		cin >> op;
		if (op == 'D')
		{
			int x;
			cin >> x;
			a[x] = 1;
			st.push(x);
		}
		if (op == 'R')
		{
			a[st.top()] = 0;
			st.pop();
		}
		if (op == 'Q')
		{
			int x;
			cin >> x;
			int L, R; // 记录 x左边右边的第一个被摧毁的位置
			for (int i = x; i >= 0; i--)
				if (a[i] == 1)
				{
					L = i;
					break;
				}
			for (int i = x; i <= n + 1; i++)
				if (a[i] == 1)
				{
					R = i;
					break;
				}
			if (L == R)
				cout << 0 << "\n";
			else
				cout << R - L - 1 << "\n";
		}
	}
	return 0;
}

O(log2⁡n) 查询

树状数组写法

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50000;
int n, m;
int a[MAXN + 5]; // 1 表示被摧毁了，0 表示没被摧毁
stack<int> st;	 // 记录摧毁的房子
// 树状数组
int t[MAXN + 5];
int lowbit(int x)
{
	return x & -x;
}
// a[x]+=y
void update(int x, int y)
{
	for (int i = x; i <= n; i += lowbit(i))
		t[i] += y;
}
// sum(a[1]~a[x])
int query(int x)
{
	int res = 0;
	for (int i = x; i > 0; i -= lowbit(i))
		res += t[i];
	return res;
}
int my_lower_bound(int x)
{
	// 找到第一个 query(i) 大于等于 x 的 i
	int l = 1;
	int r = n;
	int ans = -1;
	while (l <= r)
	{
		int mid = (l + r) / 2;
		if (query(mid) >= x)
		{
			ans = mid;
			r = mid - 1;
		}
		else
			l = mid + 1;
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	a[0] = 1;
	a[n + 1] = 1;
	while (m--)
	{
		char op;
		cin >> op;
		if (op == 'D')
		{
			int x;
			cin >> x;
			a[x] = 1;
			update(x, 1);
			st.push(x);
		}
		if (op == 'R')
		{
			a[st.top()] = 0;
			update(st.top(), -1);
			st.pop();
		}
		if (op == 'Q')
		{
			int x;
			cin >> x;
			if (a[x] == 1)
			{
				cout << 0 << "\n";
				continue;
			}
			int cnt = query(x); // x及左边有多少个房子被摧毁了
			int L, R;			// 记录 x左边右边的第一个被摧毁的位置
			if (cnt == 0)
				L = 0; // 左边没有房子被摧毁时，认为左边第一个被摧毁的是 0 号位置
			else
				L = my_lower_bound(cnt);
			if (cnt == st.size())
				R = n + 1; // 左边没有房子被摧毁时，认为右边第一个被摧毁的是 n + 1 号位置
			else
				R = my_lower_bound(cnt + 1);
			cout << R - L - 1 << "\n";
		}
	}
	return 0;
}

线段树写法

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50000;
int n, m;
int a[MAXN + 5]; // 1 表示被摧毁了，0 表示没被摧毁
stack<int> st;	 // 记录摧毁的房子
// 线段树
int t[MAXN * 4 + 5];
int lazy[MAXN * 4 + 5];
// 当前节点为 now，对应的线段为 [l,r]
void build(int now, int l, int r)
{
	if (l == r)
	{
		t[now] = a[l];
		return;
	}
	int mid = (l + r) / 2;
	build(now * 2, l, mid);
	build(now * 2 + 1, mid + 1, r);
	t[now] = t[now * 2] + t[now * 2 + 1];
}
// 下传一层懒标记
// 当前节点为 now，对应的线段为 [l,r]
void down(int now, int l, int r)
{
	if (l == r || lazy[now] == 0)
		return;
	int mid = (l + r) / 2;
	t[now * 2] += (mid - l + 1) * lazy[now];
	t[now * 2 + 1] += (r - mid) * lazy[now];
	lazy[now * 2] += lazy[now];
	lazy[now * 2 + 1] += lazy[now];
	lazy[now] = 0;
}
// 做到了 now 节点，对应区间为 [l,r]
// 单点修改：a[x]~a[y] += z
void update(int now, int l, int r, int x, int y, int z)
{
	// 当前区间完全属于要查询的部分就偷个懒
	if (x <= l && r <= y)
	{
		t[now] += (r - l + 1) * z;
		lazy[now] += z;
		return;
	}
	// 下传懒标记
	down(now, l, r);
	// 左子节点：now * 2 [l, mid]
	// 右子节点：now * 2 + 1 [mid + 1, r]
	int mid = (l + r) / 2;
	if (x <= mid)
		update(now * 2, l, mid, x, y, z);
	if (y >= mid + 1)
		update(now * 2 + 1, mid + 1, r, x, y, z);
	t[now] = t[now * 2] + t[now * 2 + 1];
}
// 做到了 now 节点，对应区间为 [l,r]
// 查询 [x,y] 在当前节点中的部分之和
int query(int now, int l, int r, int x, int y)
{
	// 当前区间完全属于要查询的部分就直接返回
	if (x <= l && r <= y)
		return t[now];
	// 下传懒标记
	down(now, l, r);
	// 左子节点：now * 2 [l, mid]
	// 右子节点：now * 2 + 1 [mid + 1, r]
	int mid = (l + r) / 2;
	int res = 0;
	if (x <= mid)
		res += query(now * 2, l, mid, x, y);
	if (y >= mid + 1)
		res += query(now * 2 + 1, mid + 1, r, x, y);
	return res;
}

int my_lower_bound(int x)
{
	// 找到第一个 query(i) 大于等于 x 的 i
	int l = 1;
	int r = n;
	int ans = -1;
	while (l <= r)
	{
		int mid = (l + r) / 2;
		if (query(1, 1, n, 1, mid) >= x)
		{
			ans = mid;
			r = mid - 1;
		}
		else
			l = mid + 1;
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	a[0] = 1;
	a[n + 1] = 1;
	build(1, 1, n);
	while (m--)
	{
		char op;
		cin >> op;
		if (op == 'D')
		{
			int x;
			cin >> x;
			a[x] = 1;
			update(1, 1, n, x, x, 1);
			st.push(x);
		}
		if (op == 'R')
		{
			a[st.top()] = 0;
			update(1, 1, n, st.top(), st.top(), -1);
			st.pop();
		}
		if (op == 'Q')
		{
			int x;
			cin >> x;
			if (a[x] == 1)
			{
				cout << 0 << "\n";
				continue;
			}
			int cnt = query(1, 1, n, 1, x); // x及左边有多少个房子被摧毁了
			int L, R;						// 记录 x左边右边的第一个被摧毁的位置
			if (cnt == 0)
				L = 0; // 左边没有房子被摧毁时，认为左边第一个被摧毁的是 0 号位置
			else
				L = my_lower_bound(cnt);
			if (cnt == st.size())
				R = n + 1; // 左边没有房子被摧毁时，认为右边第一个被摧毁的是 n + 1 号位置
			else
				R = my_lower_bound(cnt + 1);
			cout << R - L - 1 << "\n";
		}
	}
	return 0;
}

O(log⁡n) 查询

树状数组写法

略

线段树写法

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50000;
int n, m;
int a[MAXN + 5]; // 1 表示被摧毁了，0 表示没被摧毁
stack<int> st;   // 记录摧毁的房子
// 线段树
int t[MAXN * 4 + 5];
int lazy[MAXN * 4 + 5];
// 当前节点为 now，对应的线段为 [l,r]
void build(int now, int l, int r)
{
    if (l == r)
    {
        t[now] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(now * 2, l, mid);
    build(now * 2 + 1, mid + 1, r);
    t[now] = t[now * 2] + t[now * 2 + 1];
}
// 下传一层懒标记
// 当前节点为 now，对应的线段为 [l,r]
void down(int now, int l, int r)
{
    if (l == r || lazy[now] == 0)
        return;
    int mid = (l + r) / 2;
    t[now * 2] += (mid - l + 1) * lazy[now];
    t[now * 2 + 1] += (r - mid) * lazy[now];
    lazy[now * 2] += lazy[now];
    lazy[now * 2 + 1] += lazy[now];
    lazy[now] = 0;
}
// 做到了 now 节点，对应区间为 [l,r]
// 单点修改：a[x]~a[y] += z
void update(int now, int l, int r, int x, int y, int z)
{
    // 当前区间完全属于要查询的部分就偷个懒
    if (x <= l && r <= y)
    {
        t[now] += (r - l + 1) * z;
        lazy[now] += z;
        return;
    }
    // 下传懒标记
    down(now, l, r);
    // 左子节点：now * 2 [l, mid]
    // 右子节点：now * 2 + 1 [mid + 1, r]
    int mid = (l + r) / 2;
    if (x <= mid)
        update(now * 2, l, mid, x, y, z);
    if (y >= mid + 1)
        update(now * 2 + 1, mid + 1, r, x, y, z);
    t[now] = t[now * 2] + t[now * 2 + 1];
}
// 做到了 now 节点，对应区间为 [l,r]
// 查询 [x,y] 在当前节点中的部分之和
int query(int now, int l, int r, int x, int y)
{
    // 当前区间完全属于要查询的部分就直接返回
    if (x <= l && r <= y)
        return t[now];
    // 下传懒标记
    down(now, l, r);
    // 左子节点：now * 2 [l, mid]
    // 右子节点：now * 2 + 1 [mid + 1, r]
    int mid = (l + r) / 2;
    int res = 0;
    if (x <= mid)
        res += query(now * 2, l, mid, x, y);
    if (y >= mid + 1)
        res += query(now * 2 + 1, mid + 1, r, x, y);
    return res;
}

// 找到第一个权值前缀和大于等于 x 的 位置
int segtree_lowerbound(int now, int l, int r, int x)
{
    if (l == r)
        return l;
    int mid = (l + r) / 2;
    if (t[now * 2] >= x)
        return segtree_lowerbound(now * 2, l, mid, x);
    return segtree_lowerbound(now * 2 + 1, mid + 1, r, x - t[now * 2]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    a[0] = 1;
    a[n + 1] = 1;
    build(1, 1, n);
    while (m--)
    {
        char op;
        cin >> op;
        if (op == 'D')
        {
            int x;
            cin >> x;
            a[x] = 1;
            update(1, 1, n, x, x, 1);
            st.push(x);
        }
        if (op == 'R')
        {
            a[st.top()] = 0;
            update(1, 1, n, st.top(), st.top(), -1);
            st.pop();
        }
        if (op == 'Q')
        {
            int x;
            cin >> x;
            if (a[x] == 1)
            {
                cout << 0 << "\n";
                continue;
            }
            int cnt = query(1, 1, n, 1, x); // x及左边有多少个房子被摧毁了
            int L, R;                       // 记录 x左边右边的第一个被摧毁的位置
            if (cnt == 0)
                L = 0; // 左边没有房子被摧毁时，认为左边第一个被摧毁的是 0 号位置
            else
                L = segtree_lowerbound(1,1,n,cnt);
            if (cnt == st.size())
                R = n + 1; // 左边没有房子被摧毁时，认为右边第一个被摧毁的是 n + 1 号位置
            else
                R = segtree_lowerbound(1,1,n,cnt + 1);
            cout << R - L - 1 << "\n";
        }
    }
    return 0;
}
上次编辑于: 2024/12/25 16:47:05
贡献者: 代建杉