WHU-1551-Pairs(莫队算法+分块实现)
2024-09-01 08:24:44
Description
Give you a sequence consisted of n numbers. You are required to answer how many pairs of numbers (ai, aj) satisfy that | ai - aj | <= 2 and L <= i < j <= R.
Input
The input consists of one or more test cases.
For each case, the first line contains two numbers n and m, which represent the length of the number sequence and the number of queries. ( 1 <= n <= 10^5 and 1 <= m <= 10^5 )
The second line consists of n numbers separated by n - 1 spaces.( 0 <= ai <= 10^5 )
Then the m lines followed each contain two values Li and Ri.
For each case, the first line contains two numbers n and m, which represent the length of the number sequence and the number of queries. ( 1 <= n <= 10^5 and 1 <= m <= 10^5 )
The second line consists of n numbers separated by n - 1 spaces.( 0 <= ai <= 10^5 )
Then the m lines followed each contain two values Li and Ri.
Output
For each case, first output “Case #: “ in a single line, where # will be replaced by case number.
Then just output the answers in m lines.
Then just output the answers in m lines.
Sample Input
10 10
5 5 1 3 6 3 5 7 1 7
3 4
6 8
8 9
2 8
5 7
6 7
1 9
3 10
3 10
5 6
5 5 1 3 6 3 5 7 1 7
3 4
6 8
8 9
2 8
5 7
6 7
1 9
3 10
3 10
5 6
Sample Output
Case 1:
1
2
0
13
2
1
22
14
14
0
1
2
0
13
2
1
22
14
14
0
思路：把n个数分成 sqrt(n)块。用pos数组保存i所在的块。将全部查询按(pos(l),r)双keyword排序(这样子是为了降低后面的移动次数),然后模拟l向左向右移,r向左向右移,求出全部区间的结果。详见代码。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std; struct Q{
int l,r,index,ans;
}query[100001]; int pos[100001],f[100001],w[100001]; bool cmplr(struct Q a,struct Q b)
{
if(pos[a.l]==pos[b.l]) return a.r<b.r;//先按l所在的块排。假设相等就按r排
else return pos[a.l]<pos[b.l];
} bool cmpid(struct Q a,struct Q b)
{
return a.index<b.index;
} int update(int p,int ans,int add)//每移一步就更新一次结果
{
int i; if(add==1)//1代表区间长度加1
{
for(i=w[p]-2;i<=w[p]+2;i++)
{
if(i>=0) ans+=f[i];
}
f[w[p]]++;//f[i]表示当前区间里面包括了f[i]个i
}
else//-1代表区间长度减1
{
f[w[p]]--;//f[i]表示当前区间里面包括了f[i]个i
for(i=w[p]-2;i<=w[p]+2;i++)
{
if(i>=0) ans-=f[i];
}
} return ans;
} int main()
{
int n,m,cnt,i,ans,l,r,casenum=1; while(~scanf("%d%d",&n,&m))
{
memset(f,0,sizeof(f));//f[i]表示当前区间里面包括了f[i]个i cnt=(int)sqrt(n);//分成sqrt(n)块 for(i=1;i<=n;i++)
{
scanf("%d",&w[i]);
pos[i]=i/cnt;
} for(i=1;i<=m;i++)
{
scanf("%d%d",&query[i].l,&query[i].r);
query[i].index=i;
} sort(query+1,query+m+1,cmplr); ans=0;
l=1,r=0;
for(i=1;i<=m;i++)//每一次都使l和r指向查询区间的l和r，这样子区间长度添加时就不用把自己加进去了，区间长度减小时要把自己减去
{
if(query[i].l==query[i].r)
{
query[i].ans=0;
continue;
} if(r<query[i].r)
{
for(r=r+1;r<=query[i].r;r++)
{
ans=update(r,ans,1);
}
r--;
}
if(r>query[i].r)
{
for(;r>query[i].r;r--)
{
ans=update(r,ans,-1);
}
}
if(l<query[i].l)
{
for(;l<query[i].l;l++)
{
ans=update(l,ans,-1);
}
}
if(l>query[i].l)
{
for(l=l-1;l>=query[i].l;l--)
{
ans=update(l,ans,1);
}
l++;
} query[i].ans=ans;
//printf("index=%d,l=%d,r=%d,ans=%d\n",query[i].index,query[i].l,query[i].r,query[i].ans);
} sort(query+1,query+m+1,cmpid); printf("Case %d:\n",casenum++); for(i=1;i<=m;i++)
{
printf("%d\n",query[i].ans);
}
} }
最新文章
- 自定义UITableViewCell实现左滑动多菜单功能LeftSwipe
- 你真的了解load方法么？（转载）
- 学习笔记之-------UIScrollView 基本用法 代理使用
- Sprint(第八天11.21)
- R----stringr包介绍学习
- Qt操作xml文件（增删改功能）
- hdu 4630 No Pain No Game
- px em rem在WEB前端开发中的区别
- 关于ORA-04021解决办法（timeout occurred while waiting to lock object）
- 代码-Weka的决策树类J48
- C++小知识之sprintf用法
- u3d脚本生命周期
- Windows2008/2012多用户同时远程连接终端服务授权
- scala时间和时间戳互转
- 嵌入页面的几种方法（转载自萤火虫小Q）
- Solr入门介绍
- FastQC结果详解
- python 变量名的规范
- Area---poj1265（皮克定理+多边形求面积）
- windows 命令行报错：file(s) not in client view