P6138

syta · 2024-02-26 20:05:12 · 题解

传送门

首先，如果一个区间打完，那一定留下最大值，其余值留着也不会产生影响。

故需要算出“ 假设现在没有迟到的骑士，每次的询问对应在初始序列的 [l,r] 是什么 ”。这里可以使用线段树或树状数组上二分，具体来说，找到前缀有 l 个 1 的位置。

那么再考虑现在加入迟到的骑士 x，不难发现，对于区间 [l,r]，如果原序列的 [l,r-1] 中没有大于 x 的数，那么 x 就可以放在 [l,r] 中数的前面。

原因很简单，放进 x 必然挤掉最后一个数，所以和最后一个数是没有关系的。

一开始我想到，如果当前序列的最后一个数不在最后一个位置上，不也可以在这次被挤掉吗。

但实际上这是不对的，因为如果该数不在最后一个位置，且是最大的数，那么在该时刻之前一定进行了一次比赛，如果我们将迟到的骑士放在了这个数的前面，就一定会导致上次的比赛区间向前移了一个，这时候我们发现被挤掉的数字仍是原序列下标上的最后一个，而大的数还包含在当前区间。

对答案的贡献用前缀和统计即可。

时间复杂度 O(n\log n)。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,k;
int a[N];
struct tree{
    int l,r,sum;
}t[N*4];
void build(int p,int l,int r){
    t[p].l=l,t[p].r=r;
    t[p].sum=r-l+1;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(p<<1,l,mid),build(p<<1|1,mid+1,r);
}
void add(int p,int x){
    if(t[p].l==t[p].r){
        t[p].sum--;
        return;
    }
    int mid=(t[p].l+t[p].r)>>1;
    if(x<=mid) add(p<<1,x);
    else add(p<<1|1,x);
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
int find(int p,int x){
    if(t[p].l==t[p].r) return t[p].l;
    if(t[p<<1].sum>=x) return find(p<<1,x);
    else return find(p<<1|1,x-t[p<<1].sum);
}
int ans[N];
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<n;i++) scanf("%d",&a[i]),a[i]=a[i-1]+(a[i]>k);
    build(1,1,n);
    while(m--){
        int l,r;
        scanf("%d%d",&l,&r),l++,r++;
        int L=find(1,l),R=find(1,r+1)-1,len=r-l;
        while(len--) add(1,find(1,l+1));
        if(a[R-1]==a[L-1]) ans[L]++,ans[R+1]--;
    }
    int pos=1;
    for(int i=1;i<=n;i++){
        ans[i]+=ans[i-1];
        if(ans[i]>ans[pos]) pos=i;
    }
    printf("%d",pos-1);
    return 0;
}