1. 数列分块入门1
区间修改，单点查询
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=5e4+5;
int n,len,cnt;
int a[MAXN],tag[MAXN];
int pos[MAXN],l[MAXN],r[MAXN];
inline void add(int x,int y,int k)
{
if(x>y)return;
if(pos[x]==pos[y])
{
for(register int i=x;i<=y;i++)
a[i]+=k;
return;
}
for(register int i=x;i<=r[pos[x]];i++)a[i]+=k;
for(register int i=l[pos[y]];i<=y;i++)a[i]+=k;
for(register int i=pos[x]+1;i<=pos[y]-1;i++)tag[i]+=k;
}
signed main()
{
scanf("%lld",&n);
len=sqrt(n);
cnt=n/len+(n%len!=0);
for(register int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
pos[i]=(i-1)/len+1;
}
for(register int i=1;i<=cnt;i++)
{
l[i]=(i-1)*len+1;
r[i]=i*len;
}
for(register int i=1;i<=n;i++)
{
int op,x,y,c;
scanf("%lld%lld%lld%lld",&op,&x,&y,&c);
if(op==0)add(x,y,c);
if(op==1)printf("%lld\n",a[y]+tag[pos[y]]);
}
return 0;
}
2. 数列分块入门2
区间修改，询问区间中小于 \(c\) 的数的个数
用 \(b\) 数组记录每个块排序之后的数组，以便二分查询排名
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+5;
int n,len,cnt;
int a[MAXN],b[MAXN],tag[MAXN];
int pos[MAXN],l[MAXN],r[MAXN];
inline void add(int x,int y,int k)
{
if(x>y)return;
if(pos[x]==pos[y])
{
for(register int i=x;i<=y;i++)
a[i]+=k;
return;
}
for(register int i=x;i<=r[pos[x]];i++)a[i]+=k;
for(register int i=l[pos[y]];i<=y;i++)a[i]+=k;
for(register int i=pos[x]+1;i<=pos[y]-1;i++)tag[i]+=k;
}
inline int ask(int x,int y,int k)
{
int sum=0;
if(x>y)return 0;
if(pos[x]==pos[y])
{
for(register int i=x;i<=y;i++)
if(a[i]+tag[pos[i]]<k)sum++;
return sum;
}
for(register int i=x;i<=r[pos[x]];i++)if(a[i]+tag[pos[i]]<k)sum++;
for(register int i=l[pos[y]];i<=y;i++)if(a[i]+tag[pos[i]]<k)sum++;
for(register int i=pos[x]+1;i<=pos[y]-1;i++)
{
int w=lower_bound(b+l[i],b+1+r[i],k-tag[i])-b;
sum+=(w-l[i]);
}
return sum;
}
signed main()
{
scanf("%lld",&n);
len=sqrt(n);
cnt=(n/len)+(n%len!=0);
for(register int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
b[i]=a[i];
pos[i]=(i-1)/len+1;
}
for(register int i=1;i<=cnt;i++)
{
l[i]=(i-1)*len+1;
r[i]=i*len;
}
r[cnt]=n;
for(register int i=1;i<=cnt;i++)
sort(b+l[i],b+1+r[i]);
for(register int i=1;i<=n;i++)
{
int op,x,y,c;
scanf("%lld%lld%lld%lld",&op,&x,&y,&c);
if(op==0)
{
add(x,y,c);
for(register int i=l[pos[x]];i<=r[pos[x]];i++)b[i]=a[i];
for(register int i=l[pos[y]];i<=r[pos[y]];i++)b[i]=a[i];
sort(b+l[pos[x]],b+1+r[pos[x]]);
sort(b+l[pos[y]],b+1+r[pos[y]]);
}
if(op==1)printf("%lld\n",ask(x,y,c*c));
}
return 0;
}
3. 数列分块入门3
区间修改，询问区间中 \(c\) 的前驱
和上一题差不多，同样也是块内排序，二分查找
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+5;
int n,len,cnt;
int a[MAXN],b[MAXN],tag[MAXN];
int pos[MAXN],l[MAXN],r[MAXN];
inline void add(int x,int y,int k)
{
if(x>y)return;
if(pos[x]==pos[y])
{
for(register int i=x;i<=y;i++)
a[i]+=k;
return;
}
for(register int i=x;i<=r[pos[x]];i++)a[i]+=k;
for(register int i=l[pos[y]];i<=y;i++)a[i]+=k;
for(register int i=pos[x]+1;i<=pos[y]-1;i++)tag[i]+=k;
}
inline int ask(int x,int y,int k)
{
int ans=-1;
if(x>y)return ans;
if(pos[x]==pos[y])
{
for(register int i=x;i<=y;i++)
if(a[i]+tag[pos[i]]<k)ans=max(ans,a[i]+tag[pos[i]]);
return ans;
}
for(register int i=x;i<=r[pos[x]];i++)if(a[i]+tag[pos[i]]<k)ans=max(ans,a[i]+tag[pos[i]]);
for(register int i=l[pos[y]];i<=y;i++)if(a[i]+tag[pos[i]]<k)ans=max(ans,a[i]+tag[pos[i]]);
for(register int i=pos[x]+1;i<=pos[y]-1;i++)
{
int w=lower_bound(b+l[i],b+1+r[i],k-tag[i])-b;
w--;
if(b[w]+tag[pos[w]]<k)ans=max(ans,b[w]+tag[pos[w]]);
}
return ans;
}
signed main()
{
scanf("%lld",&n);
len=sqrt(n);
cnt=(n/len)+(n%len!=0);
for(register int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
b[i]=a[i];
pos[i]=(i-1)/len+1;
}
for(register int i=1;i<=cnt;i++)
{
l[i]=(i-1)*len+1;
r[i]=i*len;
}
r[cnt]=n;
for(register int i=1;i<=cnt;i++)
sort(b+l[i],b+1+r[i]);
for(register int i=1;i<=n;i++)
{
int op,x,y,c;
scanf("%lld%lld%lld%lld",&op,&x,&y,&c);
if(op==0)
{
add(x,y,c);
for(register int i=l[pos[x]];i<=r[pos[x]];i++)b[i]=a[i];
for(register int i=l[pos[y]];i<=r[pos[y]];i++)b[i]=a[i];
sort(b+l[pos[x]],b+1+r[pos[x]]);
sort(b+l[pos[y]],b+1+r[pos[y]]);
}
if(op==1)printf("%lld\n",ask(x,y,c));
}
return 0;
}