苏州微网站建设公司哪家好,极验验证 wordpress,wordpress 列表页,树苗网站源码正题 题目大意
两个序列不降a,ba,ba,b#xff0c;每次可以修改或询问[l1,r1,l2,r2][l_1,r_1,l_2,r_2][l1,r1,l2,r2]要求输出将序列aaa的l1∼r1l_1\sim r_1l1∼r1和bbb的l2∼r2l_2\sim r_2l2∼r2部分合起来然后求中位数。 解题思路
我们考虑分治#xff0c;…正题 题目大意
两个序列不降a,ba,ba,b每次可以修改或询问[l1,r1,l2,r2][l_1,r_1,l_2,r_2][l1,r1,l2,r2]要求输出将序列aaa的l1∼r1l_1\sim r_1l1∼r1和bbb的l2∼r2l_2\sim r_2l2∼r2部分合起来然后求中位数。 解题思路
我们考虑分治我们取出两个区间l1k2−1∼r1l_1\frac{k}{2}-1\sim r_1l12k−1∼r1和l2k2−1∼r2l_2\frac{k}{2}-1\sim r2l22k−1∼r2然后我们可以判断 若amid1lt;bmid2a_{mid_1}lt;b_{mid_2}amid1bmid2我们就有mid11∼r1mid_11\sim r_1mid11∼r1和mid2∼r2mid_2\sim r_2mid2∼r2都比l1∼mid1l_1 \sim mid_1l1∼mid1大然后因为这些区间的大小大于等于kkk所以l1∼mid1l_1\sim mid_1l1∼mid1是不包含答案的所以我们把这个区间去掉。
然后就是这样不停减少就过了 codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N510000;
int n,m,a[N],b[N];
int calc(int *a,int w,int l,int r)
{return (lower_bound(al,a1r,w)-a)-l;}
int solve(int l1,int r1,int l2,int r2,int k)
{if(r2l2) return a[l1k-1];if(r1l1) return b[l2k-1];if(k1) return min(a[l1],b[l2]);int m1min(l1k/2-1,r1),m2min(l2k/2-1,r2);if(a[m1]b[m2]) return solve(m11,r1,l2,r2,k-(m1-l11));else return solve(l1,r1,m21,r2,k-(m2-l21));
}
int main()
{freopen(median.in,r,stdin);freopen(median.out,w,stdout);scanf(%d%d,n,m);for(int i1;in;i)scanf(%d,a[i]);for(int i1;in;i)scanf(%d,b[i]);while(m--){int opt,x,y,l,r;scanf(%d%d%d%d,opt,x,y,l);if(opt1){if(!x) a[y]l;else b[y]l; }else {scanf(%d,r);printf(%d\n,solve(x,y,l,r,((r-l1)(y-x1))/21));}}
}
