QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#387693#3746. 千万别用树套树NYOJ-1AC ✓163ms4668kbC++17651b2024-04-12 18:54:072024-04-12 18:54:11

Judging History

This is the latest submission verdict.

  • [2024-04-12 18:54:11]
  • Judged
  • Verdict: AC
  • Time: 163ms
  • Memory: 4668kb
  • [2024-04-12 18:54:07]
  • Submitted

answer

#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 1000010
#define low(x) (x&-x)
typedef long long ll;
int n, q, t[maxn][2];

void add(int x, int flg) {
	while (x <= n) {
		t[x][flg] += 1;
		x += low(x);
	}
}
int sum(int x, int flg) {
	int res = 0;
	while (x > 0) {
		res += t[x][flg];
		x -= low(x);
	}
	return res;
}
int main() {
	while (~scanf("%d%d", &n, &q)) {
		for (int i = 1; i <= n; i++) t[i][0] = t[i][1] = 0;
		for (int i = 1; i <= q; i++) {
			int op, l, r; scanf("%d%d%d", &op, &l, &r);
			if (op == 1) {
				add(l, 0); add(r, 1);
			}
			else {
				printf("%d\n", sum(l, 0) - sum(r - 1, 1));
			}
		}
	}
	return 0;
}


詳細信息

Test #1:

score: 100
Accepted
time: 163ms
memory: 4668kb

input:

100000 100000
1 48500 63742
1 43673 89780
1 6471 44388
1 68054 71541
1 30056 91431
1 49687 70537
2 46899 46900
1 5165 57954
1 85892 88481
2 18060 18062
2 45289 45289
1 18927 67848
1 17389 96139
1 63451 92197
1 15473 87341
1 15162 15744
1 76728 99645
2 48730 48731
2 20886 20888
1 9756 67424
1 23175 4...

output:

2
2
3
7
5
8
9
4
6
2
11
13
13
10
13
15
9
10
14
16
17
16
16
15
2
4
11
6
11
12
23
9
26
3
28
20
12
12
22
30
5
27
6
29
10
14
27
6
17
15
9
30
20
34
7
36
15
8
32
16
21
40
19
2
1
12
12
39
37
13
19
20
1
9
37
1
41
40
20
34
45
43
27
30
47
29
13
50
41
44
29
35
38
53
2
46
54
36
56
58
45
32
42
26
52
42
60
1
4
25
...

result:

ok 500497 numbers