目录
显示
题目链接
题解
思路同 [NOI2010]超级钢琴 和 [十二省联考 2019]异或粽子。
我们用线段树维护区间最小值，以及最小值所在位置。
设 \((l,r,x,p)\) 这个四元组表示区间 \([l,r]\)，该区间最小值为 \(x\)，最小值所在位置为 \(p\)。
对于每个询问 \([l,r]\)，我们先将该区间的最小值和其所在位置求出，将 \((l,r,x,p)\) 插入堆中。
我们每次从堆顶取出最小的 \(x\)，计入答案。
每取出一个四元组 \((l,r,x,p)\) 后，我们尝试求出 \([l,p-1]\) 和 \([p+1,r]\) 这两个区间的最小值（如果存在），将相应的信息继续插入堆中即可。重复上述过程，直到取足 \(x\) 个数，或是无法再取为止。
// Problem: #504. 「LibreOJ β Round」ZQC 的手办
// Contest: LibreOJ
// URL: https://loj.ac/problem/504
// Memory Limit: 256 MB
// Time Limit: 4000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct seg
{
int mina,pos,tag;
bool operator<(const seg&a)const
{
return mina<a.mina||(mina==a.mina&&pos<a.pos);
}
}s[2000005];
struct node
{
int l,r,mina,pos;
bool operator>(const node&a)const
{
return mina>a.mina||(mina==a.mina&&pos>a.pos);
}
};
int a[500005];
void pushup(int root)
{
if(s[root<<1].mina<s[root<<1|1].mina)
s[root].mina=s[root<<1].mina,s[root].pos=s[root<<1].pos;
else
s[root].mina=s[root<<1|1].mina,s[root].pos=s[root<<1|1].pos;
}
void pushdown(int root,int l,int r)
{
if(s[root].tag)
{
int tag=s[root].tag;
s[root<<1].mina=max(s[root<<1].mina,tag);
s[root<<1|1].mina=max(s[root<<1|1].mina,tag);
s[root<<1].tag=s[root<<1|1].tag=tag;
s[root].tag=0;
}
}
void build(int root,int l,int r)
{
if(l==r)
{
s[root].mina=a[l],s[root].pos=l;
return;
}
int mid=(l+r)>>1;
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
pushup(root);
}
void update(int root,int cl,int cr,int l,int r,int x)
{
if(r<cl||cr<l)return;
if(l<=cl&&cr<=r)
{
if(x>s[root].mina)
s[root].mina=x,s[root].tag=x;
return;
}
pushdown(root,cl,cr);
int mid=(cl+cr)>>1;
update(root<<1,cl,mid,l,r,x);
update(root<<1|1,mid+1,cr,l,r,x);
pushup(root);
}
seg query(int root,int cl,int cr,int l,int r)
{
if(r<cl||cr<l)return {1<<30,0,0};
if(l<=cl&&cr<=r)return s[root];
pushdown(root,cl,cr);
int mid=(cl+cr)>>1;
return min(query(root<<1,cl,mid,l,r),query(root<<1|1,mid+1,cr,l,r));
}
int main()
{
ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);
int Q;
cin>>Q;
while(Q--)
{
int op;
cin>>op;
if(op==1)
{
int a,b,k;
cin>>a>>b>>k;
update(1,1,n,a,b,k);
}
else
{
vector<int> res;
priority_queue<node,vector<node>,greater<node> > q;
int a,b,k,x;
cin>>a>>b>>k>>x;
seg tmp=query(1,1,n,a,b);
q.push({a,b,tmp.mina,tmp.pos});
while(!q.empty())
{
node u=q.top();
q.pop();
if((int)res.size()>=x||u.mina>=k)break;
res.push_back(u.mina);
int l=u.l,r=u.r,pos=u.pos;
if(l<pos)
{
tmp=query(1,1,n,l,pos-1);
q.push({l,pos-1,tmp.mina,tmp.pos});
}
if(pos<r)
{
tmp=query(1,1,n,pos+1,r);
q.push({pos+1,r,tmp.mina,tmp.pos});
}
}
if((int)res.size()<x)cout<<-1;
else
for(auto x:res)
cout<<x<<' ';
cout<<endl;
}
}
return 0;
}