题解：P10711 [NOISG 2024 Prelim] Amusement Park

思路

其实我觉得这题不到紫，但是我做这道题的时候因为一个不算很常见的问题调了很久（后面会说到）。

首先看题面，我们发现用线段树维护前两个操作是十分简单的，难点是第三个。其实第三个操作我们每次有线段树维护左边第一个能用的，然后暴力减去即可，这么做看起来很暴力，但其实复杂度是对的，因为当你全删完了也就不能再多删了。

这个时候你会发现在第三个操作也是要修改的，但他还有返回值，那么你的 pushup 函数就不能写在最后面了。否则这个 pushup 就跟没有一样。

我的代码中因为最开始看反了

w

，所以把那俩换了一下。

说句实话，对于能来做紫的大家，这道题真的没有任何的思维难度，所以我也没什么好讲的。这个题的难点我个人认为难点在代码，所以 ——

下面是代码。

code

CPP

#include <bits/stdc++.h>
#define fi first
#define se second
#define ull unsigned ll
#define pii pair<int,int>
#define zyd cerr<<"zydakioi\n"
#define look_memory cerr<<abs(&M2-&M1)/1024.0/1024
#define look_time cerr<<(clock()-Time)*1.0/CLOCKS_PER_SEC
#define int long long
#define ls rt<<1
#define rs rt<<1|1
#define mid ((l+r)/2)
#define se second
#define fi first
#define mpr make_pair
using namespace std;
bool M2;int Time=clock();
void Main(int year,string s);
//what I should remember:
//have I deleted Main()?
//have I deleted #define int long long?
const int N = 2e5 + 10;
struct node{
    int sum, id, mi, join;
}t[N << 2];
int q, n, cnt;
pii print[N];
void pushup(int rt)
{
    if(t[ls].id == 1ll || t[rs].id == 1ll) t[rt].id = 1ll;
    else if(t[ls].id == 2ll || t[rs].id == 2ll) t[rt].id = 2ll;
    else t[rt].id = 0ll;
    t[rt].mi = min(t[rs].mi, t[ls].mi);
    t[rt].join = max(t[ls].join, t[rs].join);
}
void add(int rt, int l ,int r, int p, int num, int id)
{
    if(l == r)
    {
        t[rt].sum = t[rt].mi = num;
        t[rt].id = id; 
        t[rt].join = 1ll;
        return ;
    }
    if(p <= mid) add(ls, l ,mid, p, num, id);
    else add(rs, mid + 1, r, p, num, id);
    pushup(rt);
}
void del(int rt, int l, int r, int p)
{
    if(l == r)
    {
        t[rt].sum = t[rt].id =  t[rt].join = 0ll;
        t[rt].mi = 1e9;
        return ;
    }
    if(p <= mid) del(ls, l ,mid, p);
    else del(rs, mid + 1, r, p);
    pushup(rt);
}
bool check(int rt, int num)
{
    if(!t[rt].join) return 0;
    if(t[rt].id == 1) return 1;
    else if(t[rt].id == 2 && t[rt].mi <= num) return 1;
    else return 0;
}
pii query(int rt , int l, int r, int num)
{
    if(l == r)
    {
        if(t[rt].id == 1)
        {
            pii res = mpr(l, min(t[rt].sum, num));
            t[rt].sum = t[rt].sum - res.se;
            if(!t[rt].sum) 
            {
                t[rt].id = t[rt].join = 0ll;
                t[rt].mi = 1e9;
            }
            else t[rt].mi = t[rt].sum;
            return res;
        }
        else if(t[rt].id == 2)
        {
            if(t[rt].sum > num) return mpr(l, 0ll);
            else
            {
                pii res = mpr(l, t[rt].sum);
                t[rt].sum = 0ll;
                t[rt].id = t[rt].join = 0ll;
                t[rt].mi = 1e9;   
                return res; 
            }
        }
        else return mpr(l, 0ll);
    }
    pii res = mpr(0,0);
    if(check(ls, num)) res = query(ls, l, mid, num);
    else res = query(rs, mid + 1, r, num);
    pushup(rt);
    return res;
}
void build(int rt, int l,int r)
{
    if(l == r)
    {
        t[rt].mi = 1e9;
        return ;
    }
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(rt);
}
int ask(int rt,int l,int r,int p)
{
    if(l==r) return t[rt].id;
    if(p<=mid) return ask(ls,l,mid,p);
    else return ask(rs,mid+1,r,p);
}
signed main()
{
    freopen("bus.in","r",stdin);
    freopen("bus.out","w",stdout);
    ios::sync_with_stdio(0);
	cin.tie(0); 
    cout.tie(0);
    cin >> q;
    build(1, 1, 2e5);
    while(q--)
    {
        int opt, x, y;
        cin >> opt;
        if(opt == 1)
        {
            cin >> x >> y;
            if(y == 1) y = 0;
            else y = 1;
            add(1, 1, 2e5, ++n, x, y + 1);
        }
        else if(opt == 2)
        {
            cin >> x;
            del(1, 1, 2e5, x);
        }
        else
        {
            cin >> x;
            while(x)
            {
                pii p = query(1, 1, 2e5, x);
                x -= p.se;
                int t=ask(1,1,2e5,3);
                if(p.se) print[++cnt] = p;
                else break;            
            }
            cout << cnt << '\n';
            for(int i = 1;i <= cnt; i++)
            {
                cout << print[i].fi << " " << print[i].se << '\n';
            }
            cnt = 0;
        }
    }
	//Main(2025,"NOIP");
	return 0;
}
void Main(int year,string s)
{
	bool M1;
	cerr<<"memory:"<<' ';
	look_memory;
	cerr<<"MB"<<'\n';
	cerr<<"time:"<<' ';
	look_time;	
	cerr<<"s"<<'\n';
	cerr<<s<<year<<"：RP++"<<'\n';
	return;
}

题解：P10711 [NOISG 2024 Prelim] Amusement Park

文章操作

思路

code

相关推荐

评论

题解：P10711 [NOISG 2024 Prelim] Amusement Park