第k小整数（树状数组）

洛谷传送门

入门难度。。

没错，但是我并不是要暴力做。

而是用树状数组来做。

先离散化，然后随便搞一搞就可以了。（晕。比暴力还慢）

如果要查找某一区间的的话可以把区间取出重新建树，然后再求。（更暴力）

1 #include <cstdio> 2 #include <vector> 3 #include <algorithm> 4 #define N 10001 5 #define lowbit(x) x & x 6 7 using namespace std; 8 9 int n, m, k; 10 int c[N]; 11 bool b[3 * N]; 12 struct node 13 a[N]; 16 17 inline bool cmp(node x, node y) 18 21 22 inline void add(int x) 23 29 } 30 31 int solve(int k) 32 40 return ans + 1; 41 } 42 43 int main() 44 52 if(m < k) 53 57 sort(a + 1, a + m + 1, cmp); 58 for(i = 1; i <= m; i++) add(a[i].id); 59 printf("%d\n", a[solve(k)].val); 60 return 0; 61 }
View Code

上一篇：[HDU2896]病毒侵袭（AC自动机）

下一篇：Monkey King（左偏树）

---

树状数组 离散化