LOJ #6279 数列分块入门3

Dear 丶 2022-05-19 10:35 133阅读 0赞

[题目链接][Link 1]

题意：给出一个长度为 n 的数列，以及 n 个操作，操作涉及区间加法，求区间内小于某个值 x 的前驱（比x小的最大元素)

1≤n≤100000

分析：考虑直接用分块莽一波，设每个块的大小为√n，对于查询操作，不完整的块因为它的大小不超过√n，对于更新操作，对于两头不完整的块，直接暴力更新，用一个sum数组来维护完整区间内的加法标记，为了在完整的区间时能够快速访问到前驱，需要使得区间内的元素是有序的，我们可以直接用set来维护，set默认是从小到大排序的，每次更新的时候直接erase原来的值，然后加入增加以后的那个值，然后对于每次查询，不在完整区间内的，直接暴力查询，在完整区间内的块就通过二分来实现快速查询。

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5+7;
    int belong[maxn],l[maxn],r[maxn];
    int n,num,block;
    int a[maxn],sum[maxn];
    set<int>s[2005];
    
    long long read()
    {
    	char ch=getchar();long long ret=0,f=1;
    	while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
    	return f*ret;
    }
    
    void build()
    {
        block=sqrt(n);
        num=n/block;if(n%block) num++;
        for(int i=1;i<=num;i++)
            l[i]=(i-1)*block+1,r[i]=i*block;
        r[num]=n;
        for(int i=1;i<=n;i++)
        {
             belong[i]=(i-1)/block+1;
             s[belong[i]].insert(a[i]);
        }
    }
    
    void update(int x,int y,int c)
    {
        if(belong[x]==belong[y])
        {
            for(int i=x;i<=y;i++)
            {
                s[belong[x]].erase(a[i]);
                a[i]+=c;
                s[belong[x]].insert(a[i]);
            }
            return;
        }
        for(int i=x;i<=r[belong[x]];i++)
        {
            s[belong[x]].erase(a[i]);
            a[i]+=c;
            s[belong[x]].insert(a[i]);
        }
        for(int i=belong[x]+1;i<belong[y];i++)
            sum[i]+=c;
        for(int i=l[belong[y]];i<=y;i++)
        {
            s[belong[y]].erase(a[i]);
            a[i]+=c;
            s[belong[y]].insert(a[i]);
        }
    }
    
    int query(int x,int y,int c)
    {
        int ans = -1;
        if(belong[x]==belong[y])
        {
            for(int i=x;i<=y;i++)
            {
                if(a[i]+sum[belong[x]]<c) ans=max(ans,a[i]+sum[belong[x]]);
            }
            return ans;
        }
        for(int i=x;i<=r[belong[x]];i++)
            if(a[i]+sum[belong[x]]<c) ans=max(ans,a[i]+sum[belong[x]]);
        for(int i=belong[x]+1;i<belong[y];i++)
        {
            int x=c-sum[i];
            set<int>::iterator it=s[i].lower_bound(x);
            if(it==s[i].begin()) continue;
            it--;
            ans=max(ans,*it+sum[i]);
        }
        for(int i=l[belong[y]];i<=y;i++)
            if(a[i]+sum[belong[y]]<c) ans=max(ans,a[i]+sum[belong[y]]);
        return ans;
    }
    
    int main()
    {
        n=read();
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        build();
        for(int i=1;i<=n;i++)
        {
            int op=read(),l=read(),r=read(),c=read();
            if(op==1) printf("%d\n",query(l,r,c));
            else update(l,r,c);
        }
        return 0;
    }

[Link 1]: https://loj.ac/problem/6279