【问题描述】
给出一个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; }