【LibreOJ 6279】数列分块入门 3 （分块）

传送门

code：

//By Menteur_Hxy

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<set>

using namespace std;

int rd() {

    int x=0,fla=1; char c=' ';

    while(c>'9'|| c<'0') {if(c=='-') fla=-fla; c=getchar();}

    while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar();

    return x*fla;

}

const int MAX=100005;

const int INF=0x3f3f3f3f;

int n,blo;

int v[MAX],bl[MAX],tag[MAX];

set <int> st[205];

void add(int a,int b,int c) {

    for(int i=a;i<=min(bl[a]*blo,b);i++) {

        st[bl[a]].erase(v[i]);

        v[i]+=c;

        st[bl[a]].insert(v[i]);

    }

    if(bl[a]!=bl[b]) {

        for(int i=(bl[b]-1)*blo+1;i<=b;i++) {

            st[bl[b]].erase(v[i]);

            v[i]+=c;

            st[bl[b]].insert(v[i]);

        }

    }

    for(int i=bl[a]+1;i<=bl[b]-1;i++)

        tag[i]+=c;

}

int query(int a,int b,int c) {

    int ans=-1;

    for(int i=a;i<=min(bl[a]*blo,b);i++)

        if(v[i]+tag[bl[a]]<c) ans=max(ans,v[i]+tag[bl[a]]);

    if(bl[a]!=bl[b])

        for(int i=(bl[b]-1)*blo+1;i<=b;i++)

            if(v[i]+tag[bl[b]]<c) ans=max(ans,v[i]+tag[bl[b]]);

    for(int i=bl[a]+1;i<=bl[b]-1;i++) {

        int x=c-tag[i];

        set<int>::iterator it=st[i].lower_bound(x);

        if(it==st[i].begin()) continue;

        --it;

        ans=max(ans,*it+tag[i]);

    }

    return ans;

}

int main() {

    n=rd(); blo=1000;//1000玄学

//  cout<<n<<endl;

    for(int i=1;i<=n;i++) v[i]=rd();

    for(int i=1;i<=n;i++) {

        bl[i]=(i-1)/blo+1;

        st[bl[i]].insert(v[i]);

    }

    for(int i=1;i<=n;i++) {

        int opt=rd(),l=rd(),r=rd(),c=rd();

        if(opt) printf("%d\n",query(l,r,c));

        else add(l,r,c);

    }

    return 0;

}

巴特西

【LibreOJ 6279】数列分块入门 3 （分块）

传送门

最新文章

热门文章

巴特西

【LibreOJ 6279】 数列分块入门 3 （分块）

传送门

最新文章

热门文章

【LibreOJ 6279】数列分块入门 3 （分块）