洛谷 P4497 - [WC2011]拼点游戏（数据结构综合）
神仙 DS。
首先关于第一问可以轻松想到一个 DP，\(dp_{i,j}\) 表示考虑到第 \(i\) 位，这一位奇偶性为 \(j\) 的最大权值，时间复杂度 \(n^2q\)，可以拿到 \(3\) 分的好成绩（大雾），如果稍微动点脑子使用前缀和优化还可以拿到 \(9\) 分的好成绩，但是显然这个做法是没有前途的，因为这个 DP 对第二问没有任何启发作用，并且也无法将它优化到每次询问都可以在低于 \(\mathcal O(n)\) 内处理的复杂度，因此我们只好放弃这个思路。
按照我们做题的经验，我们考虑分析一下这个权值最大的序列有什么性质，手玩几组数据后你就能发现以下性质：
Observation 1. 对于一个序列 \(a\)，我们如果将 \(a\) 划分成一段段上升段和下降段，那么我们选择的子序列的第 \(2k+1\) 个元素一定是第 \(k\) 个极小值点，第 \(2k+2\) 个元素一定是第 \(k\) 个极大值点
具体证明可用调整法，留给读者自己思考。
也就是说，第 \(2k+1\) 和第 \(2k+2\) 个元素一定是第 \(k\) 个上升段的开头和结尾，这个序列的权值就是所有上升段的结尾值减去开头的值。
注意到这个上升段、下降段维护起来有点棘手，因此我们不妨换个角度，用与其联系紧密的差分序列 \(b_i=a_{i+1}-a_i\) 来看待这个问题，因为差分序列的正负性即暗示了该元素位于上升段中还是下降段中。注意到对于一段上升序列，其末尾元素与开头元素的差就是这个差分序列中所有元素的和，而对于下降序列，其差分序列中所有元素都非正，因此我们稍微转化一下即可得到以下性质：
Observation 2. 对于序列 \(a\)，其子序列点值的最大值就是其差分序列中所有正数的和
这样第一问就解决了，因为每次区间加操作最多影响差分序列中两个元素的权值，因此这个贡献是可以 \(\mathcal O(1)\) 计算的。
接下来考虑第二问，每次操作相当于移动最优序列中下标 \(2k,2k+1\) 元素，而根据之前的推论这两个元素必然是同一个下降段的首尾元素，而显然对于下降段中的某个元素 \(x\)，将 \(x\) 移至 \(x+1\) 会使得权值加上 \(b_x\)，因此操作等价于选择某个下降段中的某个不相交的前缀和后缀，并令权值加上这段前缀和后缀中所有元素的和，问最少几次操作能使权值 \(\le 0\)。
由于下降段的差分序列中每个元素都 \(\le 0\)，因此我们肯定会贪心地选择长度加起来等于下降段减 \(1\) 的前后缀，也就是将下标 \(2k,2k+1\) 元素移至某对相邻位置 \(p,p+1\)，这样贡献就是这个相邻段中差分序列权值之和加上 \(b_p\)，而我们显然会选择 \(b_p\) 最大的 \(p\) 作为目标位置，因此可以得到：
Observation 3. 对于差分序列上每个非正段，其移动一次权值最大减少量就是这段差分序列权值之和减去这段中 \(b_i\) 的最大值。
因此对于每个非正整数的段，其进行一次操作权值的最大减少量是确定的，而我们肯定会优先选择减少量最大的下降段，因此我们可以将所有连续段权值最大减少量扔进一个平衡树，每次询问在平衡树上二分即可。每次修改操作导致连续段的变化量是 \(\mathcal O(1)\) 级别的，用个 set 维护一下即可，差分数组的区间最小值可用线段树维护。于是这题就被我们拆分成几步解决了，时间复杂度 \(n\log n\)。
注意点：注意特殊判断第一段和最后一段下降段。
码了 188 行
const int MAXN=1e5;
int n,qu,a[MAXN+5];ll b[MAXN+5],sum=0;
struct segtree{
struct node{int l,r;ll sum,mx;} s[MAXN*4+5];
void clear(int k){
if(s[k].l==s[k].r) return s[k].l=s[k].r=s[k].sum=s[k].mx=0,void();
clear(k<<1);clear(k<<1|1);s[k].l=s[k].r=s[k].sum=s[k].mx=0;
}
void pushup(int k){
s[k].mx=max(s[k<<1].mx,s[k<<1|1].mx);
s[k].sum=s[k<<1].sum+s[k<<1|1].sum;
}
void build(int k,int l,int r){
s[k].l=l;s[k].r=r;if(l==r) return s[k].mx=s[k].sum=b[l],void();
int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k);
}
void modify(int k,int p,ll x){
if(s[k].l==s[k].r) return s[k].mx=s[k].sum=x,void();int mid=s[k].l+s[k].r>>1;
(p<=mid)?modify(k<<1,p,x):modify(k<<1|1,p,x);pushup(k);
}
ll getmax(int k,int l,int r){
if(l<=s[k].l&&s[k].r<=r) return s[k].mx;int mid=s[k].l+s[k].r>>1;
if(r<=mid) return getmax(k<<1,l,r);else if(l>mid) return getmax(k<<1|1,l,r);
else return max(getmax(k<<1,l,mid),getmax(k<<1|1,mid+1,r));
}
ll getsum(int k,int l,int r){
if(l<=s[k].l&&s[k].r<=r) return s[k].sum;int mid=s[k].l+s[k].r>>1;
if(r<=mid) return getsum(k<<1,l,r);else if(l>mid) return getsum(k<<1|1,l,r);
else return getsum(k<<1,l,mid)+getsum(k<<1|1,mid+1,r);
}
} st;
struct fhqtreap{
struct node{int ch[2],key,siz;ll sum,val;} s[MAXN*3+5];
int rt,ncnt;
fhqtreap(){rt=ncnt=0;}
void init(){
for(int i=1;i<=ncnt;i++) s[i].ch[0]=s[i].ch[1]=s[i].key=s[i].siz=s[i].sum=s[i].val=0;
rt=ncnt=0;
}
void pushup(int k){
s[k].sum=s[s[k].ch[0]].sum+s[s[k].ch[1]].sum+s[k].val;
s[k].siz=s[s[k].ch[0]].siz+s[s[k].ch[1]].siz+1;
}
void split(int k,ll v,int &a,int &b){
if(!k) return a=b=0,void();
if(s[k].val<=v) return a=k,split(s[k].ch[1],v,s[k].ch[1],b),pushup(k),void();
else return b=k,split(s[k].ch[0],v,a,s[k].ch[0]),pushup(k),void();
}
int merge(int x,int y){
if(!x||!y) return x+y;
if(s[x].key<s[y].key) return s[x].ch[1]=merge(s[x].ch[1],y),pushup(x),x;
else return s[y].ch[0]=merge(x,s[y].ch[0]),pushup(y),y;
}
void insert(ll x){
// printf("insert %lld\n",x);
s[++ncnt].sum=x;s[ncnt].val=x;s[ncnt].key=rand();s[ncnt].siz=1;
int k1,k2;split(rt,x-1,k1,k2);rt=merge(merge(k1,ncnt),k2);
// printf("%d\n",rt);
}
void del(ll x){
// printf("del %lld\n",x);
int k1,k2,k3;split(rt,x-1,k1,k2);split(k2,x,k2,k3);
rt=merge(merge(k1,s[k2].ch[0]),merge(s[k2].ch[1],k3));
}
int walk(int k,ll v){
if(v<=0) return 0;
if(s[k].sum+v>0) return -1;
// printf("%d %lld %lld %lld %lld\n",k,v,s[s[k].ch[0]].sum,s[s[k].ch[1]].sum);
if(s[s[k].ch[0]].sum+v<=0) return walk(s[k].ch[0],v);
else if(s[s[k].ch[0]].sum+s[k].val+v<=0) return s[s[k].ch[0]].siz+1;
else return s[s[k].ch[0]].siz+1+walk(s[k].ch[1],v+(s[s[k].ch[0]].sum+s[k].val));
}
} trp;
ll getval(int l,int r){return st.getsum(1,l,r)-st.getmax(1,l,r);}
set<pii> itv;
void delitv(int l,int r){
assert(l<=r);
// printf("delitv %d %d\n",l,r);
itv.erase(itv.find(mp(l,r)));
if((l^1)&&(r^(n-1))) trp.del(getval(l,r));
}
void insitv(int l,int r){
assert(l<=r);
// printf("insitv %d %d\n",l,r);
itv.insert(mp(l,r));
if((l^1)&&(r^(n-1))) trp.insert(getval(l,r));
}
void chg(int x,ll v){
sum-=max(b[x],0ll);sum+=max(v,0ll);
if(b[x]>0&&v<=0){
pii nxt=*itv.upper_bound(mp(x,n+1));
pii pre=*--itv.lower_bound(mp(x,0));
int l=x,r=x;
if(nxt.fi==x+1) delitv(nxt.fi,nxt.se),r=nxt.se;
if(pre.se==x-1) delitv(pre.fi,pre.se),l=pre.fi;
st.modify(1,x,v);insitv(l,r);
} else if(b[x]<=0&&v>0){
pii lrg=*--itv.lower_bound(mp(x,n+1));
delitv(lrg.fi,lrg.se);st.modify(1,x,v);
if(lrg.se^x) insitv(x+1,lrg.se);
if(lrg.fi^x) insitv(lrg.fi,x-1);
} else if(b[x]<=0){
pii t=*--itv.lower_bound(mp(x,n+1));
delitv(t.fi,t.se);st.modify(1,x,v);
insitv(t.fi,t.se);
} else st.modify(1,x,v);
b[x]=v;
}
void clear(){
memset(a,0,sizeof(a));memset(b,0,sizeof(b));
sum=0;itv.clear();trp.init();st.clear(1);
}
void solve(){
scanf("%d%d",&n,&qu);clear();
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<n;i++) b[i]=a[i+1]-a[i],sum+=max(b[i],0ll);
st.build(1,1,n-1);itv.insert(mp(-1,-1));itv.insert(mp(n+1,n+1));
int pre=0;
for(int i=1;i<n;i++) if(b[i]>0){
if(pre^(i-1)) insitv(pre+1,i-1);
pre=i;
} if(pre^(n-1)) insitv(pre+1,n-1);
while(qu--){
int opt;scanf("%d",&opt);
if(opt==0){
int l,r,v;scanf("%d%d%d",&l,&r,&v);
if(l^1) chg(l-1,b[l-1]+v);
if(r^n) chg(r,b[r]-v);
} else {
printf("%lld %d\n",sum,trp.walk(trp.rt,sum));
}
}
}
int main(){int qu;scanf("%d",&qu);while(qu--) solve();return 0;}
最新文章
- 【13-Annotation】
- Moscow Pre-Finals Workshop 2016. National Taiwan U Selection
- Command设计模式
- HDU5437 Alisha’s Party 优先队列
- oracle 中v$sqlarea,v$sql,v$session,gv$session，远程连接等问题
- UIImagePickerController 如何显示中文界面
- 1.2 N层架构
- oracle查询第一篇
- 关于RDLC报表打印预览界面显示页码问号的问题
- arduino与DS1302时钟调试失败的分析
- 异常-----freemarker.core.ParseException: Encountered
- （一）你的第一个Socket程序
- linux TOP参数
- h5中input的request属性提示文字字段
- Github Upload Large File 上传超大文件
- C#编程（三十五）----------foreach和yield
- kubernetes实战(十二)：k8s使用helm持久化部署redmine集成openLDAP
- php file_exists无效解决办法
- javascript 中 if (window != top) top.location.href = location.href;的意思
- 使用 C＃ 开发智能手机软件：推箱子(十四)