题解：P13978 数列分块入门 3

· · 题解

前言

和数列分块入门 2 思路差不多，如果做过思路部分可以基本略过。如果没做过，那么最起码要会做数列分块入门 1，最好数列分块入门 4 也要了解一下。如果不会可以看看我的题解：第一题题解，第二题题解。
声明：此处没有想宣传本人题解，看别人更好懂的也可以。

思路

首先，区间查询和区间修改思路基本一样，这个应该可以不说吧。
然后，发现题目要我们求一个数 x 的前驱。那其实就是让我找到该区间内小于 x 的最大数。诶，和数列分块入门 2 很像诶！
那么我们也可以用一样的思路（这里再叙述一遍）：
很容易想到二分，也就是说，假定每个块内有序，如果当前是一整个块，那么可以直接二分解决前驱；反之，则一个一个枚举判断，取最大值。
那么，现在的问题就是：如何让每个块内有序。
容易发现我们不可以直接排序，因为直接排序会打乱每个数的顺序，修改的时候就会出错。所以，我们可以再开一个数组，记录的就是每个块内排好序的序列。
那么，初始化很简单了，就是每个块内的数直接排序。那么修改操作呢？
首先，如果修改了这一整个块，那么由于是整体全都加上了一个数，所以排序结果不变，只是数值整体变化了，我们还是按照数列分块入门 1 的思想，直接把这个数加进这个块的“权值”。
然后，问题就在如果修改的不是一个整块上了。那么很容易发现，每次修改最多只有两个这样的小部分，因此直接修改以后再次排序即可。
时间复杂度：O(n\sqrt n \log \sqrt n)，可以通过本题。

Code

代码细节比较多，最好自己写，可以借鉴一下，但是请不要抄袭。
如果没做过数列分块入门 2，做完这题可以去看看，思路很接近，甚至代码我都是直接拷过来改一下的。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[200005],b[200005],num[455],len,n;
void update(int now){//对每个块排序 
    for(int i = (now-1)*len+1;i<=min(now*len,n)/*一定要注意角块！*/;i++){
        b[i] = a[i];
    }
    sort(b+(now-1)*len+1,b+min(now*len,n)+1);
}
signed main() {
//  freopen("1.in","r",stdin);
//  freopen("1.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    len = sqrt(n);
    for(int i = 1; i<=n; i++) {
        cin>>a[i];
    }
    for(int i = 1; i<=len+(len*len!=n)/*后面的条件语句是判断有没有角块的，如果有，块的数量要增加一个*/; i++) {
        update(i);//初始化每个块 
    }
    for(int i = 1; i<=n; i++) {
        int op,l,r,c;
        cin>>op>>l>>r>>c;
        int nl,nr;
        nl = (l-1)/len+1;
        nr = (r-1)/len+1;
        if(!op) {//修改操作 
            if(nl == nr) {
                for(int j = l; j<=r; j++) {
                    a[j] = a[j]+c;
                }
                update(nl);//注意非完整块修改完以后要排序 
            } else {
                for(int j = l; j<=nl*len; j++) {
                    a[j] = a[j]+c;
                }
                update(nl);
                for(int j = nl+1; j<nr; j++) {
                    num[j] = num[j]+c;
                }
                for(int j = (nr-1)*len+1; j<=r; j++) {
                    a[j] = a[j]+c;
                }
                update(nr);
            }
        } else {
            int ans;
            ans = -1e18;//千万，千万不要设置成-1！因为a[i]可能为负！ 
            if(nl == nr){
                for(int j = l;j<=r;j++){
                    if(a[j]+num[nl]<c){
                        ans = max(ans,a[j]+num[nl]);//不要忘记加上这个块的权值 
                    }
                }
            }else{
                for(int j = l;j<=nl*len;j++){
                    if(a[j]+num[nl]<c){
                        ans = max(ans,a[j]+num[nl]);
                    }
                }
                for(int j = nl+1;j<nr;j++){
                    int w;
                    w = lower_bound(b+(j-1)*len+1,b+j*len+1,c-num[j])-b-1; 
                    if(w>(j-1)*len){//注意：如果这个块内没有比x（即代码中的c）更小的，一定要特殊判断。否则你取的最大值就是上一个块的最后一个数。 
                        ans = max(ans,b[w]+num[j]);
                    }
                }
                for(int j = (nr-1)*len+1;j<=r;j++){
                    if(a[j]+num[nr]<c){
                        ans = max(ans,a[j]+num[nr]);
                    }
                }
            }
            if(ans == -1e18){
                ans = -1;
            }
            cout<<ans<<"\n";
        }
    }
    return 0;
}