[loj 504]「LibreOJ β Round」ZQC 的手办

题目链接

https://loj.ac/problem/504

题解

思路同 [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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据