题目描述

blablabla

算法1

用map记录有水滴的点，用deque控制水滴爆掉的顺序，每次取出队头，给水滴大小++，当水滴爆掉时，先把右边爆的加入队头，在把左边爆的加入队头，这样就满足题目要求的左边先爆的顺序

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define __lg(x) (int)log2(x)
#define ep emplace
#define x first
#define y second
#define lowbit(x) (x&(-x))
#define T_T 0
#define endl "\n"
#define Endl "\n"
#define ls u<<1
#define rs u<<1|1
#define i128 __int128
#define nmsl cout<<"输出：\t";//农贸税率
#define retrun return 
typedef long long ll;
typedef double db;
typedef ll LL;
typedef unsigned long long ull;
typedef pair<string, int> PSI;
typedef pair<double, double>PDD;
//mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
//mt19937_64 rng(time(0));
int T = 1;

namespace DBG {
    template <class T>
    ostream& operator<<(ostream& os, const vector<T>& v) 
    {
        os << "[ ";
        for (const auto& x : v)os << x << ", ";
        os << "]";
        return os;
    }

    template <class A, class B>
    ostream& operator<<(ostream& os, const map<A, B>& mp) 
    {
        os << "{ ";
        for (const auto& [k, v] : mp)os << k << ":" << v << ", ";
        os << "}";
        return os;
    }

    template <class T>
    void _dbg(const char* f, T t) 
    {
        cerr << f << " = " << t << '\n';
    }

    template <class A, class... B>
    void _dbg(const char* f, A a, B... b) 
    {
        while (*f != ',')cerr << *f++;
        cerr << " = " << a << ", ";
        _dbg(f + 1, b...);
    }
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
}
using namespace DBG;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;
const int N = 2e5 + 5, M = 5e3 + 5;
const ll mod = 1e9 + 7;

#define int ll
#define double long double
typedef pair<int, int> PII;
ll n, m, x, y, k;
PII a[M];
bool st[N];

void jiangly()
{
    cin >> n >> m >> k;
    map<int, int>mp;//记录有水的点
    for (int i = 0; i < m; i++)
    {
        int u, v; cin >> u >> v;
        mp[u] = v;
    }
    for (int i = 0; i < k; i++)
    {
        int p; cin >> p;
        mp[p]++;
        if (mp[p] >= 5)
        {
            deque<int>q;//控制水滴爆掉的顺序
            q.push_front(p);
            set<int>s;//记录在队列中的点
            s.insert(p);
            while (q.size())
            {
                p = q.front();
                mp.erase(p);//清除爆掉的点
                q.pop_front();
                s.erase(p);
                auto it = mp.upper_bound(p);//找右边最近的水滴
                if (it != mp.end())
                {
                    mp[(*it).x]++;
                    if (mp[(*it).x] >= 5)
                        if (!s.count(it->x))//看该点是否已在队列中，不能重复加入
                            q.push_front((*it).x), s.insert(it->x);
                }
                it = mp.lower_bound(p);//找左边最近的水滴
                if (it != mp.begin())
                {
                    it--;
                    mp[(*it).x]++;
                    if (mp[(*it).x] >= 5)
                        if (!s.count(it->x))
                            q.push_front((*it).x), s.insert(it->x);
                }
            }
        }
        cout << mp.size() << endl;
    }

}
/*

*/
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //cout << fixed << setprecision(15);
    //cin >> T;
    while (T--)jiangly();
    return 0;
}