张掖网站建设公司,代理网页 在线,电商具体是做什么的上班,海南专业网站建设定制【题目描述】 HDU - 5919 Sequence II 【题目分析】 题目给定一个数组#xff0c;每次查询一个区间#xff0c;找出区间内不同数字的个数x#xff0c;然后输出按出现顺序第x/2向上取整个数字的位置。
按照要求#xff0c;我们首先需要能够找出给定区间不同的数字个数。 首…【题目描述】 HDU - 5919 Sequence II 【题目分析】 题目给定一个数组每次查询一个区间找出区间内不同数字的个数x然后输出按出现顺序第x/2向上取整个数字的位置。
按照要求我们首先需要能够找出给定区间不同的数字个数。 首先我们分析一个简单一些的问题对于右端点固定的区间如何计算不同左区间内不同数字的个数。 我们不妨用一个数组记录cntcntcnt哪些位置出现了一个不同的数字用sumsumsum数组进行维护cnt[1..l]cnt[1..l]cnt[1..l]的和可以用线段树或者树状数组那么对于区间[l,r][l,r][l,r]内不同数字的个数就是sum[r]−sum[l−1]sum[r]-sum[l-1]sum[r]−sum[l−1]。 在从前往后进行添加的过程中如果该数字在前面已经出现就将前面的标记消除在后面的位置进行标记也就是说尽可能将标记后放。例如对于数组1,2,2,3,5,11,2,2,3,5,11,2,2,3,5,1维护以后的cntcntcnt数组就是0,0,1,1,1,10,0,1,1,1,10,0,1,1,1,1这样做的原因是我们假设的是右端点固定对于重复的元素在后面如果出现过前面就没有必要标记。 如果询问是离线的我们大可以先将询问保存下来然后从前往后加入数据的过程中不断将对应的询问答案保存对应是指右端点相同最后输出就可以了。 可是这个问题是强制在线的所以我们必须使用主席树进行可持久化。可是这种可持久化和以前的主席树运用不同因为在添加的过程中会将前面的标记消除所以不同根节点的主席树不在拥有可以互相加减的能力加减的结果不再有意义。然而在我们这个问题里面我们是不需要进行加减的。不同于求区间第K大的时候我们的主席树维护的是值区间即值在区间内的个数这里根节点的1..n1..n1..n指的是数据范围aiaiai的最大值。在这里我们的根节点的1..n1..n1..n的nnn指的是数据的个数就是题目中的nnn标记的是该位置上出现了一个之前没有出现过的数字。 因此对于每次询问我们访问的版本里保存的就是实际的数组直接计数就可以。而区间第K大就需要减去之前的版本才是该区间内的数的个数。题目要求的是数据第一次出现的位置可是按照上面的想法进行建树的话我们保存的是当前区间[1,i][1,i][1,i]数据最后一次出现的位置。很自然我们应该进行逆序建树这样的话我们保存的就是[i,n][i,n][i,n]区间内数据第一次出现的位置对于需要查询的区间[l,r][l,r][l,r]我们访问第lll个版本的主席树就满足题目要求啦。 求出数字的个数后我们再除以2向上取整就是题目要求的k然后在找出对应的位置这里类似区间第K大 【参考文献】 大佬博客1 大佬博客2 【AC代码】
#includecstdio
#includecstring
#includealgorithm
#includequeue
#includevector
#includeset
#includeclimits
#includestring
#includecmath
#includecstdlibusing namespace std;const int MAXN200005;
int a[MAXN];
int n,m;
struct node
{int ls,rs,cnt;
}tree[MAXN*40];
int root[MAXN*40];
int b[MAXN];
int tot;void Insert(int now,int pre,int x,int l,int r,int add)
{int tmpnow; nowtot;tree[now]tmp?tree[tmp]:tree[pre];tree[now].cntadd;if(lr) return;int mid(lr)1;if(xmid) Insert(tree[now].ls,tree[pre].ls,x,l,mid,add);else Insert(tree[now].rs,tree[pre].rs,x,mid1,r,add);
}int GetSum(int k,int l,int r,int L,int R)
{if(lL rR) return tree[k].cnt;int ret0; int mid(lr)1;if(Lmid) retGetSum(tree[k].ls,l,mid,L,R);if(Rmid) retGetSum(tree[k].rs,mid1,r,L,R);return ret;
}int query(int k,int l,int r,int x)
{if(lr) return l;int mid(lr)1;int tmptree[tree[k].ls].cnt;if(xtmp) query(tree[k].ls,l,mid,x);else query(tree[k].rs,mid1,r,x-tmp);
}int main()
{int T,ans,l,r,tmp,sum;scanf(%d,T);for(int Case1;CaseT;Case){scanf(%d%d,n,m);memset(tree,0,sizeof(tree));memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(root,0,sizeof(root));tot0;for(int i1;in;i){scanf(%d,a[i]);}for(int in;i0;i--){if(b[a[i]]) Insert(root[i],root[i1],b[a[i]],1,n,-1);Insert(root[i],root[i1],i,1,n,1);b[a[i]]i;}ans0;printf(Case #%d:,Case);//测试 //printf(\n);for(int i0;im;i){scanf(%d%d,l,r);l(lans)%n1; r(rans)%n1;if(lr) tmpl,lr,rtmp;//printf(test: l%d r%d\n,l,r);sumGetSum(root[l],1,n,l,r);//printf(test: sum%d\n,sum);sum(sum1)/2;//printf(test: sum%d\n,sum);ansquery(root[l],1,n,sum);printf( %d,ans);}printf(\n);}return 0;
}
