终极管理员
知识笔记
114阅读
code class="prism language-cpp">#include <bits/stdc.h>using namespace std;#define int long longusing ll long long;using ull unsigned long long;#define vi vector<int>#define pii pair<int, int>#define fi first#define se second#define pb push_back#define inf 1ll << 62#define ar(k) array<int, k>#define db double#define endl \n#define max(a, b) ((a) > (b) ? (a) : (b))#define min(a, b) ((a) < (b) ? (a) : (b))#define de_bug(x) cerr << #x << << x << endl#define all(a) a.begin(), a.end()#define IOS \ std::ios::sync_with_stdio(false); \ std::cin.tie(0); \ std::cout.tie(0);#define fer(i, a, b) for (int i a; i < b; i)#define der(i, a, b) for (int i a; i > b; i--)const int mod 998244353;const int N 1e6 10;mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());int n, m, k;struct node { int a, b, c, cnt, num;} e[N], d[N];int ans[N];int c[N];bool cmp1(node x, node y) { return x.a < y.a || (x.a y.a && x.b < y.b) || (x.a y.a && x.b y.b && x.c < y.c);}bool cmp2(node x, node y) { return x.b < y.b || (x.b y.b && x.c < y.c); }void add(int a, int b) { for (a; a < k; a (a & (-a))) c[a] b;}int query(int a) { int ans 0; for (; a; a - (a & (-a))) { ans c[a]; } return ans;}void cdq(int l, int r) { if (l r) return; int mid (l r) >> 1; //cout<<l<< <<r<<endl; cdq(l, mid); cdq(mid 1, r); int len1 mid - l 1; int len2 r - (mid 1) 1; sort(d l, d len1 l, cmp2); sort(d mid 1, d mid 1 len2, cmp2); vector<int> x; for (int i l, j mid 1; j < r; j) { while (i < mid && d[i].b < d[j].b) { add(d[i].c, d[i].num); x.push_back(i); i; } d[j].cnt query(d[j].c); } for (auto &it : x) { add(d[it].c, -d[it].num); }}void solve() { cin >> n >> k; fer(i, 1, n) { int a, b, c; cin >> a >> b >> c; e[i] {a, b, c, 0, 0}; } sort(e 1, e 1 n, cmp1); int tt 0; int tot 0; for (int i 1; i < n; i) { tt; if (e[i].a ! e[i 1].a || e[i].b ! e[i 1].b || e[i].c ! e[i 1].c) { d[tot].a e[i].a; d[tot].b e[i].b; d[tot].c e[i].c; d[tot].num tt; tt 0; } } // cout<<tot<<endl; cdq(1, tot); for (int i 1; i < tot; i) ans[d[i].cnt d[i].num - 1] d[i].num; for (int i 0; i < n; i) { cout << ans[i] << endl; }}signed main() { // freopen(../a.txt, r, stdin); // freopen(../b.txt, w, stdout); IOS; int _ 1; // cin>>_; while (_--) solve(); return 0;}/pre>
标签：
