QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#55418 | #3746. 千万别用树套树 | hyx000 | AC ✓ | 297ms | 5988kb | C++17 | 1.5kb | 2022-10-13 17:28:58 | 2022-10-13 17:28:59 |
Judging History
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