Power Sockets【CF 1469F】【线段树+贪心】

有N条链，每条链上有len[i]个点，现在树上有一个白点（根），我们每次可以选择一条链，链接到已知树上的任意白点上，然后链接的两点变黑，我们想知道树上白点数大于等于K的时候，第K近的白点距离根节点的距离。

所以，有贪心的策略，我们每次都选剩下的最长的链挂到树上去，然后每次查询答案即可，而且我们肯定选择链中心的点，去挂在树上距离根节点最近的白点上面。然后就是一个简单的区间更新和区间查询的过程了，线段树的简单操作了。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cmath>
  4 #include <string>
  5 #include <cstring>
  6 #include <algorithm>
  7 #include <limits>
  8 #include <vector>
  9 #include <stack>
 10 #include <queue>
 11 #include <set>
 12 #include <map>
 13 #include <bitset>
 14 #include <unordered_map>
 15 #include <unordered_set>
 16 #define lowbit(x) ( x&(-x) )
 17 #define pi 3.141592653589793
 18 #define e 2.718281828459045
 19 #define INF 0x3f3f3f3f
 20 #define HalF (l + r)>>1
 21 #define lsn rt<<1
 22 #define rsn rt<<1|1
 23 #define Lson lsn, l, mid
 24 #define Rson rsn, mid+1, r
 25 #define QL Lson, ql, qr
 26 #define QR Rson, ql, qr
 27 #define myself rt, l, r
 28 #define pii pair<int, int>
 29 #define MP(a, b) make_pair(a, b)
 30 using namespace std;
 31 typedef unsigned long long ull;
 32 typedef unsigned int uit;
 33 typedef long long ll;
 34 const int maxN = 8e5 + 7;
 35 int N, K;
 36 ll len[maxN];
 37 ll tree[maxN << 3], lazy[maxN << 3];
 38 void pushdown(int rt, int l, int r)
 39 {
 40     if(lazy[rt])
 41     {
 42         int mid = HalF;
 43         tree[lsn] += lazy[rt] * (mid - l + 1);
 44         tree[rsn] += lazy[rt] * (r - mid);
 45         lazy[lsn] += lazy[rt];
 46         lazy[rsn] += lazy[rt];
 47         lazy[rt] = 0;
 48     }
 49 }
 50 void pushup(int rt) { tree[rt] = tree[lsn] + tree[rsn]; }
 51 void update(int rt, int l, int r, int ql, int qr, ll val)
 52 {
 53     if(ql <= l && qr >= r)
 54     {
 55         lazy[rt] += val;
 56         tree[rt] += val * (r - l + 1);
 57         return;
 58     }
 59     pushdown(myself);
 60     int mid = HalF;
 61     if(qr <= mid) update(QL, val);
 62     else if(ql > mid) update(QR, val);
 63     else { update(QL, val); update(QR, val); }
 64     pushup(rt);
 65 }
 66 int _Fir(int rt, int l, int r)
 67 {
 68     if(l == r) return l;
 69     pushdown(myself);
 70     int mid = HalF;
 71     if(tree[lsn]) return _Fir(Lson);
 72     else return _Fir(Rson);
 73 }
 74 int _Ans(int rt, int l, int r, ll kth)
 75 {
 76     if(l == r) return l;
 77     pushdown(myself);
 78     int mid = HalF;
 79     if(kth <= tree[lsn]) return _Ans(Lson, kth);
 80     else return _Ans(Rson, kth - tree[lsn]);
 81 }
 82 int main()
 83 {
 84     scanf("%d%d", &N, &K);
 85     for(int i = 1; i <= N; i ++) scanf("%lld", &len[i]);
 86     sort(len + 1, len + N + 1, greater<ll>() );
 87     int ans = INF;
 88     int _UP = 8e5 + 5;
 89     update(1, 0, _UP, 0, 0, 1);
 90     for(int i = 1, pos, nex_L, nex_R, tmp; i <= N; i ++)
 91     {
 92         pos = _Fir(1, 0, _UP);
 93         update(1, 0, _UP, pos, pos, -1);
 94         nex_L = pos + 2;
 95         tmp = (int)len[i] - 1;
 96         nex_R = nex_L + tmp / 2 - 1;
 97         update(1, 0, _UP, nex_L, nex_R, 2);
 98         if(tmp & 1) update(1, 0, _UP, nex_R + 1, nex_R + 1, 1);
 99         if(tree[1] >= K)
100         {
101             ans = min(ans, _Ans(1, 0, _UP, K));
102         }
103     }
104     if(ans < INF) printf("%d
", ans);
105     else printf("-1
");
106     return 0;
107 }