【问题描述】

给出一个n长的数列,在进行m次询问,每次询问询问两个区间【L1,R1】【L2,R2】

询问数列第L2到R2个数字每一个数在数列第L1到R1个数中有多少个数字不大于他。

【输入格式】

第一行两个整数n,m

第二行n个整数,表示数列

接下来m行,每行四个整数L1,R1,L2,R2,意义如上

【输出格式】

m行,每行R2-L1+1个整数,第一个整数表示第L2个数在数列第L1到R1个数中不大于它的个数,第二个整数表示第L2+1个数在数列第L1到R1个数中不大于他的个数,以此类推

【样例输入】

5 3

5 2 3 4 1

1 2 3 4

2 3 1 5

1 5 2 3

【样例输出】

1 1

2 1 2 2 0

2 3

【数据规模和约定】

n,m<=1000,数列的数字非负且小于1000。

分析见代码注释
#include<stdio.h> int main(){ static int N[1000],M[1000][4];
//因为规模比较大,所以用静态,一般二维数组最大为320*640 int n,m; scanf("%d %d",&n,&m); int i,j;
for(i=0;i<n;i++){ scanf("%d",&N[i]); //输入数组 } for(i=0;i<m;i++){
for(j=0;j<4;j++){ scanf("%d",&M[i][j]); //输入询问的数组 } } static int
print[1000]={0}; //定义输出的数组 int sign,x,l1,r1,l2,r2; for(i=0;i<m;i++){ //m组询问
j=0; //每次循环令输出数组的起始为0 sign=M[i][3]-M[i][2]+1; //表示输出数组的长度 l2=M[i][2];
//因为是静态数组,数值不能改变,所以拿一个变量代替 r2=M[i][3]; while(l2<=r2){ //遍历L2到R2 l1=M[i][0];
r1=M[i][1]; while(l1<=r1){ //遍历L1到R1 if(N[(l2-1)]>=N[(l1-1)]){ //符合条件
print[j]++; } l1++; } j++; //遍历第二次,输出数组的下标加一 l2++; } for(x=0;x<sign;x++){ //输出
printf("%d ",print[x]); print[x]=0; } printf("\n"); } return 0; }

技术
今日推荐
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:[email protected]
QQ群:766591547
关注微信