学校网站设计的目的,南阳做网站多少电话,oa办公软件怎么使用,织梦dedecms网站内容页题目链接#xff1a; Codeforces702F 题目大意#xff1a;有$n$种T恤#xff0c;每种有一个价格$c_{i}$和品质$q_{i}$且每种数量无限。现在有$m$个人#xff0c;第$i$个人有$v_{i}$元#xff0c;每人每次会买他能买得起的品质最高的一件T恤(当两件T恤品质相同时优先买价格…题目链接 Codeforces702F 题目大意有$n$种T恤每种有一个价格$c_{i}$和品质$q_{i}$且每种数量无限。现在有$m$个人第$i$个人有$v_{i}$元每人每次会买他能买得起的品质最高的一件T恤(当两件T恤品质相同时优先买价格低的)每人只能买一件每种T恤。求最后每个人买的T恤件数。 暴力的方法是将T恤品质从大到小排序对于每个人从第一种T恤(排序后的第一种)开始模拟每件T恤能买就买不能买就跳过。 发现暴力的方法是对于每个人决策每件T恤我们可以对于每件T恤来决策哪些人能买用非旋转$treap$来维护每个人还剩的钱数。 那么每次就是将权值大于$q_{i}$的人的权值都减少$q_{i}$并把答案都增加$1$。 对于区间修改我们直接打标记即可但问题是无法将被修改的部分和没被修改的部分合并。 因为非旋转$treap$的合并要求一棵树的最大权值小于另一棵树的最小权值而被修改部分在权值减小之后会有一部分的权值比未被修改部分最大权值小。 那么我们就把这部分暴力插入到未被修改的那棵树中剩下被修改的那部分直接合并。 假设被暴力插入的权值为$x$那么$x-q_{i}q_{i},xq_{i}$也就是说$2q_{i}x,q_{i}\frac{x}{2}$即每次暴力插入的数权值减半所以每个数最多暴力插入$log_{v_{i}}$次。 总时间复杂度是$O((n\sum log_{v_{i}})log_{m})$。 #includeset
#includemap
#includequeue
#includestack
#includecmath
#includecstdio
#includebitset
#includevector
#includecstring
#includeiostream
#includealgorithm
#define ll long long
using namespace std;
int ls[200010];
int rs[200010];
int val[200010];
int num[200010];
int r[200010];
int sum[200010];
int tag[200010];
int res[200010];
int root;
int n,m,x;
int cnt;
int a,b,c,d;
int L,R;
struct lty
{int c,v;
}q[200010];
queueintQ;
inline int build(int v)
{int rtcnt;r[rt]rand();val[rt]v;return rt;
}
inline void add(int rt,int x,int y)
{tag[rt]x;val[rt]x;sum[rt]y;res[rt]y;
}
inline void pushdown(int rt)
{if(tag[rt]sum[rt]){add(ls[rt],tag[rt],sum[rt]);add(rs[rt],tag[rt],sum[rt]);tag[rt]sum[rt]0;}
}
inline int merge(int x,int y)
{if(!x||!y){return xy;}pushdown(x);pushdown(y);if(r[x]r[y]){rs[x]merge(rs[x],y);return x;}else{ls[y]merge(x,ls[y]);return y;}
}
inline void split(int rt,int x,int y,int k)
{if(!rt){xy0;return ;}pushdown(rt);if(val[rt]k){yrt;split(ls[rt],x,ls[y],k);}else{xrt;split(rs[rt],rs[x],y,k);}
}
inline bool cmp(lty a,lty b)
{return a.vb.v?a.cb.c:a.vb.v;
}
inline void dfs(int rt)
{pushdown(rt);if(ls[rt]){dfs(ls[rt]);}if(rs[rt]){dfs(rs[rt]);}
}
int main()
{scanf(%d,n);for(int i1;in;i){scanf(%d%d,q[i].c,q[i].v);}sort(q1,q1n,cmp);scanf(%d,m);for(int i1;im;i){scanf(%d,x);split(root,a,b,x);rootmerge(merge(a,build(x)),b);}for(int i1;in;i){split(root,a,b,q[i].c);split(b,b,c,2*q[i].c);add(b,-q[i].c,1);add(c,-q[i].c,1);Q.push(b);while(!Q.empty()){int nowQ.front();Q.pop();pushdown(now);if(ls[now]){Q.push(ls[now]);}if(rs[now]){Q.push(rs[now]);}ls[now]rs[now]0;split(a,a,d,val[now]);amerge(merge(a,now),d);}rootmerge(a,c);}dfs(root);for(int i1;im;i){printf(%d ,res[i]);}
} 转载于:https://www.cnblogs.com/Khada-Jhin/p/10697330.html
