系统学习参考 hzw大佬原博
分块基本操作就不写了 这里主要是贴板子方便复习使用
毕竟比较简单易懂……
分块入门
1. 单点查询与区间加法
暴力分块
打标区间加
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#define N 1000005
using namespace std;
int a[N],num[N],tot,n,m,ans[N],k,sum,bl[N],r[N],l[N],c[N],len[N];
int cnt,tag[N];
struct node
{
int l,r,k,id;
}q[N];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
bool mmp(node x,node y)
{
return bl[x.l]<bl[y.l]||bl[x.l]==bl[y.l]&&x.r<y.r;
}
void update(int x,int y,int k)
{
int L=bl[x],R=bl[y];
if(L==R)
for(int i=x;i<=y;i++)
a[i]+=k;
else
{
for(int i=x;i<=r[L];i++)a[i]+=k;
for(int i=l[R];i<=y;i++)a[i]+=k;
for(int i=L+1;i<R;i++)
tag[i]+=k;
}
}
int main()
{
n=read();
int p=sqrt(n);
for(int i=1;i<=n;i++)bl[i]=(i-1)/p+1;
for(int i=1;i<=n;i++)
{
r[bl[i]]=i;
if(!l[bl[i]])l[bl[i]]=i;
}
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)
{
int op,l,r,k;
scanf("%d%d%d%d",&op,&l,&r,&k);
if(op==0)update(l,r,k);
else printf("%d\n",a[r]+tag[bl[r]]);
}
return 0;
}
2. 区间加法与查找
第一行输入一个数字 n。
op1 区间加
op2 区间找比c*c小的数的个数
vector暴力清除
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#define N 50005
using namespace std;
int a[N],num[N],tot,n,m,ans[N],k,sum,bl[N],r[N],l[N],c[N],len[N];
int cnt,tag[N];
vector<int>ve[N];
struct node
{
int l,r,k,id;
}q[N];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
bool mmp(node x,node y)
{
return bl[x.l]<bl[y.l]||bl[x.l]==bl[y.l]&&x.r<y.r;
}
void re(int x)
{
ve[x].clear();
for(int i=l[x];i<=r[x];i++)
ve[x].push_back(a[i]);
sort(ve[x].begin(),ve[x].end());
}
void update(int x,int y,int k)
{
int L=bl[x],R=bl[y];
if(L==R)
{
for(int i=x;i<=y;i++)
a[i]+=k;
re(L);
}
else
{
for(int i=x;i<=r[L];i++)a[i]+=k;
re(L);
for(int i=l[R];i<=y;i++)a[i]+=k;
re(R);
for(int i=L+1;i<R;i++)
tag[i]+=k;
}
}
int query(int x,int y,int k)
{
int tot=0;
int L=bl[x],R=bl[y];
if(L==R)
{
for(int i=x;i<=y;i++)
if(a[i]+tag[bl[i]]<k)tot++;
}
else
{
for(int i=x;i<=r[L];i++)
if(a[i]+tag[bl[i]]<k)tot++;
for(int i=l[R];i<=y;i++)
if(a[i]+tag[bl[i]]<k)tot++;
for(int i=L+1;i<R;i++)
{
int kk=k-tag[i];
tot+=lower_bound(ve[i].begin(),ve[i].end(),kk)-ve[i].begin();
}
}
return tot;
}
int main()
{
n=read();
int p=sqrt(n);
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)
{
bl[i]=(i-1)/p+1;
ve[bl[i]].push_back(a[i]);
}
for(int i=1;i<=n;i++)
{
r[bl[i]]=i;
if(!l[bl[i]])l[bl[i]]=i;
}
for(int i=1;i<=bl[n];i++)
sort(ve[i].begin(),ve[i].end());
for(int i=1;i<=n;i++)
{
int op,l,r,k;
scanf("%d%d%d%d",&op,&l,&r,&k);
if(op==0)update(l,r,k);
else printf("%d\n",query(l,r,k*k));
}
return 0;
}
3. 求前驱与加法
暴力vetor排序后二分
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#define N 100000+110
using namespace std;
int a[N],num[N],tot,n,m,ans[N],k,sum,bl[N],r[N],l[N],c[N],len[N];
int cnt,tag[N];
vector<int>ve[N];
struct node
{
int l,r,k,id;
}q[N];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
bool mmp(node x,node y)
{
return bl[x.l]<bl[y.l]||bl[x.l]==bl[y.l]&&x.r<y.r;
}
void re(int x)
{
ve[x].clear();
for(int i=l[x];i<=r[x];i++)
ve[x].push_back(a[i]);
sort(ve[x].begin(),ve[x].end());
}
void update(int x,int y,int k)
{
int L=bl[x],R=bl[y];
if(L==R)
{
for(int i=x;i<=y;i++)
a[i]+=k;
re(L);
}
else
{
for(int i=x;i<=r[L];i++)a[i]+=k;
re(L);
for(int i=l[R];i<=y;i++)a[i]+=k;
re(R);
for(int i=L+1;i<R;i++)
tag[i]+=k;
}
}
int query(int x,int y,int k)
{
int tot=-(1<30);
int L=bl[x],R=bl[y];
if(L==R)
{
for(int i=x;i<=y;i++)
if(a[i]+tag[bl[i]]<k)tot=max(a[i]+tag[bl[i]],tot);
}
else
{
for(int i=x;i<=r[L];i++)
if(a[i]+tag[bl[i]]<k)tot=max(a[i]+tag[bl[i]],tot);
for(int i=l[R];i<=y;i++)
if(a[i]+tag[bl[i]]<k)tot=max(a[i]+tag[bl[i]],tot);
for(int i=L+1;i<R;i++)
{
int kk=k-tag[i];
int pre=lower_bound(ve[i].begin(),ve[i].end(),kk)-ve[i].begin();
if(pre)
{
tot=max(tot,ve[i][pre-1]+tag[i]);
}
}
}
if(tot==-(1<<30))return -1;
else
return tot;
}
int main()
{
n=read();
int p=sqrt(n);
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)
{
bl[i]=(i-1)/p+1;
ve[bl[i]].push_back(a[i]);
}
for(int i=1;i<=n;i++)
{
r[bl[i]]=i;
if(!l[bl[i]])l[bl[i]]=i;
}
for(int i=1;i<=bl[n];i++)
sort(ve[i].begin(),ve[i].end());
for(int i=1;i<=n;i++)
{
int op,l,r,k;
scanf("%d%d%d%d",&op,&l,&r,&k);
if(op==0)update(l,r,k);
else printf("%d\n",query(l,r,k));
}
return 0;
}
4. 询问区间和
依旧打标
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#define ll long long
#define N 500000+110
using namespace std;
int num[N],tot,n,m,ans[N],k,bl[N],c[N],len[N],p;
ll cnt,tag[N],sum[N],a[N],r[N],l[N];
vector<int>ve[N];
struct node
{
int l,r,k,id;
}q[N];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
bool mmp(node x,node y)
{
return bl[x.l]<bl[y.l]||bl[x.l]==bl[y.l]&&x.r<y.r;
}
void re(int x)
{
ve[x].clear();
for(int i=l[x];i<=r[x];i++)
ve[x].push_back(a[i]);
sort(ve[x].begin(),ve[x].end());
}
void update(int x,int y,int k)
{
int L=bl[x],R=bl[y];
if(L==R)
{
for(int i=x;i<=y;i++)
a[i]+=k,sum[bl[i]]+=k;
}
else
{
for(int i=x;i<=r[L];i++)
a[i]+=k,sum[bl[i]]+=k;
for(int i=l[R];i<=y;i++)
a[i]+=k,sum[bl[i]]+=k;
for(int i=L+1;i<R;i++)
tag[i]+=k;
}
}
ll query(int x,int y)
{
ll ans=0;
int L=bl[x],R=bl[y];
if(L==R)
{
for(int i=x;i<=y;i++)
ans+=a[i]+tag[L];
}
else
{
for(int i=x;i<=r[L];i++)
ans+=a[i]+tag[bl[i]];
for(int i=l[R];i<=y;i++)
ans+=a[i]+tag[bl[i]];
for(int i=L+1;i<R;i++)
{
ans+=sum[i]+tag[i]*p;
}
}
return ans;
}
int main()
{
n=read();
p=sqrt(n);
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)
{
bl[i]=(i-1)/p+1;
sum[bl[i]]+=a[i];
}
for(int i=1;i<=n;i++)
{
r[bl[i]]=i;
if(!l[bl[i]])l[bl[i]]=i;
}
for(int i=1;i<=n;i++)
{
int op,l,r,k;
scanf("%d%d%d%d",&op,&l,&r,&k);
if(op==0)update(l,r,k);
else printf("%lld\n",query(l,r)%(k+1));
}
return 0;
}
5. 开根号
暴力打标删除数
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#define ll long long
#define N 500000+110
using namespace std;
int num[N],tot,n,m,ans[N],k,bl[N],c[N],len[N],p;
ll cnt,tag[N],sum[N],a[N],r[N],l[N],flag[N];
vector<int>ve[N];
struct node
{
int l,r,k,id;
}q[N];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
bool mmp(node x,node y)
{
return bl[x.l]<bl[y.l]||bl[x.l]==bl[y.l]&&x.r<y.r;
}
void solve(int x)
{
if(flag[x])return ;
flag[x]=1;
sum[x]=0;
for(int i=l[x];i<=r[x];i++)
{
a[i]=sqrt(a[i]);
sum[x]+=a[i];
if(a[i]>1)flag[x]=0;
}
}
void update(int x,int y)
{
int L=bl[x],R=bl[y];
if(L==R)
{
for(int i=x;i<=y;i++)
{
sum[bl[i]]-=a[i];
a[i]=sqrt(a[i]);
sum[bl[i]]+=a[i];
}
}
else
{
for(int i=x;i<=r[L];i++)
{
sum[bl[i]]-=a[i];
a[i]=sqrt(a[i]);
sum[bl[i]]+=a[i];
}
for(int i=l[R];i<=y;i++)
{
sum[bl[i]]-=a[i];
a[i]=sqrt(a[i]);
sum[bl[i]]+=a[i];
}
for(int i=L+1;i<R;i++)
solve(i);
}
}
ll query(int x,int y)
{
ll ans=0;
int L=bl[x],R=bl[y];
if(L==R)
{
for(int i=x;i<=y;i++)
ans+=a[i];
}
else
{
for(int i=x;i<=r[L];i++)
ans+=a[i];
for(int i=l[R];i<=y;i++)
ans+=a[i];
for(int i=L+1;i<R;i++)
ans+=sum[i];
}
return ans;
}
int main()
{
n=read();
p=sqrt(n);
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)
{
bl[i]=(i-1)/p+1;
sum[bl[i]]+=a[i];
}
for(int i=1;i<=n;i++)
{
r[bl[i]]=i;
if(!l[bl[i]])l[bl[i]]=i;
}
for(int i=1;i<=n;i++)
{
int op,l,r,k;
scanf("%d%d%d%d",&op,&l,&r,&k);
if(op==0)update(l,r);
else printf("%lld\n",query(l,r));
}
return 0;
}
分块进阶
1. 第k小（主席树暴力版）
不带修改的，只能水过比较小的数据还是主席树快
如需修改加一个tag数组就行
#include <bits/stdc++.h>
#define N 300000+110
using namespace std;
int bl[N],n,m,p,l[N],r[N],a[N],st[N],out[N],maxx=-(1<<30),b[N],minn=(1<<30);
int findf(int x,int y,int k)
{
int ans=0;
int L=bl[x],R=bl[y];
if(L==R)
{
for(int i=x;i<=y;i++)
if(a[i]<k)ans++;
}
else
{
for(int i=x;i<=r[L];i++)
if(a[i]<k)ans++;
for(int i=l[R];i<=y;i++)
if(a[i]<k)ans++;
for(int i=L+1;i<R;i++)
{
int lt=l[i],rt=r[i];
int sum=0;
while(lt<=rt)
{
int mid=(lt+rt)/2;
if(b[mid]<k)sum=max(sum,mid-l[i]+1),lt=mid+1;
else rt=mid-1;
}
ans+=sum;
}
}
return ans;
}
int query(int x,int y,int z)
{
int l=minn,r=maxx;
int ans=0;
while(l<=r)
{
int mid=(l+r)/2;
if(findf(x,y,mid)<z)ans=max(ans,mid),l=mid+1;
else r=mid-1;
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
p=sqrt(n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
bl[i]=(i-1)/p+1;
maxx=max(maxx,a[i]);
minn=min(minn,a[i]);
b[i]=a[i];
}
for(int i=1;i<=n;i++)
{
if(!l[bl[i]])l[bl[i]]=i;
r[bl[i]]=i;
}
for(int i=1;i<=bl[n];i++)
sort(b+l[i],b+r[i]+1);
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
printf("%d\n",query(x,y,z));
}
return 0;
}
2. 区间众数
以前是黑题，现在紫了，OI题真的越来越难了，离谱x
这是一大难题呀，照着hzw大佬的代码码了2个小时才码过mmp
首先，什么样的问题能用到分块这种暴力？
必须能预处理整块信息，也就是有整块整块的变量才能使用暴力算法，
这个大家都知道，所以这题的关键就是预处理整块的众数，
至于小的零散块直接二分暴力求在区间内的出现次数，
这其实和luogu数颜色的思想不谋而合，刚好我昨天才做了那道题
于是大体思想就讲完了
直接看代码吧
//分块求区间众数
#include <bits/stdc++.h>
#define N 50005
#define ll long long
using namespace std;
int bl[N],l[N],r[N],n,p,a[N],cnt,val[N],m;
int f[505][505];//预处理每个大块l,r之间的区间众数
vector<int>ve[N];
map<int,int>mp;//map动态开数组避免数组太大
ll read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int vis[N];
void pre(int x)//预处理大块之间众数
{
memset(vis,0,sizeof(vis));
int mx=0,ans=0;
for(int i=l[x];i<=n;i++)
{
int t=bl[i];
vis[a[i]]++;
if(vis[a[i]]>mx||vis[a[i]]==mx&&val[a[i]]<val[ans])
mx=vis[a[i]],ans=a[i];
f[x][t]=ans;
}
}
int two_point(int x,int y,int v)//二分求区间出现次数，我手写二分TLE了QWQ
{
int t=upper_bound(ve[v].begin(),ve[v].end(),y)-lower_bound(ve[v].begin(),ve[v].end(),x);
return t;
}
int query(int x,int y)//只有这样写比较快，我的老版写法就T了QWQ
{
int ans,mx;
ans=f[bl[x]+1][bl[y]-1];//直接提取大块间众数信息
mx=two_point(x,y,ans);
for(int i=x;i<=min(r[bl[x]],y);i++)//零散块直接暴力二分查找
{
int t=two_point(x,y,a[i]);
if(t>mx||(t==mx&&val[a[i]]<val[ans]))ans=a[i],mx=t;
}
if(bl[x]!=bl[y])
for(int i=l[bl[y]];i<=y;i++)
{
int t=two_point(x,y,a[i]);
if(t>mx||(t==mx&&val[a[i]]<val[ans]))ans=a[i],mx=t;
}
return ans;
}
int main()
{
n=read();m=read();
p=sqrt(n);
for(int i=1;i<=n;i++)//预处理
{
a[i]=read();
if(!mp[a[i]])
{
mp[a[i]]=++cnt;
val[cnt]=a[i];
}
a[i]=mp[a[i]];//离散化操作
ve[a[i]].push_back(i);//记录每个数字的出现位置，因为是递增的可以直接二分
bl[i]=(i-1)/p+1;
if(l[bl[i]]==0)l[bl[i]]=i;
r[bl[i]]=i;
}
for(int i=1;i<=bl[n];i++)pre(i);
int pre_ans=0;
for(int i=1;i<=m;i++)
{
int x,y;
x=read();y=read();
x=(x+pre_ans-1)%n+1;y=(y+pre_ans-1)%n+1;
if(x>y)swap(x,y);
pre_ans=val[query(x,y)];
printf("%d\n",pre_ans);
}
return 0;
}
分块的具体应用
1.巧妙的分块——色板游戏
- 题目描述
色板长度为L，L是一个正整数，
所以我们可以均匀地将它划分成L块1厘米长的小方格。 并从左到右标记为1, 2, … L。
现在色板上只有一个颜色，老师告诉阿宝在色板上只能做两件事：
1.”C A B C” 指在A到 B 号方格中涂上颜色 C。
2.”P A B” 指老师的提问：A到 B号方格中有几种颜色。
学校的颜料盒中一共有 T 种颜料。为简便起见，
我们把他们标记为 1, 2, … T.
开始时色板上原有的颜色就为1号色。
面对如此复杂的问题，阿宝向你求助，你能帮助他吗？
- 主要思路
用暴力分块；
其实我也是看的题解才知道这种题也可以用分块暴力
首先我一看题就很疑惑，因为统计不同的颜色这种东西就算能处理每个块不同的颜色树，但跨块这就显得没有任何意义，非常摸不着头脑
但是我们可以维护当一整个大块都是一个颜色是的情况，这样就显得有意义起来，然后用一个数组a来记录零碎的信息，当一个大块中颜色不统一时，用f数组打标记，b数组清零，将信息转移至a数组，查询非整块是在a数组中，整块就直接赋给bl，这样就可以暴力了！简单粗暴，不O2 2000ms左右还是有点慢但思路很简单巧妙，非常不错！
- 代码
#include <bits/stdc++.h>
#define N 100000+110
using namespace std;
int n,m,t,blo[N],p;
struct node
{
int l,r,v;
int f[50];
}bl[N];//这是每个大的块的信息，颜色也是用来存储整块颜色都相同时的情况
int a[N];//这是每个零散块中信息或者是表示整块但颜色不一样的情况
void update(int p)//每一次计算时都把大块中的整块信息转移到a数组中，方便非整块统计
{
memset(bl[p].f,0,sizeof(bl[p].f));
if(bl[p].v!=0)
{
for(int i=bl[p].l;i<=bl[p].r;i++)
a[i]=bl[p].v;
bl[p].v=0;
}
for(int i=bl[p].l;i<=bl[p].r;i++)
bl[p].f[a[i]]=1;//将大块中的信息全部转入f数组中
}
void color(int l,int r,int k)//分整块或部分块进行操作
{
int L=blo[l],R=blo[r];
if(L==R)
{
update(L);
for(int i=l;i<=r;i++)
a[i]=k;
update(L);
}
else
{
update(L);
for(int i=l;i<=bl[L].r;i++)
a[i]=k;
update(L);
update(R);
for(int i=bl[R].l;i<=r;i++)
a[i]=k;
update(R);
for(int i=L+1;i<R;i++)
bl[i].v=k;
}
}
int query(int l,int r)
{
int L=blo[l],R=blo[r];
int flag[50];int ans=0;
memset(flag,0,sizeof(flag));
if(L==R)
{
update(L);
for(int i=l;i<=r;i++)
if(!flag[a[i]])
flag[a[i]]=1;
}
else
{
update(L);
for(int i=l;i<=bl[L].r;i++)
if(!flag[a[i]])flag[a[i]]=1;
update(R);
for(int i=bl[R].l;i<=r;i++)
if(!flag[a[i]])flag[a[i]]=1,ans++;
for(int i=L+1;i<R;i++)
{
if(bl[i].v==0)
{
for(int j=1;j<=t;j++)
if(bl[i].f[j]&&flag[j]==0)
flag[j]=1;
}
else if(!flag[bl[i].v])flag[bl[i].v]=1;
}
}
ans=0;
for(int i=1;i<=t;i++)
if(flag[i])ans++;
return ans;
}
int main()
{
scanf("%d%d%d",&n,&t,&m);
p=sqrt(n)+1;
for(int i=1;i<=n;i++)blo[i]=(i-1)/p+1,a[i]=1;//初始化
for(int i=1;i<=p;i++)
{
bl[i].v=0;
bl[i].l=(i-1)*p+1;
bl[i].r=i*p;
bl[i].f[1]=1;
}
for(int i=1;i<=m;i++)
{
char op[3];
int x,y,k;
scanf("%s %d%d",op,&x,&y);
if(x>y)swap(x,y);
if(op[0]=='C')
{
scanf("%d",&k);
color(x,y,k);
}
else
{
printf("%d\n",query(x,y));
}
}
return 0;
}
2. 分块——暴力统计
搞了4个多小时才好不容易把这题A了，虽然luogu加O2过的，但bzoj是过了的
搞了4个多小时才好不容易把这题A了，虽然luogu加O2过的，但bzoj是过了的
虽然跑的比较慢但觉得方法很好理解，一开始有些细节没考虑以及预处理比较慢，就没过。之后借鉴了黄学长的代码才弄出来
不嫌弃的话就看看吧
思路
这题和蒲公英其实是处理方法很相近
主要是预处理每个大块之间出现偶数次的数的个数
注意O(n)预处理，O($$n^2$$)肯定不行
查询的时候需要注意在处理零散块时也要统计一遍
要注意分奇偶考虑，在考虑零散块的时候也要考虑大块中的出现次数奇偶性。
例：在1-2中出现2次，2-6中出现3次，没有被统计过要加答案；
在1-2中出现1次，2-6出现2次，这时一共出现3次就不符合了，答案反而要减。
这是非常需要注意的，所以细节的处理也非常重要。
所以直接看代码吧
我用的vector估计比较慢，query写的也很繁复，这估计就是luogu TLE的原因吧，只有O2才能救我，但只觉得这样思路很清晰就这样写了
这题c给的真的有用吗emmmmmmm
代码
#include <bits/stdc++.h>
#define N 100005
#define ri register int
using namespace std;
int bl[N],l[N],r[N],n,p,a[N],cnt,val[N],m,num,vis2[N];
int f[1505][1505];//预处理每个大块l,r之间的出现次数为偶数次的个数
vector<int>ve[N];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int vis[N];
inline void pre()//预处理
{
for(ri i=1;i<=bl[n];i++)
{
int ans=0;
for(ri j=l[i];j<=n;j++)vis[a[j]]=0;
for(ri j=l[i];j<=n;j++)
{
if(!(vis[a[j]]&1)&&vis[a[j]])ans--;//如果在之前已经出现过偶数次了，说明此时这个数已经不符合要求，ans--
vis[a[j]]++;
if(!(vis[a[j]]&1))ans++;//此时满足偶数次，ans++
f[i][bl[j]]=ans;//边算边更新就不用n2了，我之前n2写法就很慢
}
}
}
inline int two_point(int x,int y,int v)//二分求在x-y区间出现的次数，不知道手写二分会不会快一些QWQ
{
int t=upper_bound(ve[v].begin(),ve[v].end(),y)-lower_bound(ve[v].begin(),ve[v].end(),x);
return t;
}
inline int query(int x,int y)//这部分可能我写的也比较慢，但还是比较好理解的
{
int ans=0,mx;
int L=bl[x],R=bl[y];
if(L==R)//当在同一个块时，直接暴力统计
{
for(ri i=x;i<=y;i++)
{
int t=two_point(x,y,a[i]);
if(!(t&1)&&!vis2[a[i]])ans++,vis2[a[i]]=1;
}
for(ri i=x;i<=y;i++)vis2[a[i]]=0;//清零
}
else
{
ans=f[L+1][R-1];//先计算出中间块的满足条件的数的个数
int ll=l[L+1];int rr=r[R-1];
for(ri i=x;i<=r[L];i++)
{
if(vis2[a[i]])continue;
int t=two_point(x,y,a[i]),t2=two_point(ll,rr,a[i]);
if(!(t&1))//如果在散区间中出现次数为偶数次
{if((t2&1)||!t2)ans++;}//如果在大块中出现奇数次或没出现，（之前也没统计过，此时满足条件，ans++
else if(!(t2&1)&&t2)ans--;//如果散区间出现奇数次，大块中出现偶数次且之前统计过，此时已经不满足条件，ans--
vis2[a[i]]=1;
}
for(ri i=l[R];i<=y;i++)//同上
{
if(vis2[a[i]])continue;
int t=two_point(x,y,a[i]),t2=two_point(ll,rr,a[i]);
if(!(t&1))
{if((t2&1)||!t2)ans++;}
else if(!(t2&1)&&t2)ans--;
vis2[a[i]]=1;
}
for(ri i=x;i<=r[L];i++) vis2[a[i]]=0;
for(ri i=l[R];i<=y;i++)vis2[a[i]]=0;
}
return ans;
}
int main()
{
n=read();num=read();m=read();
p=sqrt((double)n/log((double)n)*log(2));
for(ri i=1;i<=n;i++)//预处理
{
a[i]=read();
ve[a[i]].push_back(i);//用vector处理每个数字出现的位置，因为是递增的可以直接二分，所以我选择了vector而不是数组
bl[i]=(i-1)/p+1;
if(l[bl[i]]==0)l[bl[i]]=i;
r[bl[i]]=i;
}
pre();
int pre_ans=0;
for(ri i=1;i<=m;i++)
{
int x,y;
x=read();y=read();
x=(x+pre_ans)%n+1;
y=(y+pre_ans)%n+1;
if(x>y)swap(x,y);
pre_ans=query(x,y);
printf("%d\n",pre_ans);
}
return 0;
}
3. 用分块A树套树的暴力美学
今天偶然看到这题，当年被树套树吓到了然而如今一看，分块的确可以水过(当然要加O2)
加了O2也不算很慢，大概1560ms左右
这道题的确是各大分块板子的集合，也是很经典的查询，不太会分块操作的可以去loj练手
复杂度我就不写了，首页dalao写的很清楚
- 区间求排名
这个操作比较简单，直接暴力处理非整块+二分处理整块
分块中很常见的操作，多次写分块的同学都知道二分是分块的常见辅助算法
直接贴代码了
inline int Rank(int x,int y,int k)
{
int L=bl[x],R=bl[y],ans=1;
if(L==R)
{
for(int i=x;i<=y;i++)
if(a[i]<k)ans++;//暴力处理
}
else
{
for(int i=x;i<=r[L];i++)
if(a[i]<k)ans++;
for(int i=l[R];i<=y;i++)
if(a[i]<k)ans++;
for(int i=L+1;i<R;i++)
{
int kk=lower_bound(b+l[i],b+r[i]+1,k)-b;//整块二分处理
ans+=kk-l[i];
}
}
return ans;
}
- 区间第k小
前面写到过，直接贴代码
inline int query(int x,int y,int k)//与查排名的函数其实一样，就是把ans初始值改了一下罢了
{
int L=bl[x],R=bl[y],ans=0;
if(L==R)
{
for(int i=x;i<=y;i++)
if(a[i]<k)ans++;
}
else
{
for(int i=x;i<=r[L];i++)
if(a[i]<k)ans++;
for(int i=l[R];i<=y;i++)
if(a[i]<k)ans++;
for(int i=L+1;i<R;i++)
{
int kk=lower_bound(b+l[i],b+r[i]+1,k)-b;
ans+=kk-l[i];
}
}
return ans;
}
inline int Find(int x,int y,int k)//经典二分
{
int ll=1,rr=maxx,ans=0;
while(ll<=rr)
{
int mid=(ll+rr)/2;
int xx=query(x,y,mid);
if(xx<k)ans=max(ans,mid),ll=mid+1;
else rr=mid-1;
}
return ans;
}
- 单点修改
这个操作很简单，直接o(1)修改，再整块能重新排序一遍就行
inline void change(int pos,int k)
{
a[pos]=k;
for(int i=l[bl[pos]];i<=r[bl[pos]];i++)b[i]=a[i];
sort(b+l[bl[pos]],b+r[bl[pos]]+1);
}
- 查前驱和后继
这个和查排名操作差不多，也很好写。 直接用max和min记一下值就可以
inline int pre(int x,int y,int k)
{
int L=bl[x],R=bl[y],ma=-inf;
if(L==R)
{
for(int i=x;i<=y;i++)
if(a[i]<k)ma=max(ma,a[i]);
}
else
{
for(int i=x;i<=r[L];i++)
if(a[i]<k)ma=max(ma,a[i]);
for(int i=l[R];i<=y;i++)
if(a[i]<k)ma=max(ma,a[i]);
for(int i=L+1;i<R;i++)
{
int kk=lower_bound(b+l[i],b+r[i]+1,k)-b;
if(kk>l[i])//注意判断越界
ma=max(ma,b[kk-1]);
}
}
return ma;
}
inline int suc(int x,int y,int k)
{
int L=bl[x],R=bl[y],mi=inf;
if(L==R)
{
for(int i=x;i<=y;i++)
if(a[i]>k)mi=min(mi,a[i]);
}
else
{
for(int i=x;i<=r[L];i++)
if(a[i]>k)mi=min(mi,a[i]);
for(int i=l[R];i<=y;i++)
if(a[i]>k)mi=min(mi,a[i]);
for(int i=L+1;i<R;i++)
{
int kk=upper_bound(b+l[i],b+r[i]+1,k)-b;//这里直接upper_bound更方便
if(kk<=r[i])//注意边界
mi=min(b[kk],mi);
}
}
return mi;
}
就这么简单的搞完了？？
一看都是板子操作，很好想也很简单
比某树套树不是好多了吗，在考场上轻易水到70分的好成绩！！虽然我因为一个等于号调了一个上午，不够细心QWQ
所以
分块大法好！！
完整代码
#include <bits/stdc++.h>
#define inf 2147483647
using namespace std;
const int N=5e4+110;
int a[N],bl[N],b[N],n,m,cnt,p,l[N],r[N],maxx;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline int Rank(int x,int y,int k)
{
int L=bl[x],R=bl[y],ans=1;
if(L==R)
{
for(int i=x;i<=y;i++)
if(a[i]<k)ans++;
}
else
{
for(int i=x;i<=r[L];i++)
if(a[i]<k)ans++;
for(int i=l[R];i<=y;i++)
if(a[i]<k)ans++;
for(int i=L+1;i<R;i++)
{
int kk=lower_bound(b+l[i],b+r[i]+1,k)-b;
ans+=kk-l[i];
}
}
return ans;
}
inline int query(int x,int y,int k)
{
int L=bl[x],R=bl[y],ans=0;
if(L==R)
{
for(int i=x;i<=y;i++)
if(a[i]<k)ans++;
}
else
{
for(int i=x;i<=r[L];i++)
if(a[i]<k)ans++;
for(int i=l[R];i<=y;i++)
if(a[i]<k)ans++;
for(int i=L+1;i<R;i++)
{
int kk=lower_bound(b+l[i],b+r[i]+1,k)-b;
ans+=kk-l[i];
}
}
return ans;
}
inline int Find(int x,int y,int k)
{
int ll=1,rr=maxx,ans=0;
while(ll<=rr)
{
int mid=(ll+rr)/2;
int xx=query(x,y,mid);
if(xx<k)ans=max(ans,mid),ll=mid+1;
else rr=mid-1;
}
return ans;
}
inline void change(int pos,int k)
{
a[pos]=k;
for(int i=l[bl[pos]];i<=r[bl[pos]];i++)b[i]=a[i];
sort(b+l[bl[pos]],b+r[bl[pos]]+1);
}
inline int pre(int x,int y,int k)
{
int L=bl[x],R=bl[y],ma=-inf;
if(L==R)
{
for(int i=x;i<=y;i++)
if(a[i]<k)ma=max(ma,a[i]);
}
else
{
for(int i=x;i<=r[L];i++)
if(a[i]<k)ma=max(ma,a[i]);
for(int i=l[R];i<=y;i++)
if(a[i]<k)ma=max(ma,a[i]);
for(int i=L+1;i<R;i++)
{
int kk=lower_bound(b+l[i],b+r[i]+1,k)-b;
if(kk>l[i])
ma=max(ma,b[kk-1]);
}
}
return ma;
}
inline int suc(int x,int y,int k)
{
int L=bl[x],R=bl[y],mi=inf;
if(L==R)
{
for(int i=x;i<=y;i++)
if(a[i]>k)mi=min(mi,a[i]);
}
else
{
for(int i=x;i<=r[L];i++)
if(a[i]>k)mi=min(mi,a[i]);
for(int i=l[R];i<=y;i++)
if(a[i]>k)mi=min(mi,a[i]);
for(int i=L+1;i<R;i++)
{
int kk=upper_bound(b+l[i],b+r[i]+1,k)-b;
if(kk<=r[i])
mi=min(b[kk],mi);
}
}
return mi;
}
int main()
{
n=read();p=sqrt(n);m=read();
for(int i=1;i<=n;i++)
{
a[i]=read(),bl[i]=(i-1)/p+1;
if(!l[bl[i]])l[bl[i]]=i;
r[bl[i]]=i;
b[i]=a[i];
maxx=max(maxx,a[i]);
}
if(n%p==0)cnt=n/p;
else cnt=n/p+1;
for(int i=1;i<=cnt;i++)
sort(b+l[i],b+r[i]+1);
for(int i=1;i<=m;i++)
{
int op,l,r,k,pos;
op=read();
switch(op)
{
case 1:l=read();r=read();k=read();printf("%d\n",Rank(l,r,k));break;
case 2:l=read();r=read();k=read();printf("%d\n",Find(l,r,k));break;
case 3:pos=read();k=read();change(pos,k);break;
case 4:l=read();r=read();k=read();printf("%d\n",pre(l,r,k));break;
case 5:l=read();r=read();k=read();printf("%d\n",suc(l,r,k));break;
}
}
return 0;
}
一共也就150行左右，挺划算的