南京网站制作公司南京乐识专心,杭州h5建站在线咨询,厦门市住房和城乡建设局网站,外贸公司没网站【题目描述】
HDU - 6621 K-th Closest Distance
【题目分析】 因为看到第kkk大的要求#xff0c;刚开始的时候一直都在想怎么运用第kkk大来解决问题#xff0c;但是后来看其他人的博客才发现并不需要用第k大#xff0c;但是主席树维护权值线段树还是需要的#xff0c;这…【题目描述】
HDU - 6621 K-th Closest Distance
【题目分析】 因为看到第kkk大的要求刚开始的时候一直都在想怎么运用第kkk大来解决问题但是后来看其他人的博客才发现并不需要用第k大但是主席树维护权值线段树还是需要的这样可以方便的求出某一区间内数的个数。题目要求的∣q−ai∣|q-ai|∣q−ai∣中第kkk大的我们可以尝试使用二分只不过需要进行转化。 我们对绝对值进行二分左区间为0右区间为最大的数值106对于每一个midmidmid我们查找∣q−ai∣lt;mid|q-ai|lt;mid∣q−ai∣mid的数字有没有kkk个有kkk个就减少rmid−1rmid-1rmid−1否则就增加lmid1lmid1lmid1 现在问题的关键在于如何找∣q−ai∣lt;mid|q-ai|lt;mid∣q−ai∣mid的数字有没有kkk个我们可以对这个式子进行简单的变形去点绝对值就能得到ai的范围为q−mid到qmidq-mid到 qmidq−mid到qmid即查找符合q−mid到qmidq-mid到qmidq−mid到qmid的ai有没有kkk个用一个记录权值的主席树进行维护就能很简单的得到。 【AC代码】
#includecstdio
#includecstring
#includecstdlib
#includealgorithm
#includeiostream
#includecmath
#includeclimits
#includequeue
#includevector
#includeset
#includemap
using namespace std;typedef long long ll;
const int MAXN1e510;
const int INF1e6;
struct node
{int ls,rs;int sum;
}tree[MAXN*40];
int root[MAXN];
int tot;
int n,m;
int ans;void Insert(int k,int l,int r,int x)
{tot; tree[tot]tree[k]; ktot;tree[k].sum;if(lr){return;}int mid(lr)1;if(xmid) Insert(tree[k].ls,l,mid,x);else Insert(tree[k].rs,mid1,r,x);
}int Query(int now,int pre,int l,int r,int L,int R)
{if(lL rR){return tree[now].sum-tree[pre].sum;}int mid(lr)1;int ret0;if(Lmid) retQuery(tree[now].ls,tree[pre].ls,l,mid,L,R);if(Rmid) retQuery(tree[now].rs,tree[pre].rs,mid1,r,L,R);return ret;
}int Search(int L,int R,int p,int k)
{int l0,rINF,mid,ret;while(lr){mid(lr)1;if(Query(root[R],root[L-1],1,INF,max(p-mid,1),min(pmid,INF))k){retmid;rmid-1;}else{lmid1;}}return ret;
}int main()
{int T,x,L,R,p,k;scanf(%d,T);while(T--){totroot[0]tree[0].sumtree[0].rstree[0].ls0;scanf(%d%d,n,m);for(int i1;in;i){scanf(%d,x);root[i]root[i-1];Insert(root[i],1,INF,x);}ans0;for(int i0;im;i){scanf(%d%d%d%d,L,R,p,k);LL^ans; RR^ans; pp^ans; kk^ans;//if(LR) swap(L,R);ansSearch(L,R,p,k);//这里一定要记得对ans进行赋值忘记赋值找了好久。多组数据一定要手动检查一下很容易出错printf(%d\n,ans);}}return 0;
}
