当前位置:网站首页>UOJ#749-[UNR #6]稳健型选手【贪心,分治,主席树】
UOJ#749-[UNR #6]稳健型选手【贪心,分治,主席树】
2022-08-10 23:38:00 【QuantAsk】
正题
题目链接:https://uoj.ac/problem/749
题目大意
如果有序列 a a a,你每次取走一个数字后然后这个序列最前面的数字会被别人取走,直到序列为空。此时 f ( a ) f(a) f(a)表示你最大能取走的权值和。
给出一个长度为 n n n的序列 a a a, q q q次询问区间 [ l , r ] [l,r] [l,r],求 f ( a l ∼ r ) f(a_{l\sim r}) f(al∼r)。
1 ≤ n , q ≤ 2 × 1 0 5 , 1 ≤ a i ≤ 1 0 9 1\leq n,q\leq 2\times 10^5,1\leq a_i\leq 10^9 1≤n,q≤2×105,1≤ai≤109
解题思路
考虑一下最优的取法,我们的限制其实相当于前 2 i − 1 2i-1 2i−1个数之中不能取走超过 i i i个数。
一个暴力的贪心想法是不停往前走,用一个堆维护现在取了的数,走到不是 2 i − 1 2i-1 2i−1时我们考虑是否拿这个 a i a_i ai替代堆里最小的数,走到 2 i − 1 2i-1 2i−1时直接丢进堆里就行了。
或者反过来更简单,走到一个数就丢进堆里,遇到 2 i − 1 2i-1 2i−1时直接取堆中最大的数就好了。
我们现在能处理左或右端点固定的所有答案了,我们考虑分治,问题在于怎么去合并两个区间的答案。
为了防止大量的分类讨论,对于长度为奇数的区间询问,我们可以考虑去掉区间的末尾,因为这个位置肯定会取到。
然后我们考虑怎么合并区间,显然是前面一些选了的数字变成不选,后面一些不选的数字变成选了,显然是前面拿小的,后面拿大的。
我们考虑在分治的时候对于区间 [ L , m i d , R ] [L,mid,R] [L,mid,R],对于 [ L , m i d ] [L,mid] [L,mid]部分,我们用主席树维护选了的数字,对于 [ m i d + 1 , R ] [mid+1,R] [mid+1,R]部分,我们用主席树维护没选的数字,然后对于一个询问,二分一个 k k k,然后左边的取出前 k k k小,右边的取出前 k k k大进行比较即可。
时间复杂度: O ( n log 2 n ) O(n\log^2 n) O(nlog2n)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
const ll N=2e5+10,M=N<<5;
ll n,m,cnt,a[N],b[N],l[N],r[N],ans[N],s[N],rt[N];
priority_queue<ll> q;
struct SegTree{
ll cnt,w[M],c[M],ls[M],rs[M];
ll Change(ll x,ll L,ll R,ll pos,ll val){
ll p=++cnt;w[p]=w[x]+val;c[p]=c[x]+val*b[pos];
if(L==R)return p;ll mid=(L+R)>>1;
if(pos<=mid)ls[p]=Change(ls[x],L,mid,pos,val),rs[p]=rs[x];
else rs[p]=Change(rs[x],mid+1,R,pos,val),ls[p]=ls[x];
return p;
}
ll Find(ll x,ll L,ll R,ll k){
if(L==R)return L;ll mid=(L+R)>>1;
if(w[ls[x]]>=k)return Find(ls[x],L,mid,k);
return Find(rs[x],mid+1,R,k-w[ls[x]]);
}
ll Ask(ll x,ll L,ll R,ll k){
if(!k)return 0;
if(L==R)return b[L]*k;ll mid=(L+R)>>1;
if(w[ls[x]]>=k)return Ask(ls[x],L,mid,k);
return Ask(rs[x],mid+1,R,k-w[ls[x]])+c[ls[x]];
}
}T;
bool cmp(ll x,ll y){
return l[x]<l[y];}
void solve(ll L,ll R,vector<ll> &now){
if(L==R)return;
ll mid=(L+R)>>1;
vector<ll> pl,pr,p;
for(ll i=0;i<now.size();i++)
if(l[now[i]]<=mid&&r[now[i]]>mid)p.push_back(now[i]);
else if(l[now[i]]<=mid)pl.push_back(now[i]);
else pr.push_back(now[i]);
solve(L,mid,pl);solve(mid+1,R,pr);
if(!p.size())return;
for(ll g=0;g<2;g++){
T.cnt=rt[mid]=s[mid]=0;
for(ll i=mid+1;i<=R;i++){
if(((i-mid)&1)==g)q.push(-a[i]),s[i]=s[i-1]+b[a[i]],rt[i]=rt[i-1];
else{
if(q.size()&&a[i]>-q.top()){
s[i]=s[i-1]-b[-q.top()]+b[a[i]];
rt[i]=T.Change(rt[i-1],1,cnt,-q.top(),1);
q.pop();q.push(-a[i]);
}
else rt[i]=T.Change(rt[i-1],1,cnt,a[i],1),s[i]=s[i-1];
}
}
while(!q.empty())q.pop();
for(ll i=mid;i>=L;i--){
q.push(a[i]);
if(((mid-i)&1)==g){
rt[i]=T.Change((i==mid)?0:rt[i+1],1,cnt,q.top(),1);
s[i]=((i!=mid)?s[i+1]:0)+b[q.top()];q.pop();
}
else if(i!=mid)rt[i]=rt[i+1],s[i]=s[i+1];
}
while(!q.empty())q.pop();
for(ll i=0;i<p.size();i++){
if(((mid-l[p[i]])&1)!=g)continue;
ll X=T.w[rt[l[p[i]]]],Y=T.w[rt[r[p[i]]]];
ll _l=1,_r=min(X,Y);
if(p[i]==2)
i++,i--;
while(_l<=_r){
ll _mid=(_l+_r)>>1;
if(T.Find(rt[l[p[i]]],1,cnt,_mid)<T.Find(rt[r[p[i]]],1,cnt,Y-_mid+1))
_l=_mid+1;
else _r=_mid-1;
}
ans[p[i]]+=s[l[p[i]]]-T.Ask(rt[l[p[i]]],1,cnt,_r);
ans[p[i]]+=s[r[p[i]]]+T.Ask(rt[r[p[i]]],1,cnt,Y)-T.Ask(rt[r[p[i]]],1,cnt,Y-_r);
}
}
return;
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]),b[i]=a[i];
sort(b+1,b+1+n);cnt=unique(b+1,b+1+n)-b-1;
for(ll i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;
vector<ll> v;
for(ll i=1;i<=m;i++){
scanf("%lld%lld",&l[i],&r[i]);v.push_back(i);
if((r[i]-l[i]+1)&1)ans[i]+=b[a[r[i]]],r[i]--;
}
sort(v.begin(),v.end());
solve(1,n,v);
for(ll i=1;i<=m;i++)printf("%lld\n",ans[i]);
return 0;
}
边栏推荐
猜你喜欢
There is no recycle bin for deleted files on the computer desktop, what should I do if the deleted files on the desktop cannot be found in the recycle bin?
VR全景+安全科普教育,让学生们提高安全意识
web 性能提升(将持续更新……)
Rust从入门到精通05-语句和表达式
promise详解
C194铜合金C19400铁铜合金
7. yaml
[C language] Implementation of guessing number game
翻译软件哪个准确度高【免费】
【C语言篇】表达式求值(隐式类型转换,算术转换)
随机推荐
Special class and type conversion
宝塔实测-搭建PHP在线模拟考试系统
Talk预告 | 中国科学技术大学和微软亚洲研究院联合培养博士生冷燚冲:语音识别的快速纠错模型FastCorrect
mysql数据库高级操作
烘干衣服问题
C3604环保黄铜带
工作记录:DB2查询数据,当字段为空时,赋值
How to determine how many bases a number is?
App regression testing, what are the efficient testing methods?
[C language] First understanding of pointers
HGAME 2022 Week4 writeup
11. 自定义转换器
2. Dependency management and automatic configuration
[C language] Detailed explanation of data storage
Geogebra 教程之 01 什么是Geogebra,真的可以提高我们数学水平么?
[C language] binary search (half search)
祥云杯 2021 PackageManager writeup
3. 容器功能
u盘数据不小心删除怎么恢复,u盘数据删除如何恢复
iNFTnews | Web3时代,用户将拥有数据自主权