JOISC2016 回转寿司

Problem

Link

Solution

看起来不是那么好维护,那么…分块!

首先对于一段区间和一个权为p的寿司🍣来说经过这个区间以后的答案就是max(p,a[l~r]),然后对于每个位置去更新。我们可以用一个大根堆去维护每一块,经过一块的时候比较一下堆顶和p的大小,如果p更大,那么p不会留在这个块中,否则p就会留在这个块中。

难处理的是边角部分。可以打一个tag标记表示这个块中加入了那些寿司,然后对于边角块询问的时候根据tag去重建堆。

然后我就打了一个暴力重建还以为自己复杂度是对的。其实不然,对于每个块都可能有q个标记,每个块下传一次,那么复杂度为O(qn)。

注意到我们的问题有着比较好的对称性:如果我们把寿司看成顾客,顾客看成寿司,那么我们的修改操作是类似的,同样可以用堆来维护。

那么我们不妨把块内的数看成标记,把标记看成块内的数,然后用一个堆维护所有的标记,枚举块内的每一个数并用堆求出这个数会变成哪个标记。

用一个小根堆去维护标记,顺次考虑每个人的时候看看这个标记是否会影响这个人就好了。

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
#include <bits/stdc++.h>
using namespace std;
#define IL inline
IL int read() { int x; int _w = scanf("%d", &x); return x; }
#define rep(i, j, k) for (int i = j; i <= k; ++i)
#define repd(i, j, k) for (int i = j; i >= k; --i)
#define pb push_back
#define mp make_pair
#define fr first
#define se second
#define ls (p<<1)
#define rs (p<<1|1)
#define fre(x) freopen(x".in","r",stdin),freopen(x".out", "w", stdout)
const int maxn = 400000 + 10;
int a[maxn], c[maxn], n, q, bel[maxn], ed[maxn], fr[maxn], tct;
const int bsz = 300;
priority_queue<int>mx[5000];
vector<int>tag[5000];
IL void rebuild(int bid){
if(!tag[bid].size())return;
priority_queue<int, vector<int>, greater<int> >hp(tag[bid].begin(), tag[bid].end());
rep(j,fr[bid],ed[bid]){
int cur=hp.top();
if(cur<a[j])hp.pop(),hp.push(a[j]),swap(cur,a[j]);
}
tag[bid].clear();
}
IL void roll(int bid){
mx[bid]=priority_queue<int>(a+fr[bid],a+ed[bid]+1);
}
int sol(int s,int t,int p){
int ans=p;
if(bel[s]==bel[t]){
rebuild(bel[s]);
rep(i,s,t)if(ans<a[i])swap(ans,a[i]);
roll(bel[s]);
return ans;
} else {
rebuild(bel[s]);
rep(i,s,ed[bel[s]]) if(ans<a[i])swap(ans, a[i]);
roll(bel[s]);
rep(i,bel[s]+1,bel[t]-1) {
int tmx=mx[i].top();if(ans>tmx) continue;
tag[i].push_back(ans);
mx[i].pop();
mx[i].push(ans);
ans=tmx;
}
rebuild(bel[t]);
rep(i,fr[bel[t]],t) if(ans<a[i]) swap(ans, a[i]);
roll(bel[t]);
return ans;
}
}
int main() {
// freopen("03-24.in","r",stdin);
// freopen("my.out", "w", stdout);
fre("sushi");
n=read(),q=read();
rep(i,1,n)a[i]=read(),bel[i]=(i-1)/bsz+1,ed[bel[i]]=i,fr[bel[i]]=(fr[bel[i]]?fr[bel[i]]:i);
rep(i,1,n)mx[bel[i]].push(a[i]);
rep(task,1,q){
// if(task%1000==0)cerr<<task<<endl;
int s,t,p,tp,debug;
s=read(),t=read(),p=read();
tp=(s<=t)?sol(s,t,p):sol(1,t,debug=sol(s,n,p));
printf("%d\n",tp);
}
return 0;
}