2024.8.24-美团

第3题-塔塔商店

线段树，因为需要返回区间最大值的id，所以对于建树、更新、检索部分需要进行修改

#include<bits/stdc++.h>

using namespace std;

#define lc p<<1
#define rc p<<1|1
const int N = 1e5 + 5;
int c[N];
struct segtree{
    struct node{
        int l, r, id;
    }tree[N*4];
    vector<int>w;
    void init(int m, vector<int>& d) {
        w.resize(m);
        w = d;
    }

    int compare(int x, int y) {
        if (w[x] > w[y] || (w[x] == w[y] && x < y))
            return x;
        return y;
    }

    void build(int p, int l, int r){
        tree[p] = {l, r, l};
        if(l == r) {
            return ;
        }
        int m = (l + r) >> 1;
        build(lc, l, m);
        build(rc, m + 1, r);
        tree[p].id = compare(tree[lc].id, tree[rc].id);
    }

    //单点修改
    void update(int p, int x, int k){
        if(tree[p].l == x && tree[p].r == x){
            tree[p].id = x;
            w[x] = k;
            return ;
        }
        int m = (tree[p].l + tree[p].r) >> 1;
        // cout<<lc<<" "<<x<<endl;
        if(x <= m) update(lc, x, k);
        else update(rc, x, k);
        tree[p].id = compare(tree[lc].id, tree[rc].id);
    }

    //区间查询
    int query(int p, int l, int r){
        if(l > tree[p].r || tree[p].l > r) return -1;
        if(l <= tree[p].l && tree[p].r <= r)
            return tree[p].id;
        int m = (tree[p].l + tree[p].r) >> 1;
        int left = -1, right = -1;
        if(l <= m) left = query(lc, l, r);
        if(r > m) right = query(rc, l, r);
        if(left == -1) return right;
        if(right == -1) return left;
        return compare(left, right);
    }
}seg[2];


int main(){
    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= m; i ++) cin>>c[i];
    vector<int> arr[2], B(m + 2);
    arr[0].resize(m + 2, -1);
    arr[1].resize(m + 2, -1);
    for (int i = 1; i <= m; ++i) {
        cin >> B[i];
        arr[B[i]][i] = c[i];
    }
    for (int i = 0; i < 2; ++i) {
        seg[i].init(m + 1, arr[i]);
        seg[i].build(1, 1, m);
    }
    while(n --){
        int x, y, t, k;
        cin>>x>>y>>t>>k;
        while(k --){
            int u = seg[t].query(1, x, y);
            int value = seg[t].w[u];
            if(value == -1){
                cout<<-1<<" ";
                break;
            }
            else cout<<u<<' ';
            seg[t].update(1, u, -1);
        }
        cout<<endl;
    }

    return 0;
}