培训网站完整页面,济南建设网站企业报价,不拦截网站的浏览器,成都房屋装修设计公司正题
题目链接:https://www.luogu.com.cn/problem/P2839 题目大意 nnn个数字#xff0c;mmm次询问给出(a,b,c,d)(a,b,c,d)(a,b,c,d)表示左端点在[a,b][a,b][a,b]中#xff0c;右端点在[c,d][c,d][c,d]的子区间中中位数最大的值。 解题思路
显然我们需要二分一下答案midmidm…正题
题目链接:https://www.luogu.com.cn/problem/P2839 题目大意
nnn个数字mmm次询问给出(a,b,c,d)(a,b,c,d)(a,b,c,d)表示左端点在[a,b][a,b][a,b]中右端点在[c,d][c,d][c,d]的子区间中中位数最大的值。 解题思路
显然我们需要二分一下答案midmidmid然后我们要选择一个满足条件的子区间使得区间≥mid\geq mid≥mid的个数减去midmidmid的个数最大。
换一种主席树的方式我们里面是一个按照区间的线段树外面是按照值域分的。然后维护区间最大前缀和和最大后缀和即可。
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includevector
using namespace std;
const int N21000,MN4;
struct node{int pre,suf,num;
};
int n,m,tot,a[N],b[N],q[4],rt[N];
int ls[M],rs[M],pre[M],suf[M],num[M];
vectorint v[N];
void PushUp(int x,int L,int R){int mid(LR)1;if(!ls[x])ls[x]tot,pre[tot]suf[tot]-1,num[tot]-(mid-L1);if(!rs[x])rs[x]tot,pre[tot]suf[tot]-1,num[tot]-(R-mid);pre[x]max(pre[ls[x]],num[ls[x]]pre[rs[x]]);suf[x]max(suf[rs[x]],num[rs[x]]suf[ls[x]]);num[x]num[ls[x]]num[rs[x]];return;
}
int Change(int x,int L,int R,int pos){int nowtot;if(LR){pre[now]suf[now]num[now]1;return now;}int mid(LR)1;if(posmid)ls[now]Change(ls[x],L,mid,pos),rs[now]rs[x];else rs[now]Change(rs[x],mid1,R,pos),ls[now]ls[x];PushUp(now,L,R);return now;
}
node Ask(int x,int L,int R,int l,int r){if(lr||!x)return (node){-1,-1,-(r-l1)};int mid(LR)1;if(LlRr)return (node){pre[x],suf[x],num[x]};if(rmid)return Ask(ls[x],L,mid,l,r);if(lmid)return Ask(rs[x],mid1,R,l,r);node laAsk(ls[x],L,mid,l,mid);node raAsk(rs[x],mid1,R,mid1,r);return (node){max(la.pre,la.numra.pre),max(ra.suf,ra.numla.suf),la.numra.num};
}
bool check(int x,int a,int b,int c,int d){node LAsk(rt[x],1,n,a,b);node MAsk(rt[x],1,n,b1,c-1);node RAsk(rt[x],1,n,c,d);return (L.sufM.numR.pre)0;
}
int main()
{scanf(%d,n);for(int i1;in;i)scanf(%d,a[i]),b[i]a[i];sort(b1,b1n);int cntunique(b1,b1n)-b-1;for(int i1;in;i){a[i]lower_bound(b1,b1cnt,a[i])-b;v[a[i]].push_back(i);}for(int icnt;i1;i--){rt[i]Change(rt[i1],1,n,v[i][0]);for(int j1;jv[i].size();j)rt[i]Change(rt[i],1,n,v[i][j]);}scanf(%d,m);int last0;for(int i1;im;i){scanf(%d%d%d%d,q[1],q[2],q[3],q[0]);q[1](q[1]last)%n1;q[2](q[2]last)%n1;q[3](q[3]last)%n1;q[0](q[0]last)%n1;sort(q,q4);int l1,rcnt;while(lr){int mid(lr)1;if(check(mid,q[0],q[1],q[2],q[3]))lmid1;else rmid-1;}printf(%d\n,lastb[r]);}return 0;
}
