题解：P11286 [COTS 2017] 盗道 Krimošten

· · 题解

提供一个比较直接，但是复杂度劣一点的在线做法：线段树维护分段函数。

一个比较显然的事情是：对于同一个区间 [l,r]，最终手上的钱数随着初始时的钱数的增加而单调不降。考虑设 f_{l,r}(x) 表示初始以 x 的钱数进行操作，最后钱数的变化量，不难发现这个函数形如若干段水平直线，整个函数是一个分段函数。

我们考虑暴力地在线段树上维护这些分段函数，合并两个函数时，由于上文中提到的单调性，左儿子的每一段在右儿子的对应段也是单调的。因此可以直接求出左儿子每一段对应的末状态钱数，双指针维护其对应的右儿子的段。对于一个长度为 len 的区间，其段数为 O(len) 的，合并时用双指针可以做到线性。因此 build 部分的复杂度是 O(n\log n) 的。

接下来考虑区间查询。我们依次遍历每一个线段树上的区间，维护当前钱数 v，每次二分找到 v 对应的那一段即可求出这个区间结束后的新的钱数，单次查询的复杂度是 O(\log^2 n)。

因此总复杂度是 O(n\log^2 n)，在 4s 的限制下不难通过。代码非常好写。

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define lowbit(i) (i&-i)
#define int long long
#define qingbai 666
using namespace std;
typedef long long ll;
const int N=5e5+5,M=32,inf=1e9+7,mo=1e9+7;
void read(int &p){
    int w=1,x=0;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    p=w*x;
}
int n,m,a[N];
struct seg{
    vector<pii>t[4*N];
    void pushup(int x){
        int targ=0;
        rep(i,0,(int)t[ls(x)].size()-1){
            int le=t[ls(x)][i].fir,ri=(i==(int)t[ls(x)].size()-1?inf:t[ls(x)][i+1].fir-1);
            int del=t[ls(x)][i].sec;
            int vl=le+del,vr=ri+del;
            while(targ<(int)t[rs(x)].size()-1&&t[rs(x)][targ+1].fir<=vr){
                t[x].push_back(mp(le,del+t[rs(x)][targ].sec)),le=t[rs(x)][targ+1].fir-del;
                targ++;
            }
            t[x].push_back(mp(le,del+t[rs(x)][targ].sec));
        }
    }
    void build(int x,int le,int ri){
        if(le==ri){
            if(a[le]>0)t[x].push_back(mp(0,1));
            t[x].push_back(mp(a[le],0));
            t[x].push_back(mp(a[le]+1,-1));
            return;
        }
        int mid=(le+ri)>>1;
        build(ls(x),le,mid),build(rs(x),mid+1,ri);
        pushup(x);
    }
    int query(int x,int le,int ri,int ql,int qr,int v){
        if(ql<=le&&qr>=ri){
            int targ=upper_bound(t[x].begin(),t[x].end(),mp(v,inf))-t[x].begin()-1;
            return v+t[x][targ].sec;
        }
        int mid=(le+ri)>>1,res=v;
        if(ql<=mid)res=query(ls(x),le,mid,ql,qr,v);
        if(qr>mid)res=query(rs(x),mid+1,ri,ql,qr,res);
        return res;
    }
}T;
signed main(){
    read(n),read(m);
    rep(i,1,n)
        read(a[i]);
    T.build(1,1,n);
    while(m--){
        int x,y,v;
        read(x),read(y),read(v);
        printf("%lld\n",T.query(1,1,n,x,y,v));
    }
    return 0;
}