[数据结构与算法]超市（优先队列，区间动态变化）

超市

• 优先队列，区间 $l,r$ 动态选择的一些小技巧

  本题，就是随时间增加，$g[i]$ 入队

#include <bits/stdc++.h>
#define int long long 
#define Pa pair<int,int> 
using namespace std;

const int N=1e5+5;
struct node 
{ 
    int x,r,w; 
    bool operator < (node b) const { return w>b.w || w==b.w && x>b.x; }
};
int a[N];
vector<node> g[N];
void solve()
{
    int n,m,t;
    cin>>n>>m>>t;
    for(int i=1;i<=n;i++) 
    {
        scanf("%lld",&a[i]);
        g[1].push_back({i,m,a[i]});
    }
    while(t--)
    {
        int x,y,l,r;
        cin>>x>>y>>l>>r;
        if(y<10) y*=10;
        g[l].push_back({x,r,a[x]*y/100});
    }
    priority_queue <node> q;
    for(int i=1;i<=m;i++)
    {
        for(auto it : g[i]) q.push(it); // 小技巧
        while(i>q.top().r) q.pop();
        cout<<q.top().x<<' ';
    }

}
signed main()
{
    int T=1;
    //cin>>T;
    while(T--) solve();
}