响应式网站如何做,云网站后台,品牌推广案例,广东狮山网站建设正题 题目大意
给出一个有序集合AAA#xff0c;定义Al,rA_{l,r}Al,r表示集合内l∼rl\sim rl∼r这个范围内的数。
定义加法ABABAB表示两个集合中的所有元素(不去重)。
现在询问#xff0c;每次询问ki,pik_i,p_iki,pi然后给出kik_iki个区间[lj,rj][l_j,r_j][lj,rj…正题 题目大意
给出一个有序集合AAA定义Al,rA_{l,r}Al,r表示集合内l∼rl\sim rl∼r这个范围内的数。
定义加法ABABAB表示两个集合中的所有元素(不去重)。
现在询问每次询问ki,pik_i,p_iki,pi然后给出kik_iki个区间[lj,rj][l_j,r_j][lj,rj] 求∑j1kiAlj,rj\sum_{j1}^{k_i} A_{l_j,r_j}j1∑kiAlj,rj 这个集合中第pip_ipi小的数。 解题思路
因为k≤5k\leq 5k≤5所以我们可以考虑一般的主席树求区间第kkk小。
现在对于每个询问的lj,rjl_j,r_jlj,rj我们让kkk组下标同时在主席数上跑动。那么每次的数字个数即是kkk组下标计算出来的数字的和。然后往左或往右区间走动是让555组区间同时走动即可。 codecodecode
#includecstdio
#includealgorithm
#define MN 201000
using namespace std;
struct tnode{int w,l,r,ls,rs;
}t[MN5];
int n,m,x,y,k,a[MN],b[MN],root[MN],q,w,r[6],l[6],qnum,cnt;
int build(int l,int r)
{int kcnt;t[k].ll,t[k].rr;if (lr) return k;int mid(lr)1;t[k].lsbuild(l,mid);t[k].rsbuild(mid1,r);return k;
}
int addt(int k,int z)
{int nbcnt;t[nb]t[k];t[nb].w;if (t[k].lzt[k].rz) return nb;int mid(t[k].lt[k].r)1;if (zmid) t[nb].lsaddt(t[k].ls,z);else t[nb].rsaddt(t[k].rs,z);return nb;
}
int query(int k)
{if (t[r[1]].lt[r[1]].r) return t[r[1]].l;int num0;for(int i1;iqnum;i)numt[t[r[i]].ls].w-t[t[l[i]].ls].w;if(knum){for(int i1;iqnum;i)r[i]t[r[i]].ls,l[i]t[l[i]].ls;return query(k);}else{for(int i1;iqnum;i)r[i]t[r[i]].rs,l[i]t[l[i]].rs;return query(k-num);}
}
int main()
{scanf(%d%d,n,m);for (int i1;in;i)scanf(%d,a[i]),b[i]a[i];sort(b1,b1n);int qunique(b1,b1n)-b-1;root[0]build(1,q);for (int i1;in;i){int telower_bound(b1,b1q,a[i])-b;root[i]addt(root[i-1],te);}for (int i1;im;i){scanf(%d%d,qnum,k);for(int j1;jqnum;j)scanf(%d%d,l[j],r[j]),l[j]root[l[j]-1],r[j]root[r[j]];printf(%d\n,b[query(k)]);}
}
