QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#55418#3746. 千万别用树套树hyx000AC ✓297ms5988kbC++171.5kb2022-10-13 17:28:582022-10-13 17:28:59

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-13 17:28:59]
  • Judged
  • Verdict: AC
  • Time: 297ms
  • Memory: 5988kb
  • [2022-10-13 17:28:58]
  • Submitted

answer

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>

#define int long long
#define x first
#define y second
#define ps push_back
#define endl '\n'

#define kd                     \
  ios::sync_with_stdio(false); \
  cin.tie(0);                  \
  cout.tie(0);
using namespace std;
typedef pair<int, int> pi;
const int N = 1e5 + 100, mod = 1e9 + 7, INF = 1e10;
int lowbit(int x) { return x & -x; }
int gcd(int a, int b) { return a % b == 0 ? b : gcd(b, a % b); }

int tr[3][N];
int n;
void add(int x, int id, int c) {
  for (int i = x; i <= n; i += lowbit(i)) tr[id][i] += c;
}

int get(int x, int id) {
  int res = 0;
  for (int i = x; i; i -= lowbit(i)) res += tr[id][i];
  return res;
}

void solve() {
  int m;
  while (cin >> n >> m) {
    for (int i = 1; i <= n; i++)
      for (int j = 0; j <= 2; j++) tr[j][i] = 0;

    while (m--) {
      int op;
      cin >> op;
      if (op == 1) {
        int l, r;
        cin >> l >> r;
        add(l, 0, 1);
        add(r + 1, 0, -1);
        if (r - l >= 1) {
          add(l, 1, 1);
          add(r, 1, -1);
        }
        if (r - l >= 2) {
          add(l, 2, 1);
          add(r - 1, 2, -1);
        }
      } else {
        int l, r;
        cin >> l >> r;
        cout << get(l, r - l) << endl;
      }
    }
  }
}

signed main() {
  kd;
  int _;
  _ = 1;
  // cin>>_;
  while (_--) solve();
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 297ms
memory: 5988kb

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