数列分块入门

LOJ#6281. 数列分块入门 5,

内部存款和储蓄器限制:256 MiB时限:500 ms标准输入输出 标题类型:古板评测方式:文本相比 上传者: hzwer 提交提交记录计算研讨 1 测验数据  

LOJ#6279. 数列分块入门 3,

内部存款和储蓄器限制:256 MiB时限:1500 ms标准输入输出 题目类型:守旧评测格局:文本相比较 上传者: hzwer 提交提交记录总计商量 1 测量试验数据  

LOJ#6280. 数列分块入门 4,

内部存款和储蓄器限制:256 MiB时限:500 ms规范输入输出 标题类型:守旧评测格局:文本相比较 上传者: hzwer 提交提交记录计算研究测量检验数据  

LOJ#数列分块入门。6277. 数列分块入门 1,

内部存款和储蓄器限制:256 MiB时间范围:100 ms规范输入输出 标题类型:古板评测方式:文本相比 上传者: hzwer 提交提交记录总计商量 1 测量检验数据  

标题陈诉

提交二个长为 nnn 的数列,以及 nnn 个操作,操作涉及区间开药方,区间求和。

标题陈诉

交付贰个长为 nnn 的数列,以及 nnn 个操作,操作涉及区间加法,询问区间内小于有些值 xxx 的前任(比其小的最大意素)。

主题素材陈诉

交给多个长为 nnn 的数列,以及 nnn 个操作,操作涉及区间加法,区间求和。

难题陈诉

交付一个长为 nnn 的数列,以及 nnn 个操作,操作涉及区间加法,单点查值。

输入格式

首先行输入二个数字 nnn。

其次行输入 nnn 个数字,第
i 个数字为 aia_ia​i​​,以空格隔绝。

接下去输入 nnn 行询问,每行输入多少个数字 opt\mathrm{opt}opt、lll、rrr、ccc,以空格隔绝。

若 opt=0\mathrm{opt} =
0opt=0,表示将位于 [l,r][数列分块入门。l, r][l,r] 的中间的数字都开药方。

若 opt=1\mathrm{opt} =
1opt=1,表示领悟位于 [l,r][l, r][l,r] 的装有数字的和。

输入格式

率先行输入二个数字 nnn。

第二行输入 nnn 个数字,第
i 个数字为 aia_ia​i​​,以空格隔断。

接下去输入 nnn 行询问,每行输入两个数字 opt\mathrm{opt}opt、lll、rrr、ccc,以空格隔绝。

若 opt=0\mathrm{opt} =
0opt=0,表示将位于 [l,r][l, r][l,r] 的中间的数字都加 ccc。

若 opt=1\mathrm{opt} =
1opt=1,表示通晓 [l,r][l, r][l,r] 中 ccc 的先行者的值(不设有则输出 −1-1−1)。

输入格式

第一行输入叁个数字 nnn。

其次行输入 nnn 个数字,第
i 个数字为 aia_ia​i​​,以空格隔绝。

接下去输入 nnn 行询问,每行输入多个数字 opt\mathrm{opt}opt、lll、rrr、ccc,以空格隔开。

若 opt=0\mathrm{opt} =
0opt=0,表示将身处 [l,r][l, r][l,r] 的里边的数字都加 ccc。

若 opt=1\mathrm{opt} =
1opt=1,表示精通位于 [l,r][l, r][l,r] 的具有数字的和 mod(c+1)mod (c+1)mod(c+1)。

输入格式

首先行输入一个数字 nnn。

其次行输入 nnn 个数字,第 iii 个数字为 aia_ia​i​​,以空格隔断。

接下去输入 nnn 行询问,每行输入多个数字 opt\mathrm{opt}opt、lll、rrr、ccc,以空格隔离。

若 opt=0\mathrm{opt} =
0opt=0,表示将位于 [l,r][l, r][l,r] 的时期的数字都加 ccc。

若 opt=1\mathrm{opt} =
1opt=1,表示精晓 ara_ra​r​​ 的值(lll 和 ccc 忽略)。

输出格式

对于每趟询问,输出一行三个数字代表答案。

出口格式

对此每便询问,输出一行多少个数字代表答案。

输出格式

对此每便询问,输出一行三个数字代表答案。

输出格式

对于每一次询问,输出一行三个数字代表答案。

样例

样例

样例

样例

样例输入

4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4

样例输入

4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4

样例输入

4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4

样例输入

4
1 2 2 3
0 1 3 1
1 0 1 0
0 1 2 2
1 0 2 0

样例输出

6
2

样例输出

3
-1

样例输出

1
4

样例输出

2
5

多少范围与唤醒

对于 100% 100\%100% 的数据,1≤n≤50000,−231≤others 1 \leq n \leq 50000,
-2^{31} \leq \mathrm{others}1≤n≤50000,−2​31​​≤others、ans≤231−1 \mathrm{ans} \leq 2^{31}-1ans≤2​31​​−1。

 

 

这道题的难点在于怎么样爱戴开根这几个美妙的操作

自个儿本人测的是1e7的数大致开五五回根就能化为1,所以我们直接保养整个块内的数是或不是成为了1就足以了

 

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define int long long 
using namespace std;
const int MAXN=1e5+10;
const int INF=1e8+10;
inline char nc()
{
    static char buf[MAXN],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    char c=nc();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
    return x*f;
}
int N;
int a[MAXN],block,L[MAXN],R[MAXN],belong[MAXN],sum[MAXN],flag[MAXN];

void Sqrt(int l,int r)
{
 for(int i=l;i<=min(r,R[l]);i++)
 {
  sum[belong[i]]-=a[i];
  a[i]=sqrt(a[i]);
  sum[belong[i]]+=a[i];
 }
 if(belong[l]!=belong[r])
  for(int i=L[r];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]-1;i++)
 {
  if(flag[i]) {continue;}
  flag[i]=1;
  for(int j=L[i*block];j<=R[i*block];j++)
  {
   sum[i]-=a[j];
   a[j]=sqrt(a[j]);
   sum[i]+=a[j];
   if(a[j]>1) flag[i]=0;
  }
 }
}
int Query(int l,int r)
{
 int ans=0;
 for(int i=l;i<=min(r,R[l]);i++)
  ans+=a[i];
 if(belong[l]!=belong[r])
  for(int i=L[r];i<=r;i++)
   ans+=a[i];
 for(int i=belong[l]+1;i<=belong[r]-1;i++)
  ans+=sum[i];
 return ans;
}
main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
   // freopen("b.out","w",stdout);
    #else
    #endif
 N=read();block=sqrt(N);
 for(int i=1;i<=N;i++) a[i]=read();
 for(int i=1;i<=N;i++) belong[i]=(i-1)/block+1,L[i]=(belong[i]-1)*block+1,R[i]=belong[i]*block;
 for(int i=1;i<=N;i++) sum[belong[i]]+=a[i];
 for(int i=1;i<=N;i++)
 {
  int opt=read(),l=read(),r=read(),c=read();
  if(opt==0) 
   Sqrt(l,r); 
  else  
   printf("%d\n",Query(l,r));
 }
    return 0;
}

  

. 数列分块入门 5, 内部存款和储蓄器限制:256 MiB
时间范围:500 ms 规范输入输出 标题类型:守旧 评测格局:文本比较上传者:hzwer 提交提交记录…

数量范围与唤醒

对于 100% 100\%100% 的数据,1≤n≤100000,−231≤others 1 \leq n \leq 100000,
-2^{31} \leq \mathrm{others}1≤n≤100000,−2​31​​≤others、ans≤231−1 \mathrm{ans} \leq 2^{31}-1ans≤2​31​​−1。

 

 

跟上一道题同样。

改一下二分就好了

mmp写错了三个地点调了一夜晚

 

 

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int MAXN=3*1e6+10;
const int INF=1e8+10;
inline char nc()
{
    static char buf[MAXN],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    char c=nc();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
    return x*f;
}
vector<int>v[10001];//用vector储存分块后块内的有序表
int block,L[MAXN],R[MAXN],a[MAXN],tag[MAXN],belong[MAXN],N;
void Sort(int p)
{
    v[p].clear();
    for(int i=L[p*block];i<=min(R[p*block],N);i++)
        v[p].push_back(a[i]);
    sort(v[p].begin(),v[p].end());
}
void IntervalAdd(int l,int r,int val)
{
    for(int i=l;i<=min(r,R[l]);i++) a[i]+=val;
    Sort(belong[l]);
    if(belong[l]!=belong[r])
    {
        for(int i=L[r];i<=r;i++)     a[i]+=val;
        Sort(belong[r]);
    }
    for(int i=belong[l]+1;i<=belong[r]-1;i++) tag[i]+=val;    
}
int Query(int l,int r,int val)
{
    int ans=-1;
    for(int i=l;i<=min(r,R[l]);i++) 
        if(a[i]+tag[belong[l]]<val) 
            ans=max(ans,a[i]+tag[belong[l]]);
    if(belong[l]!=belong[r])
        for(int i=L[r];i<=r;i++)
            if(a[i]+tag[belong[r]]<val) ans=max(ans,a[i]+tag[belong[r]]);
    for(int i=belong[l]+1;i<=belong[r]-1;i++)
    {
        int x=val-tag[i];
        int pos=lower_bound(v[i].begin(),v[i].end(),x)-v[i].begin();
        if(pos-1>=0) ans=max(ans,v[i][pos-1]+tag[i]);
    }
    return ans;
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    freopen("b.out","w",stdout);
    #else
    #endif
    N=read();block=sqrt(N+0.5);
    for(int i=1;i<=N;i++) a[i]=read();
    for(int i=1;i<=N;i++) belong[i]=(i-1)/block+1,L[i]=(belong[i]-1)*block+1,R[i]=belong[i]*block;
    for(int i=1;i<=N;i++) v[belong[i]].push_back(a[i]);
    for(int i=1;i<=belong[N];i++) Sort(i);
    for(int i=1;i<=N;i++)
    {
        int opt=read(),l=read(),r=read(),c=read();
        if(opt==0) IntervalAdd(l,r,c);
        else       printf("%d\n",Query(l,r,c));
    }
    return 0;
}

 

 

 

. 数列分块入门 3, 内部存款和储蓄器限制:256 MiB
时间范围:1500 ms 标准输入输出 标题类型:古板 评测格局:文本相比较上传者:hzwer 提交提交记…

数据范围与唤醒

对于 100% 100\%100% 的数据,1≤n≤50000,−231≤others 1 \leq n \leq 50000,
-2^{31} \leq \mathrm{others}1≤n≤50000,−2​31​​≤others、ans≤231−1 \mathrm{ans} \leq 2^{31}-1ans≤2​31​​−1。

 

分块

保卫安全块的值

任何的根据套路来

 

 

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define int long long 
using namespace std;
const int MAXN=2*1e6+10;
const int INF=1e8+10;
inline char nc()
{
    static char buf[MAXN],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    char c=nc();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
    return x*f;
}
int a[MAXN],belong[MAXN],L[MAXN],R[MAXN],sum[MAXN],tag[MAXN],block;
void IntervalAdd(int l,int r,int val)
{
    for(int i=l;i<=min(R[l],r);i++) a[i]+=val,sum[belong[i]]+=val;
    if(belong[l]!=belong[r])
        for(int i=L[r];i<=r;i++)
            a[i]+=val,sum[belong[i]]+=val;
    for(int i=belong[l]+1;i<=belong[r]-1;i++)
        tag[i]+=val;
}
int Query(int l,int r,int mod)
{
    int ans=0;
    for(int i=l;i<=min(R[l],r);i++) 
        ans+=a[i]+tag[belong[i]],ans=ans%mod;

    if(belong[l]!=belong[r])
        for(int i=L[r];i<=r;i++)
            ans+=a[i]+tag[belong[i]];
    for(int i=belong[l]+1;i<=belong[r]-1;i++)
        ans+=sum[i]+tag[i]*block,ans=ans%mod;
    return ans%mod;
}
main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
   // freopen("b.out","w",stdout);
    #else
    #endif
    int N=read();block=sqrt(N);
    for(int i=1;i<=N;i++) belong[i]=(i-1)/block+1,L[i]=(belong[i]-1)*block+1,R[i]=belong[i]*block;
    for(int i=1;i<=N;i++) a[i]=read();
    for(int i=1;i<=N;i++) sum[belong[i]]+=a[i];
    for(int i=1;i<=N;i++)
    {
        int opt=read(),l=read(),r=read(),c=read();
        if(opt==0) IntervalAdd(l,r,c);
        else        
            printf("%lld\n",Query(l,r,c+1));
     } 
    return 0;
}

 

 

 

. 数列分块入门 4, 内部存款和储蓄器限制:256 MiB
时间范围:500 ms 规范输入输出 标题类型:古板 评测情势:文本相比较上传者:hzwer 提交提交记录…

数据范围与唤醒

对于 100% 100\%100% 的数据,1≤n≤50000,−231≤others 1 \leq n \leq 50000,
-2^{31} \leq \mathrm{others}1≤n≤50000,−2​31​​≤others、ans≤231−1 \mathrm{ans} \leq 2^{31}-1ans≤2​31​​−1。

 

 

倍感温馨好菜呀,,

这种难度的题都写不出来QWQ。。

思路比较轻便,对队列的下标举行分块,维护每种块加上的因素,

不在整块内的暴力加

www.5929.com, 

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN=1e5+10;
const int INF=1e8+10;
inline char nc()
{
    static char buf[MAXN],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    char c=nc();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
    return x*f;
}
int N,a[MAXN],tag[MAXN],belong[MAXN],L[MAXN],R[MAXN];
int block;
void IntervalAdd(int l,int r,int val)
{
    for(int i=l;i<=min(r,R[l]);i++)    a[i]+=val;
    if(belong[l]!=belong[r]) for(int i=L[r];i<=r;i++) a[i]+=val;
    for(int i=belong[l]+1;i<=belong[r]-1;i++) tag[i]+=val;
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    int N=read();block=sqrt(N);
    for(int i=1;i<=N;i++) a[i]=read();
    for(int i=1;i<=N;i++) belong[i]=(i-1)/block+1;
    for(int i=1;i<=N;i++) L[i]=(belong[i]-1)*block+1;
    for(int i=1;i<=N;i++) R[i]=belong[i]*block;
    for(int i=1;i<=N;i++)
    {
        int opt=read(),l=read(),r=read(),c=read();
        if(opt==0) IntervalAdd(l,r,c);
        else printf("%d\n",a[r]+tag[belong[r]]);
    }
    return 0;
}

 

 

. 数列分块入门 1, 内部存款和储蓄器限制:256 MiB
时限:100 ms 规范输入输出 标题类型:守旧 评测格局:文本对比上传者:hzwer 提交提交记录…

Leave a Comment.