网站正在建设中网页,郑州市中原区建设局网站,wordpress 文章分享,买了虚拟主机怎么建设网站正题
题目链接:https://www.luogu.com.cn/problem/CF702F 题目大意
有nnn个物品#xff0c;第iii个价格为cic_ici#xff0c;质量为qiq_iqi。
然后有mmm个询问#xff0c;假设一个人有viv_ivi块#xff0c;他每次会买他能买得起的qiq_iqi最大的#xff08;如果…正题
题目链接:https://www.luogu.com.cn/problem/CF702F 题目大意
有nnn个物品第iii个价格为cic_ici质量为qiq_iqi。
然后有mmm个询问假设一个人有viv_ivi块他每次会买他能买得起的qiq_iqi最大的如果相同就cic_ici最小的物品购买直到买不起为止一个物品只能买一次求他最后能买多少个物品。
1≤n,m≤2×105,1≤ci,qi,vi≤1091\leq n,m\leq 2\times 10^5,1\leq c_i,q_i,v_i\leq 10^91≤n,m≤2×105,1≤ci,qi,vi≤109 解题思路
考虑最暴力的做法我们可以把所有物品按照qiq_iqi从大到小排序然后对于每个人枚举所有物品如果买得起就买这样就是O(nm)O(nm)O(nm)的了。
考虑如何优化这个做法在线显然难搞我们考虑把所有人放在一起维护。
对于物品价格为ccc那么所有vi≥cv_i\geq cvi≥c的都有ansi1,vi−cans_i1,v_i-cansi1,vi−c。
也就是对于一个值域进行操作考虑到这个值域是动态的尝试用平衡树维护
那么考虑对于钱数为[0,c−1][0,c-1][0,c−1]的人不操作。
对于钱数为[c,2×c−1][c,2\times c-1][c,2×c−1]的人ansi1,vi−cans_i1,v_i-cansi1,vi−c并且vi−ccv_i-ccvi−cc。也就是说此时减去后范围都在[0,c−1][0,c-1][0,c−1]会和原来[0,c−1][0,c-1][0,c−1]范围内的人有重复。
对于钱数为[2×c,∞)[2\times c,\infty)[2×c,∞)的人ansi1,vi−cans_i1,v_i-cansi1,vi−c并且vi−c≥cv_i-c\geq cvi−c≥c也就是说这一部分整体往前移动ccc位之后不会和其它部分的人有交叉。那么这一部分的人我们可以打一个标记然后插回平衡树中。
那么现在问题是[c,2×c−1][c,2\times c-1][c,2×c−1]部分的人如何操作注意到此时有vi−c≤vi2v_i-c\leq \frac{v_i}{2}vi−c≤2vi也就是一个viv_ivi最多操作log\loglog次所以我们可以直接暴力把这一部分提出来然后一个一个插回去。
用FhqTreap\text{FhqTreap}FhqTreap很轻易实现以上功能
时间复杂度O(nlognlogv)O(n\log n\log v)O(nlognlogv) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N2e510;
int n,m,root;
struct node{int q,v;
}q[N];
struct FHQ_Treap{int cnt,siz[N],rnk[N],t[N][2];int w[N],ans[N],lazy1[N],lazy2[N];int NewNode(int val){cnt;w[cnt]val;siz[cnt]1;rnk[cnt]rand();return cnt;}void PushUp(int x){siz[x]siz[t[x][0]]siz[t[x][1]]1;return;}void PushDown(int x){for(int i0;i2;i){if(!t[x][i])continue;lazy1[t[x][i]]lazy1[x];lazy2[t[x][i]]lazy2[x];w[t[x][i]]lazy1[x];ans[t[x][i]]lazy2[x];}lazy1[x]lazy2[x]0;return;}void Split(int x,int y,int p,int k){if(!p){xy0;return;}PushDown(p);if(w[p]k)xp,Split(t[x][1],y,t[p][1],k);else yp,Split(x,t[y][0],t[p][0],k);PushUp(p);return;}int Merge(int x,int y){PushDown(x);PushDown(y);if(!x||!y)return x|y;if(rnk[x]rnk[y]){t[x][1]Merge(t[x][1],y);PushUp(x);return x;}else{t[y][0]Merge(x,t[y][0]);PushUp(y);return y;}}void Ins(int p,int root){int x,y;Split(x,y,root,w[p]);rootMerge(Merge(x,p),y);return;}void Deal(int p,int c,int root){if(!p)return;PushDown(p);Deal(t[p][0],c,root);Deal(t[p][1],c,root);t[p][0]t[p][1]0;ans[p];lazy2[p];w[p]-c;lazy1[p]-c;Ins(p,root);}void Solve(int c){int x,y,z;Split(x,y,root,c-1);Split(y,z,y,2*c-1);if(z){ans[z];lazy2[z];w[z]-c;lazy1[z]-c;}rootMerge(x,z);Deal(y,c,root);return;}void Fors(int p){if(!p)return;PushDown(p);Fors(t[p][0]);Fors(t[p][1]);return;}
}T;
bool cmp(node x,node y)
{return (x.qy.q)?(x.vy.v):(x.qy.q);}
int main()
{scanf(%d,n);for(int i1;in;i)scanf(%d%d,q[i].v,q[i].q);sort(q1,q1n,cmp);scanf(%d,m);for(int i1,x;im;i){scanf(%d,x);T.Ins(T.NewNode(x),root);}for(int i1;in;i)T.Solve(q[i].v);T.Fors(root);for(int i1;im;i)printf(%d ,T.ans[i]);return 0;
}
