头像

TheWall




离线:10小时前


最近来访(0)


TheWall
4天前

题目描述

一家旅馆共有 N 个房间,这 N 个房间是连成一排的,标号为 1∼N。

现在有很多旅客以组为单位前来入住,每组旅客的数量可以用 Di 来表示。

旅店的业务分为两种,入住和退房:

旅客入住时,第 i 组旅客需要根据他们的人数 Di,给他们安排 Di 个连续的房间,并且房间号要尽可能的小。如果房间不够,则无法安排。
旅客退房时,第 i 组旅客的账单将包含两个参数 Xi 和 Di,你需要将房间号 Xi 到 Xi+Di−1 之间的房间全部清空。
现在你需要帮助该旅馆处理 M 单业务。

旅馆最初是空的。

输入数据
第一行输入两个用空格隔开的整数 N 和 M。

接下来 M 行将描述 M 单业务:

“1 Di”表示这单业务为入住业务。

“2 Xi Di”表示这单业务为退房业务。

输出数据
每个入住业务输出一个整数,表示要安排的房间序列中的第一个房间的号码。

如果没办法安排,则输出 0。

每个输出占一行。

数据范围
1≤Di≤N≤50000,
1≤M<50000

样例

输入样例:
10 6
1 3
1 3
1 3
1 3
2 5 5
1 6
输出样例:
1
4
7
0
5

线段树 + 延迟更新

多写写题解加深理解下。
设序列1-n,起初都为0,当被占用则为1。分析题意得出有2种操作

  1. 找出序列1-n中第一个长度为len的连续0子串,返回该子串左端点,并将该子串全部置为1。
  2. 给定[l,r],使该区间的值全部置为0。

可以看出具有区间查询、区间修改的特点,所以考虑使用线段树。
使用线段树最应该考虑的问题是:我们需要维护的信息是什么?如何构造合适的变量去维护?
可以看出对于任意区间[l,r],我们需要快速获取其最长连续0子串的长度,由经验得:使用ld以l为起点最长0子串长度,rd以r为终点最长0子串长度两个变量,就能够从ls和rs的信息中更新出d最长连续9子串的长度。至此我们就可以完成build函数和pushup函数了。
如何完成操作1,即如何查询答案?首先记住我们的目标是找出长度为len的连续0子串,并返回其左端点编号。在我们的query函数中,对于任意树节点所表示的区间[pi,pr]:

  • 若该区间p.d < len,则在该区间找不到答案,否则答案就在该区间内
  • 若p.d == len && p.d == pr - pi + 1,表示该区间刚好合适,pi就是答案
  • 若p.ls.d >= len,答案就在左子区间里,否则答案要么是完全在右子区间里或者左区间的.rd和右区间的.ld组成
  • 若p.ls.rd + p.rs.ld >= len,则答案为 p.ls.r - p.ls.rd + 1。
  • 递归右子区间。

考虑延迟更新?由于我们的操作要么是将一段序列全部变为1,要么全部0。当操作区间[l,r]覆盖了某个树节点区间[pi,pr],则不需要继续深入子节点进行更新数据,直接将该区间的信息更新即可,并加以标记。

时间复杂度

$O(mlogn)$

C++ 代码

#include <iostream>
#include <cmath>
using namespace std;

const int N = 50010;

struct Seg
{
    int l, r;
    int d, ld, rd;
    int lazy;
} tr[N * 4];

int n, m;

void pushup(Seg &a, Seg &b, Seg &c)
{
    a.d = max(max(b.d, c.d), b.rd + c.ld);
    a.ld = (b.r - b.l + 1) == b.d ? b.d + c.ld : b.ld;
    a.rd = (c.r - c.l + 1) == c.d ? c.d + b.rd : c.rd;
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void change(int u, int x)
{
    tr[u].d = tr[u].ld = tr[u].rd = x;
}

void pushdown(int u)
{
    if (!tr[u].lazy) return;
    if (tr[u].lazy == 1)
    {
        change(u << 1, 0);
        change(u << 1 | 1, 0);
    }
    else
    {
        change(u << 1, tr[u << 1].r - tr[u << 1].l + 1);
        change(u << 1 | 1, tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1);
    }
    tr[u << 1].lazy = tr[u << 1 | 1].lazy = tr[u].lazy;
    tr[u].lazy = 0;
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, l, 1, 1, 1, 0};
    else
    {
        tr[u].l = l, tr[u].r = r;
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}



int query(int u, int len)
{
    if (tr[u].d < len) return 0;
    if (tr[u].d == len && tr[u].d == (tr[u].r - tr[u].l + 1)) return tr[u].l;
    pushdown(u);
    if (tr[u << 1].d >= len) return query(u << 1, len); //在左半区
    if (tr[u << 1].rd + tr[u << 1 | 1].ld >= len) return tr[u << 1].r - tr[u << 1].rd + 1;
    return query(u << 1 | 1, len);
}

void modify(int u, int l, int r, int k)
{
    if (l <= tr[u].l && tr[u].r <= r)
    {
        if (k == 1)
        {
            //开房
            change(u, 0);
        }
        else
        {
            //退房
            change(u, tr[u].r - tr[u].l + 1);
        }
        tr[u].lazy = k;
    }
    else
    {
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (l <= mid) modify(u << 1, l, r, k);
        if (r > mid) modify(u << 1 | 1, l, r, k);
        pushup(u);
    }
}

int main()
{
    cin >> n >> m;
    build(1, 1, n);
    for (int i = 1; i <= m; i ++)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int c;
            cin >> c;
            int left = query(1, c);
            cout << left << endl;
            if (left)
            {
                modify(1, left, left + c - 1, 1);
            }
        }
        else
        {
            int l, r;
            cin >> l >> r;
            modify(1, l, l + r - 1, -1);
        }
    }
}




TheWall
6天前

扫描线+线段树

本题使用扫描线算法求解,采用线段树优化。由于求解周长与求解面积特点不同,我们可以对该图形进行横竖两次求解。即扫描线沿X轴和Y轴各求解一遍。虽然本题数据范围较小,但我们依然采用线段树+离散化标准解法求解。
1.线段树节点记录信息为:cnt表示区间被覆盖次数,当区间完全被覆盖时,区间有效长度len(扫描线长度)为区间r-l,否则就等于左右子区间len。
2.由于扫描线算法特殊处,我们维护的线段树只会使用tr[1]即根节点信息。并且对于区间更新(+1,-1)是成对(扫描线算法中的入边和出边概念)出现的,所以不必使用延迟更新技巧。
3.答案的求解:每加入一条边到线段树中,记加入扫描线有效长度pre = tr[1].len,加入后则为after = tr[1].len。则加入此边后,答案+=abs(pre - after)。
4.当排序边时,如果有2个边的x值相同时,一定要令入边(k=1)在前。因为此时由于2条边是重合状态,由3中答案求解过程可以发现,如果此时先处理入边再处理出边,则处理结果为正确,否则错误。具体为何,结合下图自己模拟下便知。
QQ截图20220921232523.jpg

C++ 代码

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 5010, LEN = 10001;

int n, res = 0;
struct ScanLine
{
    int x, y1, y2, k;
    bool operator< (const ScanLine &l) const
    {
        return x != l.x ? x < l.x : k > l.k;
    }
} line[N * 2];

struct Rec
{
    int x1, x2, y1, y2;
} rec[N];

struct Tree
{
    int l, r, len, cnt;
} tr[N * 8];

vector<int> ys;

int get(int x)
{
    return lower_bound(ys.begin(), ys.end(), x) - ys.begin();
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, 0, 0};
    if (l != r)
    {
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
    }
}

void pushup(int u)
{
    if (tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l];
    else tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
}

void modify(int u, int l, int r, int k)
{
    if (l <= tr[u].l && tr[u].r <= r)
    {
        tr[u].cnt += k;
        pushup(u);
    }
    else 
    {
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (l <= mid) modify(u << 1, l, r, k);
        if (r > mid) modify(u << 1 | 1, l, r, k);
        pushup(u);
    }
}

void solve_xy()
{
    ys.clear();
    sort(line, line + 2 * n);
    for (int i = 0; i < 2 * n; i ++) ys.push_back(line[i].y1), ys.push_back(line[i].y2);
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    build(1, 0, ys.size() - 2);
    int pre = 0;
    for (int i = 0; i < 2 * n; i ++)
    {
        modify(1, get(line[i].y1), get(line[i].y2) - 1, line[i].k);
        res += abs(tr[1].len - pre);
        pre = tr[1].len;
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        rec[i] = {x1 + LEN, x2 + LEN, y1 + LEN, y2 + LEN};
    }

    for (int i = 0; i < n; i ++)
    {
        line[i << 1] = {rec[i].x1, rec[i].y1, rec[i].y2, 1};
        line[i << 1 | 1] = {rec[i].x2, rec[i].y1, rec[i].y2, -1};
    }

    solve_xy();

    for (int i = 0; i < n; i ++)
    {
        line[i << 1] = {rec[i].y1, rec[i].x1, rec[i].x2, 1};
        line[i << 1 | 1] = {rec[i].y2, rec[i].x1, rec[i].x2, -1};
    }

    solve_xy();

    cout << res << endl;
}




TheWall
6天前

看题解说由于矩阵边界点不能取,所以要y + h - 1, x + w - 1。我的代码写法参考了yxc的247. 亚特兰蒂斯写法,去掉-1就可以过。萌新自己扣这种边界问题有点不能理解,希望大佬们帮看看哈

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>

using namespace std;
typedef long long LL;
const int N = 10010;

struct ScanLine
{
    LL x, y1, y2, k;
    bool operator< (const ScanLine &l)const
    {
        return x < l.x || x == l.x && k < l.k;
    }
} line[N * 2];

struct Tree
{
    int l, r;
    LL maxc, lazy;
} tr[N * 8];

int n, w, h;
vector<LL> ys;

void build(int u, int l, int r)
{
    tr[u] = {l, r, 0, 0};
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

void spread(int u)
{
    if (tr[u].lazy)
    {
        tr[u << 1].maxc += tr[u].lazy;
        tr[u << 1].lazy += tr[u].lazy;
        tr[u << 1 | 1].maxc += tr[u].lazy;
        tr[u << 1 | 1].lazy += tr[u].lazy;
        tr[u].lazy = 0;
    }
}

void pushup(int u)
{
    tr[u].maxc = max(tr[u << 1].maxc, tr[u << 1 | 1].maxc);
}

void modify(int u, int l, int r, int k)
{
    if (l <= tr[u].l && tr[u].r <= r) 
    {
        tr[u].lazy += k;
        tr[u].maxc += k;
    }
    else
    {
        spread(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (l <= mid) modify(u << 1, l, r, k);
        if (r > mid) modify(u << 1 | 1, l, r, k);
        pushup(u);
    }
}

int get(LL x)
{
    return lower_bound(ys.begin(), ys.end(), x) - ys.begin();
}


int main()
{
    while (cin >> n >> w >> h)
    {
        ys.clear();
        for (int i = 0; i < n; i ++) 
        {
            LL x, y, c;
            cin >> x >> y >> c;
            line[i << 1] = {x, y, y + h, c}, line[i << 1 | 1] = {x + w, y, y + h, -c};
            // 原本都是y + h - 1 或者 x + w - 1,但不能过
            ys.push_back(y), ys.push_back(y + h);
        }

        sort(ys.begin(), ys.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());

        sort(line, line + 2 * n);

        build(1, 0, ys.size() - 2);

        LL res = 0;
        for (int i = 0; i < 2 * n; i ++)
        {
            modify(1, get(line[i].y1), get(line[i].y2) - 1, line[i].k);
            res = max(res, tr[1].maxc);
        }
        cout << res << endl;
    }
}



TheWall
10天前

太坑了




TheWall
28天前
区间重叠次数 + 差分优化

对于任意2颗钻石a, b,其“接受”区间可表示为[a, a + k], [b, b + k]。当2个区间有重叠时,才能保证这两个钻石尺寸差不超过K,符合题目条件。求出某重叠次数最多的区间即为答案。
利用差分思想,对于任意钻石a而言,区间[a, a + k]的重叠次数+1。
QQ截图20220830213955.jpg

时间复杂度

o(n)

C++ 代码

#include <iostream>
#include <cmath>
using namespace std;
const int N = 10010;

int n, k, b[N], ans = 0;

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++)
    {
        int x;
        cin >> x;
        b[x] ++, b[x + k + 1] --;
    }
    for (int i = 1; i < N; i ++) b[i] += b[i - 1];
    for (int i = 1; i < N; i ++) ans = max(ans, b[i]);
    cout << ans << endl;

}