正題

題目鏈接:https://www.luogu.com.cn/problem/CF702F

---

題目大意

有$n$個物品，第$i$個價格為$c_i$，質量為$q_i$。

然后有$m$個詢問，假設一個人有$v_i$塊，他每次會買他能買得起的$q_i$最大的（如果相同就$c_i$最小的）物品購買，直到買不起為止，一個物品只能買一次，求他最后能買多少個物品。

$1\le n,m\le 2\times 10^5,1\le c_i,q_i,v_i\le 10^9$

---

解題思路

考慮最暴力的做法，我們可以把所有物品按照$q_i$從大到小排序，然后對于每個人枚舉所有物品，如果買得起就買，這樣就是$O(nm)$的了。

考慮如何優化這個做法，在線顯然難搞，我們考慮把所有人放在一起維護。

對于物品價格為$c$，那么所有$v_i\ge c$的都有$an{s}_i+1,v_i?c$。

也就是對于一個值域進行操作，考慮到這個值域是動態的，嘗試用平衡樹維護

那么考慮對于錢數為$[0,c?1]$的人不操作。

對于錢數為$[c,2\times c?1]$的人，$an{s}_i+1,v_i?c$，并且$v_i?c<c$。也就是說此時減去后范圍都在$[0,c?1]$，會和原來$[0,c?1]$范圍內的人有重復。

對于錢數為$[2\times c,\infty )$的人，$an{s}_i+1,v_i?c$，并且$v_i?c\ge c$，也就是說這一部分整體往前移動$c$位之后不會和其它部分的人有交叉。那么這一部分的人我們可以打一個標記然后插回平衡樹中。

那么現在問題是$[c,2\times c?1]$部分的人如何操作，注意到此時有$v_i?c\le \frac{v_i}{2}$，也就是一個$v_i$最多操作$\log$次，所以我們可以直接暴力把這一部分提出來然后一個一個插回去。

用$\text{FhqTreap}$很輕易實現以上功能

時間復雜度：$O(n\log n\log v)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2e5+10; 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 i=0;i<2;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){x=y=0;return;}PushDown(p);if(w[p]<=k)x=p,Split(t[x][1],y,t[p][1],k);else y=p,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]);root=Merge(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;}root=Merge(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.q==y.q)?(x.v<y.v):(x.q>y.q);} int main() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d%d",&q[i].v,&q[i].q);sort(q+1,q+1+n,cmp);scanf("%d",&m);for(int i=1,x;i<=m;i++){scanf("%d",&x);T.Ins(T.NewNode(x),root);}for(int i=1;i<=n;i++)T.Solve(q[i].v);T.Fors(root);for(int i=1;i<=m;i++)printf("%d ",T.ans[i]);return 0; }

總結

以上是生活随笔為你收集整理的CF702F-T-Shirts【FhqTreap】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。