|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <stack> using namespace std; #define MAXN 262146 int tree[MAXN]; int M = 1; void tree_init(int num){ memset(tree, 0, sizeof(tree)); M = 1; for (; M <= num; M <<= 1); M--; } void tree_add(int from,int to,int curl,int curr,unsigned int cur){ //put cur = 1 curl = 1 curr = M+1 to initalize if (from <= curl && to >= curr) { //completely include T tree[cur]++; return; }else if(curl > to || curr < from){ //completely out F0 return; }else{ //partially in F1 cur <<= 1; tree_add(from, to, curl, (curl+curr)/2, cur); tree_add(from, to, (curl+curr)/2+1, curr, cur+1); } } int tree_query(unsigned int currNode){ int res = 0; currNode += M; while (currNode) { res += tree[currNode]; currNode >>= 1; } return res; } int main(){ ios_base::sync_with_stdio(false); int num = 0; while (cin >> num && num) { int n = num; tree_init(num); while (num--) { int a = 0,b = 0; cin >> a >> b; tree_add(min(a,b), max(a,b), 1, M+1, 1); } for (int i = 1; i <= n; i++) { cout << tree_query(i); if (i != n) { cout << ' '; } } cout << 'n'; } return 0; } |
基于zkw线段树自己改造了一个，其实可以爆过去，时间还更少，真是邪乎。
