【IOI2018】会议

Source

IOI2018
loj2868

Hint

请先思考后再展开

对于询问[l,r],找到mx表示最大位置,那么
$ans(l,r)=min:ans(l,mx-1)+a_{mx} \times (r-mx+1),ans(mx+1,r)+a_{mx} \times (mx-l+1)​$

这样的好处就是知道有一个极大值贴着区间的某侧,然后这样通常都会产生一些不错的性质,类似的例子

Solution

请先思考后再展开

只要建出笛卡尔树,把询问挂在点上,考虑从下往上,对每个点(覆盖范围为[l,r])求出所有贴着l或者r的区间S,就能回答询问了,那么以贴着l为例,考虑怎么由lc和rc合并为当前$S_{rt}​$:lc是直接全部保留的,然后对于rc,

$ans(l,k \geq rt)=min:ans(l,rt-1)+a_{rt} \times (k-rt+1),ans(rt+1,k)+a_{rt} \times (rt-l+1)​$

仔细观察一下上式,随着k的增大,左边一定增加 $a_{rt}​$ ,右边则会增加比 $a_{rt}​$ 小的一个量($a_{rt}​$是最大的),那么只要线段树上二分到一个分界点,那么就是给区间改成与pos相关的一次函数或者区间加法,还有单点询问

$ans(k \leq rt,r)=min:ans(rt+1,r)+a_{rt} \times (rt-k+1),ans(k,rt-1)+a_{rt} \times (r-rt+1)​$ 同理
考虑如何实现,你会发现看似区间很多,但对于每个r,其实当前这一层对应的l是固定的,$seg[r]=ans(l,r)$ ,然后在非叶子节点的地方,定义为保存$a_{mid}$的值。
时间复杂度为 $O(nlogn)$ (uoj被卡常了)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3fLL;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(ll num){write(num);puts("");}
inline void chmax(int &x,int y) {x=x>y?x:y;}
inline void chmin(int &x,int y) {x=x<y?x:y;}
inline void chmaxll(ll &x,ll y) {x=x>y?x:y;}
inline void chminll(ll &x,ll y) {x=x<y?x:y;}
#define PB push_back
#define FR first
#define SE second
#define MP make_pair
#define pr pair<ll,ll>
const int MAX_N=2e6+10;
struct SegmentTree
{
#define lc 2*x
#define rc 2*x+1
pr now[MAX_N*4];bool lz2[MAX_N*4];ll lz[MAX_N*4];
SegmentTree(){memset(now,0,sizeof now);memset(lz,0,sizeof lz);memset(lz2,0,sizeof lz2);}
void ch(int x,pr c) {now[x]=c;lz2[x]=1;lz[x]=0;}
void ad(int x,ll c) {if(lz2[x] and 2*x<=MAX_N*4) ch(lc,now[x]),ch(rc,now[x]),lz2[x]=0;now[x].SE+=c;lz[x]+=c;}//debug
void update(int x)
{
if(lz2[x]) ch(lc,now[x]),ch(rc,now[x]),lz2[x]=0;
if(lz[x]>0) ad(lc,lz[x]),ad(rc,lz[x]),lz[x]=0;
}
void add(int x,int l,int r,int fl,int fr,ll c)
{
update(x);
if(l==fl and r==fr) {ad(x,c);return;}
int mid=(l+r)>>1;
if(fr<=mid) add(lc,l,mid,fl,fr,c);
else if(fl>mid) add(rc,mid+1,r,fl,fr,c);
else add(lc,l,mid,fl,mid,c),add(rc,mid+1,r,mid+1,fr,c);
if(fl<=mid and fr>=mid) now[x].SE+=c;
}
pr ask(int x,int l,int r,int pos)
{
update(x);
if(l==r) return now[x];
int mid=(l+r)>>1;
if(pos<=mid) return ask(lc,l,mid,pos);
return ask(rc,mid+1,r,pos);
}
void solve(int x,int l,int r,int fl,int fr,pr c,bool op)
{
update(x);
if(fl>fr) return;
int mid=(l+r)>>1;ll a=now[x].FR*mid+now[x].SE,b=c.FR*mid+c.SE;
if(fl<=mid and mid<=fr and b<a) now[x]=c;
if(l==fl and r==fr)
{
if(l==r) return;
if(op)
{
if(b<=a) solve(lc,l,mid,l,mid,c,op),ch(rc,c);
else solve(rc,mid+1,r,mid+1,r,c,op);
}
else
{
if(b<=a) ch(lc,c),solve(rc,mid+1,r,mid+1,r,c,op);
else solve(lc,l,mid,l,mid,c,op);
}
}
else
{
if(fr<=mid) solve(lc,l,mid,fl,fr,c,op);
else if(fl>mid) solve(rc,mid+1,r,fl,fr,c,op);
else solve(lc,l,mid,fl,mid,c,op),solve(rc,mid+1,r,mid+1,fr,c,op);
}
}
#undef lc
#undef rc
}sgt1,sgt2;
int n,h[MAX_N];
struct Qes{int l,r,id;};vector<Qes> qes[MAX_N];
int bin[20],f[MAX_N][20],root=1;
struct Nod{int dep,lc,rc,fl,fr;}p[MAX_N];
void build()
{
for(int i=2;i<=n;i++)
{
int now=i-1;
while(f[now][0]>0 and h[i]>h[now]) now=f[now][0];
if(h[i]<=h[now])
{
if(p[now].rc>0) f[p[now].rc][0]=i;//debug
p[i].lc=p[now].rc,p[now].rc=i,f[i][0]=now;
}
else f[now][0]=i,p[i].lc=now,root=i;
}
}
void dfs(int x)
{
p[x].dep=p[f[x][0]].dep+1;for(int i=1;i<20;i++) f[x][i]=f[f[x][i-1]][i-1];
p[x].fl=p[x].fr=x;
if(p[x].lc) dfs(p[x].lc),chmin(p[x].fl,p[p[x].lc].fl),chmax(p[x].fr,p[p[x].lc].fr);
if(p[x].rc) dfs(p[x].rc),chmin(p[x].fl,p[p[x].rc].fl),chmax(p[x].fr,p[p[x].rc].fr);
}
int lca(int x,int y)
{
if(p[x].dep<p[y].dep) swap(x,y);
for(int i=19;i>=0;i--) if(p[x].dep-p[y].dep>=bin[i]) x=f[x][i];
if(x==y) return x;
for(int i=19;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
ll ans[MAX_N];
void solve(int x)
{
if(p[x].lc) solve(p[x].lc);
if(p[x].rc) solve(p[x].rc);
for(int t=0;t<(int)qes[x].size();t++)
{
Qes now=qes[x][t];ans[now.id]=ll(now.r-now.l+1)*h[x];
pr k=p[x].lc>0?sgt2.ask(1,1,n,now.l):MP(0ll,0ll);
chminll(ans[now.id], (k.FR*now.l+k.SE)+ll(now.r-x+1)*h[x] );
k=p[x].rc>0?sgt1.ask(1,1,n,now.r):MP(0ll,0ll);
chminll(ans[now.id], (k.FR*now.r+k.SE)+ll(x-now.l+1)*h[x] );
}
int l=p[x].fl,r=p[x].fr;
if(l==r) sgt1.add(1,1,n,x,x,h[x]);
sgt1.add(1,1,n,x,r,(ll)h[x]*(x-l+1) );pr t=p[x].lc>0?sgt1.ask(1,1,n,x-1):MP(0ll,0ll);
sgt1.solve(1,1,n,x,r,MP(h[x],(t.FR*(x-1)+t.SE)+ll(1-x)*h[x]),0);
sgt2.add(1,1,n,l,x,(ll)h[x]*(r-x+1) );t=p[x].rc>0?sgt2.ask(1,1,n,x+1):MP(0ll,0ll);
sgt2.solve(1,1,n,l,x,MP(-h[x],(t.FR*(x+1)+t.SE)+ll(1+x)*h[x]),1);
}
void main()
{
bin[0]=1;for(int i=1;i<20;i++) bin[i]=bin[i-1]<<1;
int q;scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) h[i]=qread();
build();dfs(root);
for(int i=1;i<=q;i++)
{
int l=qread()+1,r=qread()+1;
qes[lca(l,r)].PB( (Qes){l,r,i} );
}
memset(ans,0x3f,sizeof ans);solve(root);
for(int i=1;i<=q;i++) writeln(ans[i]);
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/c53a.html
转载请注明出处,谢谢!