关于后手的策略，等价于限制先手在前$2i$个数中至多选$i$个
当$|[l,r]|$为奇数时，先手必然取走$a_{r}$，并以此转换为$[l,r)$的问题
在此基础上，对$l$的奇偶性分类讨论，并以此将相邻两数合并为一组
考虑分治，除递归的部分外，问题即实现以下步骤：
1. 求出$[l,mid]$后缀和$(mid,r]$前缀的答案
2. 将$[x,mid]$和$(mid,y]$的答案合并得到$[x,y]$的答案
关于前者，分别有以下两种贪心方式：
1. 从后往前扫描，维护集合$S$，表示当前未选的元素
每次将一组的两数加入$S$，并选择$S$中最大的元素（从$S$中删除）
2. 从前往后扫描，维护集合$S$，表示当前选择的元素
每次选择一组的两数（加入$S$），并撤销$S$中最小的元素（从$S$中删除）
关于后者，答案即不断用$(mid,y]$中未选的最大元素替换$[x,mid]$中选择的最小元素
对两侧分别用可持久化线段树维护所求的位置，并在其中二分即可
时间复杂度为$o(n\log^{2}n+q\log n)$，可以通过
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 200005
4 #define M 4000000
5 #define ll long long
6 #define mid (l+r>>1)
7 #define fi first
8 #define se second
9 int n,q,a[N],L[N],R[N];ll ans[N];
10 struct MAIN{
11 int n,V,rt[N],ls[M],rs[M],f1[M];ll sum[N],f2[M];
12 pair<int,int>a[N];vector<int>v;multiset<int>S;
13 void update(int &k,int l,int r,int x){
14 ls[++V]=ls[k],rs[V]=rs[k];
15 f1[V]=f1[k]+1,f2[V]=f2[k]+x,k=V;
16 if (l==r)return;
17 if (x<=mid)update(ls[k],l,mid,x);
18 else update(rs[k],mid+1,r,x);
19 }
20 ll query(int &k1,int &k2,int l,int r,int s1,int s2){
21 if (l==r)return f2[k1]-f2[k2]+(ll)(s1-s2)*l;
22 if (f1[ls[k1]]+s1>f1[rs[k2]]+s2)
23 return query(ls[k1],ls[k2],l,mid,s1,s2+f1[rs[k2]])+f2[rs[k1]];
24 return query(rs[k1],rs[k2],mid+1,r,s1+f1[ls[k1]],s2)-f2[ls[k2]];
25 }
26 void calc(int l,int r,vector<int>v){
27 if (v.empty())return;
28 if (l==r){
29 for(int i:v)ans[i]+=max(a[l].fi,a[l].se);
30 return;
31 }
32 V=0,S.clear();
33 for(int i=mid;i>=l;i--){
34 S.insert(a[i].fi),S.insert(a[i].se);
35 rt[i]=(i==mid ? 0 : rt[i+1]);
36 update(rt[i],1,1e9,(*--S.end())),S.erase(--S.end());
37 }
38 sum[mid]=0,S.clear();
39 for(int i=mid+1;i<=r;i++){
40 S.insert(a[i].fi),S.insert(a[i].se);
41 rt[i]=(i==mid+1 ? 0 : rt[i-1]),sum[i]=sum[i-1]+a[i].fi+a[i].se;
42 update(rt[i],1,1e9,(*S.begin())),S.erase(S.begin());
43 }
44 for(int i:v)
45 if ((L[i]<=mid)&&(mid<R[i]))
46 ans[i]+=sum[R[i]]+query(rt[L[i]],rt[R[i]],1,1e9,0,0);
47 vector<int>vl,vr;
48 for(int i:v){
49 if (R[i]<=mid)vl.push_back(i);
50 if (L[i]>mid)vr.push_back(i);
51 }
52 calc(l,mid,vl),calc(mid+1,r,vr);
53 }
54 }T1,T2;
55 int main(){
56 scanf("%d%d",&n,&q);
57 for(int i=1;i<=n;i++)scanf("%d",&a[i]);
58 T1.n=(n>>1),T2.n=(n-1>>1);
59 for(int i=1;i<=T1.n;i++)T1.a[i]=make_pair(a[(i<<1)-1],a[i<<1]);
60 for(int i=1;i<=T2.n;i++)T2.a[i]=make_pair(a[i<<1],a[(i<<1)+1]);
61 for(int i=1;i<=q;i++){
62 scanf("%d%d",&L[i],&R[i]);
63 if ((R[i]-L[i]+1)&1)ans[i]=a[R[i]--];
64 if (L[i]<R[i]){
65 if (L[i]&1)T1.v.push_back(i);
66 else T2.v.push_back(i);
67 L[i]=(L[i]+1>>1),R[i]>>=1;
68 }
69 }
70 if (T1.n)T1.calc(1,T1.n,T1.v);
71 if (T2.n)T2.calc(1,T2.n,T2.v);
72 for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
73 return 0;
74 }
View Code
标签：uoj749,rs,int,T2,mid,选手,ls,稳健,define From： https://www.cnblogs.com/PYWBKTDA/p/16594958.html