P11286 [COTS 2017] 盗道 Krimošten 题解
xixisuper
2024-11-18 14:40:47
P11286 [COTS 2017] 盗道 Krimošten 题解
小清新数据结构题，感觉没有紫。
思路
先来想弱化版的情况：假设我每次询问的 $[l,r]$ 都是 $[1,n]$，但是 $c$ 不一样，怎么做？
一个比较显然的思路是我直接维护一个值域，位置 $j$ 上的数表示初始时盗贼有 $j$ 库纳，在当前情况下有多少库纳，初始化的时候位置 $j$ 上的数就等于 $j$。对于每一户人家 $i$，**找到当前情况下值小于 $a_i$ 的那些盗贼，给他们全部加 $1$**；**找到当前情况下值大于 $a_i$ 的那些盗贼，给他们全部减 $1$**。最后，第 $j$ 个位置上的数就是对应的解。
不难发现上述算法的时间复杂度瓶颈在于如何进行快速的加减 $1$ 操作。我们能够发现，**盗贼当前的库那个数随初始库那个数单调不降**。证明这个也很简单，你会发现对于 $x<y$ 来说，在经过若干次操作后只可能会达到 $x=y$ 的一个状态，往后的所有人家都会使 $x,y$ 同加同减，所以 $x$ 永远小于等于 $y$，单调性得证。
所以我们**在值域上加的盗贼一定是一段前缀，减的盗贼一定是一段后缀**，找 $a_i$ 的位置可以用线段树上二分解决，而加减 $1$ 的操作线段树也支持，所以能够做到 $O(n\log V)$ 解决该问题。
现在来想一般情况，不难发现我们只需要把上述问题进行一个拓展就行。我们考虑**把所有询问离线，套用扫描线的思路，在遍历到第 $i$ 户人家前，把所有左端点 $L=i$ 的那些询问记录下 $c$ 在值域中出现的位置；在计算完第 $i$ 户人家的贡献后，把所有 $R=i$ 的询问的答案记录下来，最后输出即可。**
注意在这种实现下，最开始时值域的范围是 $[-n,V+n]$，因为我们要保证在扫描线时，$[0,V]$ 以内的所有数都出现在值域里，而操作 $n$ 户人家至多使最小值增加 $n$，使最大值减小 $n$。
归到时间复杂度分析，瓶颈在于线段树扫描线，时间复杂度为 $O((n+m)\log (n+V))$。
## 代码
毫无聪明的实现，看看就好。
```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define ll int
#define lc (x<<1)
#define rc ((x<<1)|1)
#define mid ((l+r)>>1)
using namespace std;
const ll V=1e6+10;
const ll N=5e5+10;
const ll MX=2*V-5;
ll tag[MX<<3],mx[MX<<3],a[N],chk[MX],n,m;
struct node{
ll L,R,c,ans,id,pos;
friend bool operator >(const node x,const node y){
return x.R>y.R;
}
}ask[N],ot[N];
priority_queue<node,vector<node>,greater<node> > qu;
bool cmp1(node x,node y){return x.L<y.L;}
bool cmp2(node x,node y){return x.id<y.id;}
void push_up(ll x){mx[x]=max(mx[lc],mx[rc]);}
void build(ll x,ll l,ll r){
if(l==r){
mx[x]=chk[l];
return;
}
build(lc,l,mid);
build(rc,mid+1,r);
push_up(x);
}
void push_down(ll x){
if(!tag[x]) return;
tag[lc]+=tag[x],tag[rc]+=tag[x];
mx[lc]+=tag[x],mx[rc]+=tag[x];
tag[x]=0;
}
void add(ll x,ll l,ll r,ll L,ll R,ll p){
if(L<=l&&r<=R){
tag[x]+=p;
mx[x]+=p;
return;
}
push_down(x);
if(L<=mid) add(lc,l,mid,L,R,p);
if(R>mid) add(rc,mid+1,r,L,R,p);
push_up(x);
}
ll gtpos(ll x,ll l,ll r,ll k){
if(l==r) return l;
push_down(x);
if(mx[lc]>=k) return gtpos(lc,l,mid,k);
return gtpos(rc,mid+1,r,k);
}
ll gtval(ll x,ll l,ll r,ll pos){
if(l==r) return mx[x];
push_down(x);
if(pos<=mid) return gtval(lc,l,mid,pos);
return gtval(rc,mid+1,r,pos);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(ll i=1;i<=n;i++) cin>>a[i];
for(ll i=1;i<=m;i++){
cin>>ask[i].L>>ask[i].R>>ask[i].c;
ask[i].id=i;
}
sort(ask+1,ask+1+m,cmp1);
for(ll i=1;i<=MX;i++) chk[i]=i-N;
build(1,1,MX);
ll top=1,as=1;
for(ll i=1;i<=n;i++){
while(top<=m&&ask[top].L==i){
ask[top].pos=gtpos(1,1,MX,ask[top].c);
qu.push(ask[top]);
top++;
}
ll pls=gtpos(1,1,MX,a[i])-1,minu=gtpos(1,1,MX,a[i]+1);
add(1,1,MX,1,pls,1),add(1,1,MX,minu,MX,-1);
while(!qu.empty()&&qu.top().R==i){
ot[as]=qu.top();
qu.pop();
ot[as].ans=gtval(1,1,MX,ot[as].pos);
as++;
}
}
sort(ot+1,ot+1+m,cmp2);
for(ll i=1;i<=m;i++) cout<<ot[i].ans<<"\n";
return 0;
}
```