Skip to content

11371: 【原1371】期末打分

题目

题目描述

author: yura 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1371

Description

马上要到期末,助教们准备开始打分,然而毕设DDL要到了,助教只好请丁姐来帮忙。众所周知丁姐大一就把毕设做完了,这时候肯定空的跟狗一样。

翁阿姨让丁姐统计分数落在区间[a,b]内的学生人数,由于学生很多,丁姐很懒,他决定把这个任务交给你。

Input Format

第一行两个整数n, m 表示有n个学生,m次询问

第二行n个正整数表示每个学生的分数

之后m行每行两个整数a, b

Output Format

对每个询问,输出学生人数

Sample Input

10 5
8 1 2 4 10 6 6 6 8 5 
1 1
4 5
1 10
7 10
3 10

Sample Output

1
2
10
3
8

Hint

数据范围n <= 100000, m <= 100000

由于输出数量较大,不要用cin和cout做输入输出,使用如下方式

#include <cstdio>
// 输入
int n, m;
scanf(“%d%d”, &n, &m);

// 输出
printf(“%d\n”, result);

q4x3's solution

/**
 * 模...拟...?
 **/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

int n, m, tmp, l, r;
int dt[100233], a[100233], maxx;

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n;++ i) {
        scanf("%d", &dt[i]);
        maxx = dt[i] > maxx ? dt[i] : maxx;
    }
    for(int i = 1;i <= n;++ i) {
        for(int j = dt[i];j <= maxx;++ j)
            ++ a[j];
    }
    for(int i = 1;i <= m;++ i) {
        scanf("%d%d", &l, &r);
        printf("%d\n", a[r] - a[l - 1]);
    }
}

victrid's solution

#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
//??前缀和
int strage[1000000] = {0};
int accu[1000000]   = {0};
int main() {
    int n, m, imax = 0, score;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        int score = 0;
        scanf("%d", &score);
        ++strage[score];
        imax = max(score, imax);
    }
    accu[0] = 0;
    for (int i = 1; i <= imax; ++i)
        accu[i] = accu[i - 1] + strage[i];
    int a, b;
    for (int i = 0; i < m; ++i) {
        scanf("%d %d", &a, &b);
        if (b > imax)
            b = imax;
        printf("%d\n", accu[b] - accu[a - 1]);
    }
    return 0;
}

yyong119's solution

#include <cstdio>
using namespace std;
const int MAX_N = 100001;
int tree[MAX_N << 2];

void update(int t, int l, int r, int point) {

    ++tree[t];
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (point <= mid)
        update(t << 1, l, mid, point);
    else
        update(t << 1 | 1, mid + 1, r, point);
}

int query(int t, int l, int r, int ql, int qr) {

    if (l == ql && r == qr) return tree[t];
    int mid = (l + r) >> 1;
    if (qr <= mid)
        return query(t << 1, l, mid, ql, qr);
    else if (ql > mid)
        return query(t << 1 | 1, mid + 1, r, ql, qr);
    else
        return query(t << 1, l, mid, ql, mid) + query(t << 1 | 1, mid + 1, r, mid + 1, qr);
}

int main() {

    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        int tmp;
        scanf("%d", &tmp);
        update(1, 1, n, tmp);
    }
    for (int i = 0; i < m; ++i) {
        int tmpl, tmpr;
        scanf("%d%d", &tmpl, &tmpr);
        printf("%d\n", query(1, 1, n, tmpl, tmpr));
    }
    return 0;
}