Loading...

Loj 数列分块入门(5/9) (To be continued...)

check评论:0 条 remove_red_eye浏览量:462 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-07-06

  • 数列分块入门1
    总体难度:3(1~10)

code:

#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;
int n,block,belong[50005],a[50005],addv[50005];
int add(int l,int r,int x)
{
    for(int i=l;i<=min(belong[l]*block,r);i++)
    {
        a[i]+=x;
    }
    if(belong[l]!=belong[r])
    {
        for(int i=(belong[r]-1)*block+1;i<=r;i++)
        {
            a[i]+=x;
        }
    }
    for(int i=belong[l]+1;i<=belong[r]-1;i++)
    {
        addv[i]+=x;
    }
}
int main()
{
    cin>>n;
    block=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]); 
    }
    for(int i=1;i<=n;i++)
    {
        belong[i]=(i-1)/block+1;
    } 
    for(int i=0;i<n;i++)
    {
        int opt,l,r,x;
        scanf("%d%d%d%d",&opt,&l,&r,&x);
        if(opt==0)
        {
            add(l,r,x);
        }
        else
        {
            printf("%d\n",a[r]+addv[belong[r]]);
        }
    }
}
  • 数列分块入门2
    总体难度:5

code:

#include <bits/stdc++.h>
using namespace std;
int n,block,cnt;
int a[50010],belong[50010],addv[500];
vector<int> vc[500];
void pre()
{
    for(int i=1;i<=cnt;i++)
    {
        sort(vc[i].begin(),vc[i].end());
    }
}
void update(int blockn)
{
    vc[blockn].clear();
    for(int i=(blockn-1)*block+1;i<=min(blockn*block,n);i++)
    {
        vc[blockn].push_back(a[i]);
    }
    sort(vc[blockn].begin(),vc[blockn].end());
}
void modify(int l,int r,int add)
{
    for(int i=l;i<=min(belong[l]*block,r);i++)
    {
        a[i]+=add;
    }
    update(belong[l]);
    if(belong[l]!=belong[r])
    {
        for(int i=(belong[r]-1)*block+1;i<=r;i++)
        {
            a[i]+=add;
        }
        update(belong[r]);
    }
    for(int i=belong[l]+1;i<belong[r];i++)
    {
        addv[i]+=add;
    }
}
int query(int l,int r,int maxn)
{
    int ans=0;
    for(int i=l;i<=min(block*belong[l],r);i++)
    {
        if(a[i]+addv[belong[i]]<maxn)
        {
            ans++;
        }
    }
    if(belong[l]!=belong[r])
    {
        for(int i=(belong[r]-1)*block+1;i<=r;i++)
        {
            if(a[i]+addv[belong[i]]<maxn)
            {
                ans++;
            }
        }
    }
    for(int i=belong[l]+1;i<belong[r];i++)
    {
        int num=maxn-addv[i];
        ans+=lower_bound(vc[i].begin(),vc[i].end(),num)-vc[i].begin();
    }
    return ans;
}
int main()
{
    cin>>n;
    block=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        belong[i]=(i-1)/block+1;
        vc[belong[i]].push_back(a[i]);
        if(i%block==1)
        {
            cnt++;
        }
    }
    pre();
    for(int i=1;i<=n;i++)
    {
        int opt,l,r,c;
        scanf("%d%d%d%d",&opt,&l,&r,&c);
        if(opt==0)
        {
            modify(l,r,c);
        }
        else
        {
            printf("%d\n",query(l,r,c*c));
        }
    }
}
  • 数列分块入门3
    总体难度:5

code:

#include <bits/stdc++.h>
using namespace std;
int n,block,cnt;
int a[100010],addv[400],belong[100010];
vector<int> vc[400];
void pre()
{
    for(int i=1;i<=cnt;i++)
    {
        sort(vc[i].begin(),vc[i].end());
    }
}
void update(int blockn)
{
    vc[blockn].clear();
    for(int i=(blockn-1)*block+1;i<=blockn*block;i++)
    {
        vc[blockn].push_back(a[i]); 
    } 
    sort(vc[blockn].begin(),vc[blockn].end());
}
void modify(int l,int r,int add)
{
    for(int i=l;i<=min(belong[l]*block,r);i++)
    {
        a[i]+=add;
    }
    update(belong[l]);
    if(belong[l]!=belong[r])
    {
        for(int i=(belong[r]-1)*block+1;i<=r;i++)
        {
            a[i]+=add; 
        }
        update(belong[r]);
    }
    for(int i=belong[l]+1;i<belong[r];i++)
    {
        addv[i]+=add;
    }
}
int query(int l,int r,int maxn)
{
    int ans=-0x3f3f3f3f;
    for(int i=l;i<=min(belong[l]*block,r);i++)
    {
        if(a[i]+addv[belong[i]]<maxn)
        {
            ans=max(ans,a[i]+addv[belong[i]]);
        }
    }
    if(belong[l]!=belong[r])
    {
        for(int i=(belong[r]-1)*block+1;i<=r;i++)
        {
            if(a[i]+addv[belong[i]]<maxn)
            {
                ans=max(ans,a[i]+addv[belong[i]]);
            }
        }
    }
    for(int i=belong[l]+1;i<belong[r];i++)
    {
        if(vc[i].at(0)+addv[i]>=maxn)
        {
            continue;
        }
        int k=lower_bound(vc[i].begin(),vc[i].end(),maxn-addv[i])-vc[i].begin();
        ans=max(ans,vc[i].at(k-1)+addv[i]);
    }
    return ans;
}
int main()
{
    int n;
    cin>>n;
    block=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        belong[i]=(i-1)/block+1;
        vc[belong[i]].push_back(a[i]);
        if(i%block==1)
        {
            cnt++;
        }
    }
    pre();
    for(int i=1;i<=n;i++)
    {
        int opt,l,r,c;
        scanf("%d%d%d%d",&opt,&l,&r,&c);
        if(opt==0)
        {
            modify(l,r,c);
        }
        else
        {
            int k=query(l,r,c);
            if(k==-0x3f3f3f3f)
            {
                printf("-1\n");
                continue;
            }
            printf("%d\n",k);
        }
    }
}
  • 数列分块入门4
    总体难度:3
#include <bits/stdc++.h>
using namespace std;
int n,block;
#define ll long long
int a[50010],belong[50010];
ll addv[300],sum[300];
void modify(int l,int r,int add)
{
    for(int i=l;i<=min(belong[l]*block,r);i++)
    {
        a[i]+=add;
        sum[belong[i]]+=add;
    }
    if(belong[l]!=belong[r])
    {
        for(int i=(belong[r]-1)*block+1;i<=r;i++)
        {
            a[i]+=add;
            sum[belong[i]]+=add;
        }
    }
    for(int i=belong[l]+1;i<belong[r];i++)
    {
        addv[i]+=add;
    }
}
ll int query(int l,int r,int mod)
{
    ll int ans=0;
    for(int i=l;i<=min(belong[l]*block,r);i++)
    {
        ans+=(a[i]+addv[belong[i]]);
        ans%=mod; 
    }
    if(belong[l]!=belong[r])
    {
        for(int i=(belong[r]-1)*block+1;i<=r;i++)
        {
            ans+=(a[i]+addv[belong[i]]);
            ans%=mod;
        }
    }
    for(int i=belong[l]+1;i<belong[r];i++)
    {
        ans+=sum[i];
        ans%=mod;
        ans+=addv[i]*block;
        ans%=mod;
    }
    return ans;
}
int main()
{
    cin>>n;
    block=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        belong[i]=(i-1)/block+1;
        sum[belong[i]]+=a[i];
    }
    for(int i=1;i<=n;i++)
    {
        ll int opt,l,r,c;
        scanf("%lld%lld%lld%lld",&opt,&l,&r,&c);
        if(opt==0)
        {
            modify(l,r,c);
        }
        else
        {
            printf("%lld\n",query(l,r,c+1));
        }
    }
}
  • 数列分块入门5
    总体难度:6
#include <bits/stdc++.h>
using namespace std;
long long int sum[500];
int a[50010],belong[50010];
int n,block;
bool flag[500]={false};
void do_sqrt_do(int blockn)
{
    if(flag[blockn])
    {
        return ;
    }
    flag[blockn]=true;
    sum[blockn]=0;
    for(int i=(blockn-1)*block+1;i<=blockn*block;i++)
    {
        a[i]=sqrt(a[i]);
        sum[blockn]+=a[i];
        if(a[i]>1)
        {
            flag[blockn]=false;
        }
    }
}
void do_sqrt(int l,int r)
{
    for(int i=l;i<=min(belong[l]*block,r);i++)
    {
        sum[belong[i]]-=a[i];
        a[i]=sqrt(a[i]);
        sum[belong[i]]+=a[i];
    }
    if(belong[l]!=belong[r])
    {
        for(int i=(belong[r]-1)*block+1;i<=r;i++)
        {
            sum[belong[i]]-=a[i];
            a[i]=sqrt(a[i]);
            sum[belong[i]]+=a[i];
        }
    }
    for(int i=belong[l]+1;i<belong[r];i++)
    {
        do_sqrt_do(i);
    }
}
int query(int l,int r)
{
    int ans=0; 
    for(int i=l;i<=min(belong[l]*block,r);i++)
    {
        ans+=a[i];
    }
    if(belong[l]!=belong[r])
    {
        for(int i=(belong[r]-1)*block+1;i<=r;i++)
        {
            ans+=a[i];
        }
    }
    for(int i=belong[l]+1;i<belong[r];i++)
    {
        ans+=sum[i];
    }
    return ans;
}
int main()
{
    cin>>n;
    block=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        belong[i]=(i-1)/block+1;
        sum[belong[i]]+=a[i];
    }
    for(int i=1;i<=n;i++)
    {
        int opt,l,r,c;
        scanf("%d%d%d%d",&opt,&l,&r,&c);
        if(opt==0)
        {
            do_sqrt(l,r);
        }
        else
        {
            printf("%d\n",query(l,r));
        }
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名