傳送門
思路：對于每一個詢問，我們都需要知道，從根節點出發，重量為X的球到達v點期間，往左走了幾個點（比X大的幾個，比X小的幾個），往右走了幾個點（比X大的幾個，比X小的幾個），我們可以用dfs從根節點出發，先遍歷左子樹，再遍歷右子樹，對于遍歷到的當前節點，我們查看是不是有到該點的詢問，如果有，就需要"得到到達該點的路徑中"往左走的點中幾個點大于X，幾個點小于X，往右也是同理，這里我們可以用線段樹tree_l和tree_r來維護，這樣我們只需要統計區間有幾個點就行，該點詢問之后我們把該點的資訊加入到tree_l和tree_r中，注意需要回溯，當然還有中概率為0的情況，我們只需要標記路線中所有的權值，如果 X存在于路線中，則重量為X的球到達點v的概率就是0，
1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 #include <queue> 5 6 using namespace std; 7 8 #define lson(rt) (rt << 1) 9 #define rson(rt) (rt << 1 | 1) 10 11 const int N = 1e5 + 10; 12 struct node 13 { 14 int rt, l, r, tot; 15 inline int mid() { return (l + r) >> 1; } 16 inline void init(int l1, int r1) { l = l1; r = r1; tot = 0; } 17 }tree[2][N << 2]; 18 vector<int > Rank; 19 vector<int > to[N]; 20 vector<pair<int ,int > > hav[N]; 21 int ans[N][2]; 22 int v[N], app[N]; 23 int Max; 24 25 void Build(int rt, int l, int r) 26 { 27 tree[0][rt].init(l, r); 28 tree[1][rt].init(l, r); 29 if(l == r) return; 30 Build(lson(rt), l, tree[0][rt].mid()); 31 Build(rson(rt), tree[0][rt].mid() + 1, r); 32 } 33 34 int Query(int rt, int l, int r, int d1, int d2, int pos) 35 { 36 if(d1 > d2) return 0; 37 if(d1 <= l && r <= d2) return tree[pos][rt].tot; 38 39 if(tree[pos][rt].mid() >= d2) { 40 return Query(lson(rt), l, tree[pos][rt].mid(), d1, d2, pos); 41 } else if(tree[pos][rt].mid() < d1) { 42 return Query(rson(rt), tree[pos][rt].mid() + 1, r, d1, d2, pos); 43 } else { 44 return Query(lson(rt), l, tree[pos][rt].mid(), d1, d2, pos) + 45 Query(rson(rt), tree[pos][rt].mid() + 1, r, d1, d2, pos); 46 } 47 } 48 49 inline void Push_up(int rt, int pos) 50 { 51 tree[pos][rt].tot = tree[pos][lson(rt)].tot + tree[pos][rson(rt)].tot; 52 } 53 54 void Add(int rt, int l, int r, int id, int v, int pos) 55 { 56 if(l == r) { 57 tree[pos][rt].tot += v; 58 return ; 59 } 60 61 if(tree[pos][rt].mid() >= id) { 62 Add(lson(rt), l, tree[pos][rt].mid(), id, v, pos); 63 } else { 64 Add(rson(rt), tree[pos][rt].mid() + 1, r, id, v, pos); 65 } 66 67 Push_up(rt, pos); 68 } 69 70 void dfs(int now) 71 { 72 for(auto info : hav[now]) { 73 int id_ball = lower_bound(Rank.begin(), Rank.end(), info.second) - Rank.begin() + 1; 74 //printf("v[%d] = %d app = %d info.second = %d\n", now, v[now], app[id_ball], info.second); 75 if(app[id_ball] && info.second == Rank[id_ball - 1]) { 76 ans[info.first][0] = -1; 77 // cout << "76 lines" << endl; 78 } else { 79 int Max_l = Query(1, 1, Max, 1, id_ball - 1, 0); 80 int Max_r = Query(1, 1, Max, 1, id_ball - 1, 1); 81 int Min_l = Query(1, 1, Max, id_ball, Max, 0); 82 int Min_r = Query(1, 1, Max, id_ball, Max, 1); 83 // printf("Min_l = %d Min_r = %d Max_l = %d Max_r = %d\n", Min_l, Min_r, Max_l, Max_r); 84 ans[info.first][0] = Max_r; 85 ans[info.first][1] = Min_l + Min_r + 3 * (Max_l + Max_r); 86 } 87 } 88 89 if(!to[now].size()) return; 90 91 int id = lower_bound(Rank.begin(), Rank.end(), v[now]) - Rank.begin() + 1; 92 app[id]++; 93 Add(1, 1, Max, id, 1, 0); 94 dfs(to[now][0]); 95 app[id]--; 96 Add(1, 1, Max, id, -1, 0); 97 98 id = lower_bound(Rank.begin(), Rank.end(), v[now]) - Rank.begin() + 1; 99 app[id]++; 100 Add(1, 1, Max, id, 1, 1); 101 dfs(to[now][1]); 102 app[id]--; 103 Add(1, 1, Max, id, -1, 1); 104 } 105 106 void work() 107 { 108 Build(1, 1, Max); 109 110 dfs(1); 111 } 112 113 void init(int n) 114 { 115 Rank.clear(); 116 for(int i = 1; i <= n; ++i) { 117 to[i].clear(); 118 hav[i].clear(); 119 app[i] = 0; 120 } 121 } 122 123 void solve() 124 { 125 int T; 126 scanf("%d", &T); 127 while(T--) { 128 129 int n; 130 scanf("%d", &n); 131 132 init(n); 133 134 ///價值 135 for(int i = 1; i <= n; ++i) { 136 scanf("%d", v + i); 137 // Max = max(Max, v[i]); 138 Rank.push_back(v[i]); 139 } 140 141 ///邊 142 int m; 143 scanf("%d", &m); 144 for(int i = 1; i <= m; ++i) { 145 int x, y1, y2; 146 scanf("%d%d%d", &x, &y1, &y2); 147 to[x].push_back(y1); 148 to[x].push_back(y2); 149 } 150 151 152 ///詢問 153 int q; 154 scanf("%d", &q); 155 for(int i = 1; i <= q; ++i) { 156 int x, y; 157 scanf("%d%d", &x, &y); 158 hav[x].push_back(make_pair(i, y)); 159 } 160 161 sort(Rank.begin(), Rank.end()); 162 Rank.erase(unique(Rank.begin(), Rank.end()), Rank.end()); 163 Max = Rank.size(); 164 165 work(); 166 167 for(int i = 1; i <= q; ++i) { 168 if(ans[i][0] == -1) printf("0\n"); 169 else printf("%d %d\n", ans[i][0], ans[i][1]); 170 } 171 172 } 173 } 174 175 int main() 176 { 177 solve(); 178 179 return 0; 180 } 181 182 /* 183 99 184 3 185 2 3 1 186 1 187 1 2 3 188 3 189 3 2 190 1 1 191 3 4 192 193 5 194 2 3 1 3 1 195 2 196 1 2 3 197 3 4 5 198 5 199 3 2 200 1 1 201 3 4 202 4 3 203 5 3 204 205 5 206 2 3 5 3 1 207 2 208 1 2 3 209 3 4 5 210 5 211 3 2 212 1 1 213 3 4 214 4 6 215 5 3 216 */
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/226020.html
標籤：其他
上一篇：蟻劍原理與魔改