回转寿司

Description

​

---

Solution

• 12%

　　暴力

　　

• 40%

　　在暴力的基础上，我们特殊处理一下$，s=1，t=n$的情况，因为每次都是从这个区间过，所以我们只需要维护一下这个区间的最大值，每次跟寿司比较，如果寿司更小就直接交换就好了（其他的值并不需要维护，因为每次都是这个区间所以顺序并不重要）

　　具体实现的话优先队列就好了
　　

• 100%

　　从上面的子任务我们得到启发，考虑分块，假设块的大小为$B$，对于每一个块我们都维护一个大根堆（啊但实现的时候不想写用优先队列也没什么问题），堆中的元素为块内的所有元素

　　如果说有一个寿司的移动完全跨过了一个块，那么我们就把堆顶的元素跟这个寿司比较一下，如果寿司更小就交换，那么一次操作是$logn$的，对于跨过不是完整块的部分，我们暴力比较更新

　　但是有个问题，子任务中是永远都只会跨过一个区间，也就是说不存在块内的修改，所以不需要维护具体某个位置是什么值，只要看整个块有哪些值就好了，但是我们现在需要处理块内的修改，所以要想办法将位置这个信息还原出来

　　我们考虑整块修改的时候，给每个块打上标记

　　考虑这样一个过程，对于一个块，每次的整块修改我们都将用来更新的值存到一个$tag$数组里面，然后最后再一次性下传，更新每个位置的值

　　考虑一下更换寿司的规则，会发现每个寿司是一遇到比自己大的就交换，手动模拟一下，会发现其实就是从左到右更新块中每个位置的值，每次从$tag$数组中找到最小的那个，比较一下，如果可以更新就交换（把原来$tag$中的最小值删掉，把这个位置原来的值丢进$tag$数组），然后再比较下一个

　　由于每次需要用的是最小值，所以我们可以考虑用对于每一个块用一个小根堆来维护所有的$tag$，每次需要块内修改的时候，先将$tag$下传，然后再进行块内的修改操作

　　这样，一次标记下传的复杂度就是$B\ log\ q$了（$B$是块大小，$q$是新寿司的数量）

　　总的时间复杂度为$O(q(B\ log\ q+\ \frac{n}{B}log\ n))$，假定$，n，q$同阶，并且将$B$设为$\sqrt n$，那么总的时间复杂度为$O(q\ \sqrt n\ log\ n)$

​　　

　　（然后我们算一下发现这很爆炸的样子。。。但是。。抱歉它就是能过qwq。。）

　　分块真的可以为所欲为

　　题外话：然而好像块大小开根号并不是最快的。。。具体开多少跑的比较快就没有大力调参了qwq

　　

　　代码大概长这个样子

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#define Pq priority_queue<int>
using namespace std;
const int MAXN=4*(1e5)+10;
Pq people[MAXN],tmpPq;
vector<int> tag[MAXN];
int a[MAXN];
int n,m,sq,all;
int Id(int x){return (x-1)/sq+1;}
int St(int x){return (x-1)*sq+1;}
int Ed(int x){return min(n,St(x)+sq-1);}
int solve(int l,int r,int w);
void update(int x);
void solve_small(int l,int r,int &w);
void solve_big(int x,int &w);
 
int main(){
#ifndef ONLINE_JUDGE
    freopen("a.in","r",stdin);
#endif
    int l,r,w;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i) scanf("%d",a+i);
    sq=sqrt(n); all=(n-1)/sq;
    for (int i=1;i<=Id(n);++i) tag[i].clear();
    for (int i=1;i<=n;++i)
        people[Id(i)].push(a[i]);
    for (int i=1;i<=m;++i){
        scanf("%d%d%d",&l,&r,&w);
        if (l<=r)
            printf("%d\n",solve(l,r,w));
        else
            printf("%d\n",solve(1,r,solve(l,n,w)));
    }
}
 
int solve(int l,int r,int w){
    int numl,numr;
    if (Id(l)==Id(r))
        solve_small(l,r,w);
    else{
        numl=Id(l); numr=Id(r);
        if (l!=St(numl))
            solve_small(l,Ed(numl),w);
        else
            solve_big(numl,w);
        for (int i=numl+1;i<numr;++i)
            solve_big(i,w);
        if (r!=Ed(numr))
            solve_small(St(numr),r,w);
        else
            solve_big(numr,w);
    }
    return w;
}
 
void update(int x){
    if (tag[x].empty()) return;
    priority_queue<int,vector<int>,greater<int> > tmpPq(tag[x].begin(),tag[x].end());
    for (int i=St(x);i<=Ed(x);++i){
        if (a[i]>tmpPq.top()){
            tmpPq.push(a[i]);
            a[i]=tmpPq.top();
            tmpPq.pop();
        }
    }
    people[x]=Pq(a+St(x)+1,a+Ed(x)+1);//priority_queue可以这么赋值的嗯qwq
    tag[x].clear();
}
 
void solve_small(int l,int r,int &w){
    int x=Id(l);
    update(x);
    for (int i=l;i<=r;++i)
        if (w<a[i])
            swap(a[i],w);
    people[x]=Pq(a+St(x),a+Ed(x)+1);
}
 
void solve_big(int x,int &w){
    if (w>=people[x].top()) return;
    tag[x].push_back(w);
    people[x].push(w);
    w=people[x].top();
    people[x].pop();
}