LOJ2611. NOIP2013 积木大赛【线段树】

LOJ2611. NOIP2013 积木大赛

题目大意是给你一个目标状态数组
每次你可以选择一个连续区间加上一个值，求最小操作次数

我是神奇的脑子
最近做数据结构疯了
然后看见这题就数据结构了

好像网上还没有这种做法

逆向考虑这个过程
我们直接从目标数组删去一个连续区间

我们先考虑对于一个区间肯定一次删掉是最优的情况
假设区间最小的位置是pos，那么删除后pos变成了0
所以可以递归成和两个区间
累加上pos的高度并且区间减这个高度就好了

因为每一次删除会把一个位置变成0，所以最多操作n次，然后时间复杂度是的

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 100010
 4 #define LD t<<1
 5 #define RD t<<1|1
 6 int n,h[N];
 7 int minv[N<<2],pos[N<<2],sub[N<<2];
 8 void pushup(int t){
 9     if(minv[LD]<=minv[RD]){
10         minv[t]=minv[LD],pos[t]=pos[LD];
11     }else{
12         minv[t]=minv[RD],pos[t]=pos[RD];
13     }
14 }
15 void pushdown(int t){
16     if(sub[t]){
17         minv[LD]-=sub[t];sub[LD]+=sub[t];
18         minv[RD]-=sub[t];sub[RD]+=sub[t];
19         sub[t]=0;
20     }
21 }
22 void build(int t,int l,int r){
23     if(l>r)return;
24     if(l==r){minv[t]=h[l];pos[t]=l;return;}
25     int mid=(l+r)>>1;
26     build(LD,l,mid);
27     build(RD,mid+1,r);
28     pushup(t);
29 }
30 void modify(int t,int l,int r,int L,int R,int vl){
31     if(l>r)return;
32     if(L<=l&&r<=R){minv[t]-=vl;sub[t]+=vl;return;}
33     pushdown(t);
34     int mid=(l+r)>>1;
35     if(R<=mid)modify(LD,l,mid,L,R,vl);
36     else if(mid<L)modify(RD,mid+1,r,L,R,vl);
37     else {
38         modify(LD,l,mid,L,mid,vl);
39         modify(RD,mid+1,r,mid+1,R,vl);
40     }
41     pushup(t);
42 }
43 #define pi pair<int,int>
44 pi query(int t,int l,int r,int L,int R){
45     if(l>r)return pi(0,0);
46     if(L<=l&&r<=R)return pi(minv[t],pos[t]);
47     pushdown(t);
48     int mid=(l+r)>>1;
49     pi ans;
50     if(mid>=R)ans=query(LD,l,mid,L,R);
51     else if(mid<L)ans=query(RD,mid+1,r,L,R);
52     else{
53         pi tl=query(LD,l,mid,L,mid);
54         pi tr=query(RD,mid+1,r,mid+1,R);
55         if(tl.first<=tr.first)ans=tl;
56         else ans=tr;
57     }
58     pushup(t);
59     return ans;
60 }
61 #define LL long long
62 LL solve(int l,int r){
63     if(l>r)return 0;
64     pi now=query(1,1,n,l,r);
65     modify(1,1,n,l,r,now.first);
66     return (LL)now.first+solve(l,now.second-1)+solve(now.second+1,r);
67 }
68 int main(){
69     scanf("%d",&n);
70     for(int i=1;i<=n;i++)scanf("%d",&h[i]);
71     build(1,1,n);
72     printf("%lld",solve(1,n));
73     return 0;
74 }

LOJ2611. NOIP2013 积木大赛 【线段树】

LOJ2611. NOIP2013 积木大赛

LOJ2611. NOIP2013 积木大赛【线段树】