泰兴做网站,wordpress 获得备案号,网址大全浏览器app,互联网编程培训我们开门见山#xff0c;讲讲一道sb题#xff1a; 给你一个数组#xff0c;查这个数组的第x大元素。 排序#xff1f;可以 二分#xff1f;怎么做啊#xff1f; 二分出一个mid#xff0c;判断这个数组中有多少个数小于等于mid#xff0c;如果个数大于等于x#xff0c;… 我们开门见山讲讲一道sb题 给你一个数组查这个数组的第x大元素。 排序可以 二分怎么做啊 二分出一个mid判断这个数组中有多少个数小于等于mid如果个数大于等于x就递归到[l,mid]区间否则是[mid1,r]区间这样递归下去就能得到结果。 怎么计算小于等于mid的个数 for一遍原数组其实只要存储数组中值在[l,r]中的数然后计算就好而对于[1,l-1]可以预先存储。 怎么计算树状数组范围太大就离散化。 这样很麻烦吧排序更好吧 但是当我给你多个询问时你就不会这么觉得了。 回顾刚才的过程我们做上图的类比。 把询问看成球答案的区间就是这个矩形每一次我们将上一层的球判断它会掉到下层的哪一块中掉到底层就是获得了答案。 刚刚的过程就是球只有1个的情况。 球有多个时就是整体二分 就是对于当前的mid对每一个询问都计算答案是大了还是小了然后决定分配到下一层的哪边。 要注意保证时间复杂度哦 一道例题HDU 5412。 查询区间K小要支持单点修改。 看代码 1 #includecstdio2 int n,q,a[100001],sum[300001],ans[300001],que1[300001],que2[300001],bit[300001];3 int I[300001],type[300001],ql[300001],qr[300001],k[300001],cnt;4 inline void ins(int t,int l,int r,int x){type[cnt]t,ql[cnt]l,qr[cnt]r,k[cnt]x,I[cnt]cnt;}5 inline void Ins(int i,int x){for(;in;bit[i]x,ii-i);}6 inline int Qur(int i){int Sum0;for(;i;Sumbit[i],i-i-i);return Sum;}7 void divide(int l,int r,int low,int upp){8 if(lr) return;9 if(lowupp) {for(int il;ir;i) if(type[I[i]]3) ans[I[i]]low; return;}
10 int midlowupp1,cl0,cr0;
11 for(int i_l,i;i_r;i_){
12 iI[i_];
13 if(type[i]1) {if(k[i]mid) Ins(ql[i],1), que1[cl]i; else que2[cr]i;}
14 if(type[i]2) {if(k[i]mid) Ins(ql[i],-1), que1[cl]i; else que2[cr]i;}
15 if(type[i]3){
16 int tmpQur(qr[i])-Qur(ql[i]-1);
17 if(k[i]sum[i]tmp) que1[cl]i;
18 else que2[cr]i, sum[i]tmp;
19 }
20 }
21 for(int i_l,i;i_r;i_){
22 iI[i_];
23 if(type[i]1) if(k[i]mid) Ins(ql[i],-1);
24 if(type[i]2) if(k[i]mid) Ins(ql[i],1);
25 }
26 for(int i1;icl;i) I[li-1]que1[i];
27 for(int i1;icr;i) I[lcli-1]que2[i];
28 divide(l,lcl-1,low,mid); divide(lcl,r,mid1,upp);
29 }
30 int main(){
31 scanf(%d,n);
32 for(int i1;in;i) scanf(%d,ai), ins(1,i,i,a[i]);
33 scanf(%d,q);
34 for(int i1,t,x,y,z;iq;i){
35 scanf(%d,t);
36 if(t1) scanf(%d%d,x,y), ins(2,x,x,a[x]), ins(1,x,x,y), a[x]y;
37 else scanf(%d%d%d,x,y,z), ins(3,x,y,z);
38 }
39 divide(1,cnt,1,1000000000);
40 for(int i1;icnt;i) if(ans[i]) printf(%d\n,ans[i]);
41 return 0;
42 } View Code 一道例题洛谷 P3332。 查询区间K大要支持区间加入。 看代码 1 #include cstdio2 3 typedef long long LL;4 const int MN 50005;5 6 int N, Q;7 8 int opt[MN], L[MN], R[MN]; LL V[MN];9 int P[MN];
10 int s1[MN], s2[MN], t1, t2;
11
12 LL Sum[MN];
13 int Ans[MN];
14
15 LL b1[MN], b2[MN];
16 inline void Add(LL *b, int i, LL x) { for(; i N; i i -i) b[i] x; }
17 inline LL Qur(LL *b, int i) { LL A 0; for(; i; i - i -i) A b[i]; return A; }
18 inline void Add(int l, int r, LL x) {
19 r;
20 Add(b1, l, x), Add(b2, l, (l - 1) * x);
21 Add(b1, r, -x), Add(b2, r, -(r - 1) * x);
22 }
23 inline LL Qur(int l, int r) {
24 --l;
25 return r * Qur(b1, r) - Qur(b2, r) - l * Qur(b1, l) Qur(b2, l);
26 }
27
28 void Solve(int l, int r, int lb, int rb) {
29 if (lb rb) {
30 for (int i l; i r; i)
31 if (opt[P[i]] 2)
32 Ans[P[i]] lb;
33 return ;
34 }
35 int mid lb rb 1;
36 t1 t2 0;
37 for (int i l; i r; i) {
38 if (opt[P[i]] 1) {
39 if (V[P[i]] mid)
40 s1[t1] P[i];
41 else {
42 Add(L[P[i]], R[P[i]], 1);
43 s2[t2] P[i];
44 }
45 }
46 else {
47 LL num Sum[P[i]] Qur(L[P[i]], R[P[i]]);
48 if (num V[P[i]])
49 s2[t2] P[i];
50 else {
51 Sum[P[i]] num;
52 s1[t1] P[i];
53 }
54 }
55 }
56 for (int i l; i r; i) {
57 if (opt[P[i]] 2) continue;
58 if (V[P[i]] mid)
59 Add(L[P[i]], R[P[i]], -1);
60 }
61 int pos l;
62 for (int i 1; i t1; i)
63 P[pos] s1[i];
64 for (int i 1; i t2; i)
65 P[pos] s2[i];
66 int M l t1 - 1;
67 Solve(l, M, lb, mid);
68 Solve(M 1, r, mid 1, rb);
69 }
70
71 int main() {
72 scanf(%d%d, N, Q);
73 for (int i 1; i Q; i) {
74 scanf(%d%d%d%lld, opt i, L i, R i, V i);
75 P[i] i;
76 }
77 Solve(1, Q, -N, N);
78 for (int i 1; i Q; i) {
79 if (opt[i] 1) continue;
80 printf(%d\n, Ans[i]);
81 }
82 return 0;
83 } View Code 转载于:https://www.cnblogs.com/PinkRabbit/p/8039083.html
