loj504 zqc的手办

  • 1 a b k 将数列 [a,b] 这个区间中所有比 $k(1≤k≤10^9)$ 小的数改为k;
    • 用个$tag$就可以维护了,只要区间的$min$值小于它,那么需要更新,遍历到了单点直接修改即可。
  • 2 a b k x 查询 [a,b] 的区间中比$k(1≤k≤10^9)$小的最小的 $x(1 \leq x \leq 10^5)$个数。
    • 只要这个区间最小的$x$个值,而且$\sum x \leq 5\times 10^6$,所以可以考虑只询问出这$x$个数,然后…为了使这个的复杂度顶多多一个$log$,维护一个堆,堆里压入区间及这个区间对应的最小值和最小值的位置,每次在区间里先找最小值的位置设为$pos$,把这个最小值压入答案,然后在$[l,pos-1]$和$[pos+1,r]$中再次询问最小值及其位置,压入这个堆,继续直到发现没有小于$k$的值或者已经找到了最小的$x$个数。这样的复杂度是$(\sum x)log_2^{(\sum x)}$的。
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <bits/stdc++.h>
using namespace std;
const int maxn=5*1000000+5;
const int inf=0x3f3f3f3f;
inline void writeout(int x)
{
if(x==0) {putchar('0');return;}
if(x<0) putchar('-');
static char s[21];int idx=0;
while(x>0) s[++idx]=x%10+'0',x/=10;
while(idx) putchar(s[idx--]);
}
int a[maxn],n,m;
#define lson (o<<1)
#define rson (o<<1|1)
#define MP make_pair
typedef pair<int ,int > pii;
int res[maxn],idx=0;
struct info{
int l,r,val,pos;
info(int l=0,int r=0,int val=0,int pos=0): l(l),r(r),val(val),pos(pos) {}
bool operator<(const info&oth)const{
return val>oth.val;
}
};
priority_queue<info> pq;
struct intervaltree{
int minv[maxn<<2],cov[maxn<<2],mpos[maxn<<2];
void maintain(int o,int l,int r)
{
if(l<r) {
minv[o]=inf;
if(minv[o]>minv[lson]) minv[o]=minv[lson],mpos[o]=mpos[lson];
if(minv[o]>minv[rson]) minv[o]=minv[rson],mpos[o]=mpos[rson];
}
if(cov[o]>0) {
if(minv[o]<cov[o]) {
minv[o]=cov[o];
}
}
}
void build(int o,int l,int r)
{
if(l>r) return;
if(l==r) minv[o]=a[l],cov[o]=0,mpos[o]=l;
else{
int mid=(l+r)>>1;
minv[o]=inf;
build(lson,l,mid);
build(rson,mid+1,r);
maintain(o,l,r);
}
}
void getcov(int o,int l,int r,int val)
{
if(minv[o]>=val) return;
cov[o]=val;
maintain(o,l,r);
}
void pushdown(int o,int l,int r)
{
int mid=(l+r)>>1;
if(cov[o]>0){
getcov(lson,l,mid,cov[o]);
getcov(rson,mid+1,r,cov[o]);
cov[o]=0;
maintain(o,l,r);
}
}
pair<int ,int > Qmin(int o,int l,int r,int ql,int qr)
{
if(ql>qr) return MP(INT_MAX,-1);
if(ql>r || qr<l) return MP(INT_MAX,-1);
if(ql<=l && r<=qr) return MP(minv[o],mpos[o]);
else{
int mid=(l+r)>>1;
pii ret=MP(INT_MAX,-1),tmp;
pushdown(o,l,r);
if(ql<=mid) {
tmp=Qmin(lson,l,mid,ql,qr);
if(ret.first>tmp.first) ret=tmp;
}
if(qr>mid) {
tmp=Qmin(rson,mid+1,r,ql,qr);
if(ret.first>tmp.first) ret=tmp;
}
return ret;
}
}
void Ucov(int o,int l,int r,int ql,int qr,int val)
{
if(ql>r || qr<l) return;
if(ql<=l && r<=qr) {getcov(o,l,r,val);return;}
else{
int mid=(l+r)>>1;
pushdown(o,l,r);
if(ql<=mid) Ucov(lson,l,mid,ql,qr,val);
if(qr>mid) Ucov(rson,mid+1,r,ql,qr,val);
maintain(o,l,r);
}
}
void Qres(int ql,int qr,int lim,int num)
{
while(!pq.empty()) pq.pop();
idx=0;
pii ini=Qmin(1,1,n,ql,qr);
if(ini.first>=lim) return;
pq.push(info(ql,qr,ini.first,ini.second));
for(int i=1;i<=num && !pq.empty();i++){
info tp=pq.top();pq.pop();
if(tp.val>=lim) return;
int l=tp.l,r=tp.r;
res[++idx]=tp.val;
if(idx==lim) return;
pii p1=Qmin(1,1,n,l,tp.pos-1),p2=Qmin(1,1,n,tp.pos+1,r);
if(p1.first!=INT_MAX && p1.first<lim) pq.push(info(l,tp.pos-1,p1.first,p1.second));
if(p2.first!=INT_MAX && p2.first<lim) pq.push(info(tp.pos+1,r,p2.first,p2.second));
}
}
} Tree;
inline int readint()
{
char c;int tmp=0,x=1;c=getchar();
while(!isdigit(c)){if(c=='-') x=-1;c=getchar();}
while(isdigit(c)){tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
int main()
{
n=readint();
for(int i=1;i<=n;i++) a[i]=readint();
Tree.build(1,1,n);
m=readint();
int op,a,b,x,k;
for(int i=1;i<=m;i++){
op=readint();
if(op==1){
a=readint(),b=readint(),k=readint();
Tree.Ucov(1,1,n,a,b,k);
}else{
a=readint(),b=readint(),k=readint(),x=readint();
Tree.Qres(a,b,k,x);
if(idx<x) printf("-1\n");
else{
for(int i=1;i<=x;i++) printf("%d ",res[i]);
printf("\n");
}
}
}
return 0;
}