[学习笔记]数列分块入门1-3

Owen_codeisking · 2018-07-12 18:37:02 · 个人记录

数列分块入门 1

题目描述:

给出一个长为 n 的数列，以及 n个操作，操作涉及区间加法，单点查值。

输入格式:

第一行输入一个数字 n。

第二行输入 n个数字，第 i个数字为 a_{i}，以空格隔开。

接下来输入 n 行询问，每行输入四个数字 opt、l、r、c，以空格隔开。

若 opt=0，表示将位于 [l,r] 的之间的数字都加 c。

若 opt=1，表示询问 a_{r} 的值（l 和 c 忽略）。

输出格式:

对于每次询问，输出一行一个数字表示答案。

样例输入:

1 2 2 3

0 1 3 1

1 0 1 0

0 1 2 2

1 0 2 0

样例输出:

提示:

对于 100% 的数据，1≤n≤50000,-2^{31}≤others、ans≤2^{31}-1

时间限制:100ms

空间限制:256MByte

分析

其实就是数列分块入门4不带sum数组，单点询问，懒得改了

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,t;
ll a[100010],sum[1010],add[1010];
ll L[1010],R[1010],pos[100010];

void change(ll l,ll r,ll d){
    ll p=pos[l],q=pos[r];
    if(p==q){
        for(ll i=l;i<=r;i++) a[i]+=d;
        sum[p]+=d*(r-l+1);
    }
    else {
        for(ll i=p+1;i<=q-1;i++) add[i]+=d;
        for(ll i=l;i<=R[p];i++) a[i]+=d;
        sum[p]+=d*(R[p]-l+1);
        for(ll i=L[q];i<=r;i++) a[i]+=d;
        sum[q]+=d*(r-L[q]+1);
    }
}

ll ask(ll l){
    ll p=pos[l];
    return add[p]+a[l];
}

int main()
{
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    t=sqrt(n);
    for(ll i=1;i<=t;i++){
        L[i]=(i-1)*t+1,R[i]=i*t;
    }
    if(R[t]!=n) t++,L[t]=R[t-1]+1,R[t]=n;
    for(ll i=1;i<=t;i++){
        for(ll j=L[i];j<=R[i];j++){
            pos[j]=i;
        }
    }
    for(ll i=1;i<=n;i++){
        ll e,l,r,k;
        scanf("%lld%lld%lld%lld",&e,&l,&r,&k);
        if(e==0) {
            change(l,r,k);
        }
        else printf("%lld\n",ask(r));
    }
    return 0;
}

数列分块入门 2（教主的魔法）

题目描述:

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内小于某个值 x 的元素个数。

输入格式:

第一行输入一个数字 n。

第二行输入n 个数字，第 i 个数字为 a_{i}，以空格隔开。

接下来输入 n 行询问，每行输入四个数字 opt、l、r、c，以空格隔开。

若 opt=0，表示将位于 [l,r] 的之间的数字都加 c。

若 opt=1，表示询问 [l,r] 中，小于 c^2 的数字的个数。

输出格式:

对于每次询问，输出一行一个数字表示答案。

样例输入:

1 2 2 3

0 1 3 1

1 1 3 2

1 1 4 1

1 2 3 2

样例输出:

提示:

对于 100% 的数据，1≤n≤50000,-2^{31}≤others、ans≤2^{31}-1

分析

好题。

这道题看到3000ms的范围就知道肯定是一道暴力题。首先分块处理，一块\sqrt{n}，先暴力排序，在将每次的l,r:

1、在一段内就暴力枚举，用ans统计个数

2、否则不在一段内：

（1）不完整一段重复1操作，再暴力排序

（2）否则在排序完了的b数组之中进行二分查找，记录第一个大于等于x的下标，用ans加上下标减去其所在块中的L端点

时间复杂度O(nlogn+mn\sqrt{n})

时间限制:3000ms

空间限制:256MByte

#include <bits/stdc++.h>
#define ll long long
#define maxn 50010
#define maxm 310
using namespace std;
ll n,t;
ll a[maxn],add[maxm],b[maxn];
ll pos[maxn],L[maxm],R[maxm];

void change(ll l,ll r,ll d){
    ll p=pos[l],q=pos[r];
    if(p==q){
        for(int i=l;i<=r;i++) a[i]+=d;
        for(int i=L[p];i<=R[p];i++) b[i]=a[i];
        sort(b+L[p],b+R[p]+1);
    }
    else {
        for(int i=p+1;i<=q-1;i++) add[i]+=d;
        for(int i=l;i<=R[p];i++) a[i]+=d;
        for(int i=L[p];i<=R[p];i++) b[i]=a[i];
        sort(b+L[p],b+R[p]+1);
        for(int i=L[q];i<=r;i++) a[i]+=d;
        for(int i=L[q];i<=R[q];i++) b[i]=a[i];
        sort(b+L[q],b+R[q]+1);
    }
}

ll query(ll l,ll r,ll d){
    ll x=lower_bound(b+l,b+r+1,d)-b;
    //printf("%lld %lld %lld %lld\n",l,r,d,x-l);
    return x-l;
}

ll ask(ll l,ll r,ll d){
    ll p=pos[l],q=pos[r],ans=0;
    if(p==q){
        for(int i=l;i<=r;i++)
            if(d-add[p]>a[i])
                ans++;
    }
    else {
        for(int i=p+1;i<=q-1;i++)
            ans+=query(L[i],R[i],d-add[i]);
        for(int i=l;i<=R[p];i++)
            if(d-add[p]>a[i])
                ans++;
        for(int i=L[q];i<=r;i++)
            if(d-add[q]>a[i])
                ans++;
    }
    return ans;
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    t=sqrt(n);
    for(int i=1;i<=t;i++)
        L[i]=(i-1)*t+1,R[i]=i*t;
    if(R[t]!=n) t++,L[t]=R[t-1]+1,R[t]=n;
    for(int i=1;i<=t;i++){
        for(int j=L[i];j<=R[i];j++){
            pos[j]=i;b[j]=a[j];
        }
        sort(b+L[i],b+R[i]+1);
    }
    /*for(int i=1;i<=n;i++)
        printf("%d ",pos[i]);
    printf("\n");*/
    for(int i=1;i<=n;i++){
        ll k,l,r,c;
        scanf("%lld%lld%lld%lld",&k,&l,&r,&c);
        if(k==0){
            change(l,r,c);
        }
        else {
            printf("%lld\n",ask(l,r,c*c));
        }
        /*for(int i=1;i<=n;i++)
            printf("%d ",a[i]);
        printf("\n");
        for(int i=1;i<=n;i++)
            printf("%d ",b[i]);
        printf("\n");
        for(int i=1;i<=t;i++)
            printf("%d ",add[i]);
        printf("\n");*/
    }
    return 0;
}

数列分块入门 3

题目描述:

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内小于某个值 x 的前驱（比其小的最大元素）。

输入格式:

第一行输入一个数字 n。

第二行输入 n 个数字，第 i 个数字为 a_{i}，以空格隔开。

接下来输入 n 行询问，每行输入四个数字 opt、l、r、c，以空格隔开。

若 opt=0，表示将位于 [l,r] 的之间的数字都加 c。

若 opt=1，表示询问 [l,r] 中 c 的前驱的值（不存在则输出 -1）。

输出格式:

对于每次询问，输出一行一个数字表示答案。

样例输入:

1 2 2 3

0 1 3 1

1 1 4 4

0 1 2 2

1 1 2 4

样例输出:

-1

提示:

对于 100% 的数据，1≤n≤50000,−2^{31}≤others、ans≤2^{31}−1。

分析

跟上题差不多，但时间小了一半，1328ms水过。跟上题差不多，就是把ans改成max函数比较

时间限制:1500ms

空间限制:256MByte

#include <bits/stdc++.h>
#define ll int
#define maxn 100010
#define maxm 1010
using namespace std;
ll n,t;
ll a[maxn],add[maxm],b[maxn];
ll pos[maxn],L[maxm],R[maxm];

void change(ll l,ll r,ll d){
    ll p=pos[l],q=pos[r];
    if(p==q){
        for(ll i=l;i<=r;i++) a[i]+=d;
        for(ll i=L[p];i<=R[p];i++) b[i]=a[i];
        sort(b+L[p],b+R[p]+1);
    }
    else {
        for(ll i=p+1;i<=q-1;i++) add[i]+=d;
        for(ll i=l;i<=R[p];i++) a[i]+=d;
        for(ll i=L[p];i<=R[p];i++) b[i]=a[i];
        sort(b+L[p],b+R[p]+1);
        for(ll i=L[q];i<=r;i++) a[i]+=d;
        for(ll i=L[q];i<=R[q];i++) b[i]=a[i];
        sort(b+L[q],b+R[q]+1);
    }
}

ll query(ll l,ll r,ll d){
    ll x=lower_bound(b+l,b+r+1,d)-b;
    //printf("%lld %lld %lld %lld\n",l,r,d,x-l);
    return x-1;
}

ll ask(ll l,ll r,ll d){
    ll p=pos[l],q=pos[r],ans=-999999;
    if(p==q){
        for(ll i=l;i<=r;i++)
            if(d>a[i]+add[p])
                ans=max(ans,a[i]+add[p]);
    }
    else {
        for(ll i=p+1;i<=q-1;i++){
            ll v=query(L[i],R[i],d-add[i]);
            if(d>b[v]+add[i])
                ans=max(ans,b[v]+add[i]);
        }
        for(ll i=l;i<=R[p];i++)
            if(d>a[i]+add[p])
                ans=max(ans,a[i]+add[p]);
        for(ll i=L[q];i<=r;i++)
            if(d>a[i]+add[q])
                ans=max(ans,a[i]+add[q]);
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(ll i=1;i<=n;i++)
        scanf("%d",&a[i]);
    t=sqrt(n);
    for(ll i=1;i<=t;i++)
        L[i]=(i-1)*t+1,R[i]=i*t;
    if(R[t]!=n) t++,L[t]=R[t-1]+1,R[t]=n;
    for(ll i=1;i<=t;i++){
        for(ll j=L[i];j<=R[i];j++){
            pos[j]=i;b[j]=a[j];
        }
        sort(b+L[i],b+R[i]+1);
    }
    /*for(int i=1;i<=n;i++)
        printf("%d ",pos[i]);
    printf("\n");*/
    for(ll i=1;i<=n;i++){
        ll k,l,r,c;
        scanf("%d%d%d%d",&k,&l,&r,&c);
        if(k==0){
            change(l,r,c);
        }
        else {
            ll ans=ask(l,r,c);
            if(ans!=-999999)
                printf("%d\n",ans);
            else printf("-1\n");
        }
        /*for(int i=1;i<=n;i++)
            printf("%d ",a[i]);
        printf("\n");
        for(int i=1;i<=n;i++)
            printf("%d ",b[i]);
        printf("\n");
        for(int i=1;i<=t;i++)
            printf("%d ",add[i]);
        printf("\n");*/
    }
    return 0;
}