题解：P14400 [JOISC 2016] 回转寿司 / Sushi

· · 题解

在操作是全局的前提下，考虑如下两个问题：

  1. 最后回收的寿司有什么性质。
  2. 如果有一些 Q 个操作，如何在 O(N+Q) 的复杂度内，求出操作后的全局序列。

对于问题 1，显然通过模拟可以发现，最后回收的寿司是序列的最大值和新放的寿司的价格的较大者。

对于问题 2，我们发现，若 a<b 且当前位置的价格为 x，则最后保留的价格为 \min\{a,b,x\}，而向后传递的价格为另外两个。

回到原问题，先断环为链，则操作变成了区间修改。数据范围和时限提示我们可以使用根号复杂度的算法，遂考虑分块。

以 B 为块长分块，每块维护一个大根堆，一个小根堆。大根堆用于维护当前块内寿司的价格，小根堆用于维护所有作用于整块的修改。散块重构时，直接从左往右扫一遍，如果当前位置的价格 > 堆顶价格，则将当前位置的价格修改为堆顶价格，并且将当前位置的价格压进堆里。

时间复杂度 O(qB\log n+\frac{nq\log n}{B})，取 B=O(\sqrt{n})，即可做到 O(q\sqrt{n}\log n)。

#include<iostream>
#include<algorithm>
#include<queue>
const int sz=4e5+10;
int a[sz],belong[sz],bl[sz],br[sz];
std::priority_queue<int>qq[sz];
std::priority_queue<int,std::vector<int>,std::greater<int>>tag[sz];
inline void build(int id){
  std::priority_queue<int>(a+bl[id],a+br[id]+1).swap(qq[id]);
}
inline void rebuild(int id){
  if(tag[id].empty())return;
  for(int i=bl[id];i<=br[id];i++){
    if(tag[id].top()>=a[i])continue;
    tag[id].push(a[i]),a[i]=tag[id].top(),tag[id].pop();
  }
  while(!tag[id].empty())tag[id].pop();
}
inline int modify(int l,int r,int v){
  if(belong[l]==belong[r]){
    rebuild(belong[l]);
    for(int i=l;i<=r;i++)
      if(a[i]>v)std::swap(a[i],v);
    build(belong[l]);
    return v;
  }
  rebuild(belong[l]),rebuild(belong[r]);
  for(int i=l;i<=br[belong[l]];i++)if(a[i]>v)std::swap(a[i],v);
  for(int i=belong[l]+1;i<belong[r];i++){
    if(qq[i].top()<=v)continue;
    tag[i].push(v),qq[i].push(v),v=qq[i].top(),qq[i].pop();
  }
  for(int i=bl[belong[r]];i<=r;i++)if(a[i]>v)std::swap(a[i],v);
  build(belong[l]),build(belong[r]);
  return v;
}
int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n,q;
  std::cin>>n>>q;
  for(int i=1;i<=n;i++)std::cin>>a[i];
  int lim=__builtin_sqrt(n),tot=n/lim;
  for(int i=1;i<=tot;i++)bl[i]=br[i-1]+1,br[i]=i*lim;
  if(br[tot]!=n)++tot,bl[tot]=br[tot-1]+1,br[tot]=n;
  for(int i=1;i<=tot;i++){
    build(i);
    for(int j=bl[i];j<=br[i];j++)belong[j]=i;
  }
  while(q--){
    int l,r,v;
    std::cin>>l>>r>>v;
    if(l<=r)std::cout<<modify(l,r,v)<<"\n";
    else std::cout<<modify(1,r,modify(l,n,v))<<"\n";
  }
  return 0;
}