建网站的地址,猎头公司前十名,wordpress5.0中文,wordpress登录地址无法登录HDU - 6278 Just hhh-index 【题目描述】 【题目分析】 题目要求在区间[l,r][l,r][l,r]内大于h的数不少于h个#xff0c;对于这种最大化问题#xff0c;我们应该想到二分。 最小情况显然是1.最大情况显然是r−l1r-l1r−l1#xff0c;对于一个hhh#xff0c;我们如何判断能…HDU - 6278 Just hhh-index 【题目描述】 【题目分析】 题目要求在区间[l,r][l,r][l,r]内大于h的数不少于h个对于这种最大化问题我们应该想到二分。 最小情况显然是1.最大情况显然是r−l1r-l1r−l1对于一个hhh我们如何判断能否满足条件呢 我们可以用主席树方便的求出区间第h大如果区间第h大大于等于h那么就能满足条件 比较伤心的是我虽然一开始就想到了正确的思路但是区间第k大却写错了。因为之前一直写的是将所有数据都放在结构体中所以一个赋值就讲所有数据复制了但是这次我想写简单一点就将计数的数组放在了外面然后在创建新节点的时候却忘记了复制导致疯狂wa还一直找不到为什么啊啊啊最终还是调试找到了 【AC代码】没有借鉴其他人的嘿嘿
#includecstdio
#includecstring
#includealgorithm
#includequeue
#includevector
#includeset
#includeclimits
#includestring
#includecmath
#includecstdlibusing namespace std;const int MAXN100005;
int a[MAXN];
int n,m;
struct node
{int ls,rs;
}tree[MAXN*40];
int root[MAXN*40];
int cnt[MAXN*40];
int top;void Insert(int k,int x,int l,int r)
{tree[top]tree[k]; cnt[top]cnt[k];cnt[top]; ktop;//printf(l%d r%d x%d cnt[%d]%d\n,l,r,x,k,cnt[k]);if(lr) return;int mid(lr)1;if(xmid) Insert(tree[k].ls,x,l,mid);else Insert(tree[k].rs,x,mid1,r);
}int query(int i,int j,int k,int l,int r)
{if(lr) return l;int tmpcnt[tree[j].rs]-cnt[tree[i].rs];int mid(lr)1;if(ktmp) return query(tree[i].rs,tree[j].rs,k,mid1,r);else return query(tree[i].ls,tree[j].ls,k-tmp,l,mid);
}int main()
{int u,v,l,r,mid,ans;while(~scanf(%d%d,n,m)){memset(cnt,0,sizeof(cnt));memset(root,0,sizeof(root));memset(tree,0,sizeof(tree));top0;for(int i1;in;i){scanf(%d,a[i]);root[i]root[i-1];Insert(root[i],a[i],1,n);}/*for(int i1;in;i){printf(%d ,query(root[0],root[n],i,1,n));}*/for(int i0;im;i){scanf(%d%d,u,v);l1; rv-u1;while(lr){mid(lr)1;if(query(root[u-1],root[v],mid,1,n)mid){ansmid;lmid1;}else{rmid-1;}}printf(%d\n,ans);}}return 0;
}
