江西 网站 建设 开发,门户网站开发解决方案,网站空间 虚拟主机,东莞网站建设qq群正题
题目链接:https://uoj.ac/problem/749 题目大意
如果有序列aaa#xff0c;你每次取走一个数字后然后这个序列最前面的数字会被别人取走#xff0c;直到序列为空。此时f(a)f(a)f(a)表示你最大能取走的权值和。
给出一个长度为nnn的序列aaa#xff0c;qqq次询问区间[l…正题
题目链接:https://uoj.ac/problem/749 题目大意
如果有序列aaa你每次取走一个数字后然后这个序列最前面的数字会被别人取走直到序列为空。此时f(a)f(a)f(a)表示你最大能取走的权值和。
给出一个长度为nnn的序列aaaqqq次询问区间[l,r][l,r][l,r]求f(al∼r)f(a_{l\sim r})f(al∼r)。
1≤n,q≤2×105,1≤ai≤1091\leq n,q\leq 2\times 10^5,1\leq a_i\leq 10^91≤n,q≤2×105,1≤ai≤109 解题思路
考虑一下最优的取法我们的限制其实相当于前2i−12i-12i−1个数之中不能取走超过iii个数。
一个暴力的贪心想法是不停往前走用一个堆维护现在取了的数走到不是2i−12i-12i−1时我们考虑是否拿这个aia_iai替代堆里最小的数走到2i−12i-12i−1时直接丢进堆里就行了。
或者反过来更简单走到一个数就丢进堆里遇到2i−12i-12i−1时直接取堆中最大的数就好了。
我们现在能处理左或右端点固定的所有答案了我们考虑分治问题在于怎么去合并两个区间的答案。
为了防止大量的分类讨论对于长度为奇数的区间询问我们可以考虑去掉区间的末尾因为这个位置肯定会取到。
然后我们考虑怎么合并区间显然是前面一些选了的数字变成不选后面一些不选的数字变成选了显然是前面拿小的后面拿大的。
我们考虑在分治的时候对于区间[L,mid,R][L,mid,R][L,mid,R]对于[L,mid][L,mid][L,mid]部分我们用主席树维护选了的数字对于[mid1,R][mid1,R][mid1,R]部分我们用主席树维护没选的数字然后对于一个询问二分一个kkk然后左边的取出前kkk小右边的取出前kkk大进行比较即可。
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n) code
#includecstdio
#includecstring
#includealgorithm
#includequeue
#define ll long long
using namespace std;
const ll N2e510,MN5;
ll n,m,cnt,a[N],b[N],l[N],r[N],ans[N],s[N],rt[N];
priority_queuell 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 pcnt;w[p]w[x]val;c[p]c[x]val*b[pos];if(LR)return p;ll mid(LR)1;if(posmid)ls[p]Change(ls[x],L,mid,pos,val),rs[p]rs[x];else rs[p]Change(rs[x],mid1,R,pos,val),ls[p]ls[x];return p;}ll Find(ll x,ll L,ll R,ll k){if(LR)return L;ll mid(LR)1;if(w[ls[x]]k)return Find(ls[x],L,mid,k);return Find(rs[x],mid1,R,k-w[ls[x]]);}ll Ask(ll x,ll L,ll R,ll k){if(!k)return 0;if(LR)return b[L]*k;ll mid(LR)1;if(w[ls[x]]k)return Ask(ls[x],L,mid,k);return Ask(rs[x],mid1,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,vectorll now){if(LR)return;ll mid(LR)1;vectorll pl,pr,p;for(ll i0;inow.size();i)if(l[now[i]]midr[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(mid1,R,pr);if(!p.size())return;for(ll g0;g2;g){T.cntrt[mid]s[mid]0;for(ll imid1;iR;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 imid;iL;i--){q.push(a[i]);if(((mid-i)1)g){rt[i]T.Change((imid)?0:rt[i1],1,cnt,q.top(),1);s[i]((i!mid)?s[i1]:0)b[q.top()];q.pop();}else if(i!mid)rt[i]rt[i1],s[i]s[i1];}while(!q.empty())q.pop();for(ll i0;ip.size();i){if(((mid-l[p[i]])1)!g)continue;ll XT.w[rt[l[p[i]]]],YT.w[rt[r[p[i]]]];ll _l1,_rmin(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-_mid1))_l_mid1;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 i1;in;i)scanf(%lld,a[i]),b[i]a[i];sort(b1,b1n);cntunique(b1,b1n)-b-1;for(ll i1;in;i)a[i]lower_bound(b1,b1cnt,a[i])-b;vectorll v;for(ll i1;im;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 i1;im;i)printf(%lld\n,ans[i]);return 0;
}
