QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#397297 | #3746. 千万别用树套树 | SamponYW | AC ✓ | 174ms | 4780kb | C++14 | 1.6kb | 2024-04-23 21:38:41 | 2024-04-23 21:38:42 |
Judging History
answer
#include <bits/stdc++.h>
#define db double
#define il inline
#define re register
#define ll long long
#define ui unsigned
#define ull ui ll
#define i128 __int128
#define pii pair<int, int>
#define fi first
#define se second
#define eb emplace_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define mems(v, x) memset(v, x, sizeof(v))
#define memc(a, b) memcpy(a, b, sizeof(a))
#define FOR(i, L, R) for(re int i = (L); i <= (R); ++i)
#define ROF(i, R, L) for(re int i = (R); i >= (L); --i)
#define LS i << 1, l, mid
#define RS i << 1 | 1, mid + 1, r
#define popc(x) __builtin_popcount(x)
using namespace std;
#define N 100005
#define P 1000000007
il int add(int x, int y) {return x + y < P ? x + y : x + y - P;}
il void addr(int &x, int y) {(x += y) >= P && (x -= P);}
il int qpow(int p, int n = P - 2) {
int s = 1;
while(n) {
if(n & 1) s = 1ll * s * p % P;
p = 1ll * p * p % P, n >>= 1;
}
return s;
}
int n, m;
struct bit {
int s[N];
il void clr() {mems(s, 0);}
il void add(int x, int v) {while(x <= n) s[x] += v, x += x & -x;}
il int query(int x) {int v = 0; while(x) v += s[x], x ^= x & -x; return v;}
il int query(int l, int r) {return query(r) - query(l - 1);}
} L, R;
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
while(cin >> n >> m) {
L.clr(), R.clr(); int A = 0;
while(m--) {
int op, a, b; cin >> op >> a >> b;
if(op == 1) ++A, L.add(a, 1), R.add(b, 1);
if(op == 2) cout << A - L.query(a + 1, n) - R.query(1, b - 1) << "\n";
}
}
cerr << 1.0 * clock() / CLOCKS_PER_SEC;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 174ms
memory: 4780kb
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