「LibreOJ β Round」ZQC 的手办（线段树+堆）

发表于 |
字数统计: 1,455字 | 阅读时长 ≈ 7min

问题描述

众所周知，ZQC 是个很喜欢收纳手办的大佬，他平时在写题前会先扫视一下桌面上排开的小姐姐们以获取灵感。假设他有 $ n(1 \leq n \leq 5\times 10 ^ 5) $ 个手办，小手办们排成一排，每个手办按照入手批次从第 $ 1 $ 个到第 $ n $ 个被贴上了一个标号 $ a_i(1 \leq a_i \leq 10 ^ 9) $。有两个熊孩子到 ZQC 家里玩，熊孩子 A 不断地改掉标签并不停地提问熊孩子 B。由于熊孩子 B 太笨，经常回答不上来，熊孩子 A 表示很生气，ZQC 为了世界和平（把熊孩子哄高兴好让它们帮忙把标签贴回去），大发慈悲地帮助熊孩子 B 回答一系列问题。假设一共 $ m(1 \leq m \leq 5\times 10 ^ 5) $ 次操作，两种操作分别为：

  • $ \texttt{1 a b k} $ 将数列 $ [a, b] $ 这个区间中所有比 $ k(1 \leq k \leq 10 ^ 9) $ 小的数改为 $ k $；
  • $ \texttt{2 a b k x} $ 查询 $ [a, b] $ 的区间中比 $ k(1 \leq k \leq 10 ^ 9) $ 小的最小的 $ x(1 \leq x \leq 10^5) $ 个数。

ZQC 最后成功维护了世界正义，请在每次查询时输出熊孩子 A 所要的回答。

输入格式

第一行为 $ n $，表示手办总数。
接下来一行 $ n $ 个数 $a_1,a_2,…,a_n$，$ a_i $ 表示第 $i$ 个手办的标号。
接下来一行为 $ m $，表示总操作数。
接下来 $ m $ 行，格式见「题目描述」。

输出格式

对于每次查询，输出一行 $ x $ 个数，每个数中间以空格间隔，按从小到大顺序排列；如果区间内小于 $ k $ 的数不足 $ x $ 个，输出 $ -1 $。

样例输入

1
2
3
4
5
6
7
3
1 2 3
4
1 1 2 2
2 1 3 1 3
2 1 3 2 1
2 1 3 3 2

样例输出

1
2
3
-1
-1
2 2

样例解释

开始序列为 ${1,2,3}$；
第一次操作修改后的序列为 ${2,2,3}$；
第二次操作查询时，区间内最小的 $3$ 个数依次为 $2,2,3$，因为 $3$ 不小于 $1$ 所以答案为 $-1$；
第三次操作查询时，区间内最小的 $1$ 个数为 $2$，因为 $2$ 不小于 $2$ 所以答案为 $-1$；
第四次操作查询时，区间内最小的 $2$ 个数依次为 $2,2$，因为 $2$ 小于 $3$ 所以答案为 $2,2$。

提示

$\sum{x}\leq 5\times 10^6$
输出总数量不超过 $2\times 10^6$ 个整数，包括 $-1$。

出题人的关怀：由于输入规模较大，建议使用读入优化。

注意到 $\sum x\leq5\times10^6$

考虑用线段树维护区间最小值和最小值的位置，用堆来暴力处理查询，即先将区间最小值加到堆中，取出后拆成两个区间，分别将两个子区间的区间最小值加进去，这样操作 $x$ 次即可

复杂度为 $O(\log n\sum x)$

修改操作直接打 $lazy$ 就行了

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define N 500005
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
inline int _R()
{
    char t=GC;int x=0;
    while(t<48||t>57)t=GC;
    for(;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
    return x;
}
struct minn{int v,x;};
struct data{int l,r;minn v;};
bool operator<(data a,data b){return a.v.v>b.v.v;}
int n,a[N],m,ans[N],tp;
struct node
{
    node *ls,*rs;
    int Min,pos,lazy;
}seg[N<<1],*rt,*tl,*null;
void Init()
{
    rt=tl=null=seg;
    null->ls=null->rs=null;
}
void update(node *p)
{
    node *l=p->ls,*r=p->rs;
    if(l->Min<r->Min)p->Min=l->Min,p->pos=l->pos;
    else p->Min=r->Min,p->pos=r->pos;
}
void build(node *&p,int l,int r)
{
    p=++tl;p->ls=p->rs=null;
    if(l==r){p->Min=a[l];p->pos=l;return;}
    int mid=l+r>>1;
    build(p->ls,l,mid);
    build(p->rs,mid+1,r);
    update(p);
}
void putdown(node *p)
{
    node *l=p->ls,*r=p->rs;
    int d=p->lazy;p->lazy=0;
    l->Min=max(l->Min,d);
    l->lazy=max(l->lazy,d);
    r->Min=max(r->Min,d);
    r->lazy=max(r->lazy,d);
}
void modify(node *p,int l,int r,int x,int y,int d)
{
    if(p->Min>=d)return;
    if(p->lazy)putdown(p);
    if(x<=l&&y>=r)
    {
        p->Min=max(p->Min,d);
        p->lazy=max(p->lazy,d);
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)modify(p->ls,l,mid,x,y,d);
    if(y>mid)modify(p->rs,mid+1,r,x,y,d);
    update(p);
}
minn getmin(node *p,int l,int r,int x,int y)
{
    if(x<=l&&y>=r)return (minn){p->Min,p->pos};
    if(p->lazy)putdown(p);
    int mid=l+r>>1;minn tl,tr;
    if(x>mid)return getmin(p->rs,mid+1,r,x,y);
    if(y<=mid)return getmin(p->ls,l,mid,x,y);
    tl=getmin(p->ls,l,mid,x,y);
    tr=getmin(p->rs,mid+1,r,x,y);
    return tl.v<tr.v?tl:tr;
}
int main()
{
    int i,j,k,x,y,z;
    n=_R();
    for(i=1;i<=n;i++)a[i]=_R();
    Init();build(rt,1,n);
    m=_R();
    for(i=1;i<=m;i++)
    {
        j=_R();
        if(j==1)
        {
            x=_R();y=_R();z=_R();
            modify(rt,1,n,x,y,z);
        }
        else
        {
            x=_R();y=_R();k=_R();z=_R();
            priority_queue<data>Q;tp=0;
            Q.push((data){x,y,getmin(rt,1,n,x,y)});
            while(Q.size()&&tp<z)
            {
                data tmp=Q.top();Q.pop();
                if(tmp.v.v>=k)break;
                ans[++tp]=tmp.v.v;
                if(tmp.v.x>tmp.l)Q.push((data){tmp.l,tmp.v.x-1,getmin(rt,1,n,tmp.l,tmp.v.x-1)});
                if(tmp.v.x<tmp.r)Q.push((data){tmp.v.x+1,tmp.r,getmin(rt,1,n,tmp.v.x+1,tmp.r)});
            }
            if(tp<z)printf("-1");
            else for(k=1;k<=tp;k++)printf("%d ",ans[k]);
            puts("");
        }
    }
}