# 11371: 【原1371】期末打分

### 题目描述

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

## 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

``````#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;
}
``````