【HNOI2016】序列【HNOI2017】影魔

Source

HNOI2016、HNOI2017
loj2051

Solution

请先思考后再展开

先说序列

先求出每个位置左右第一个比他小的lmi和rmi,可以用单调栈解决
然后显然整体思路是把每个区间贡献到最小值上面

先考虑莫队,只要能解决右边增加一个的操作,那么其他操作都是类似的
先求出[l,r+1]的最小的位置p(st表),然后一定有个位置lmi=p
注意到lmi是个森林,然后你可以把代价贡献到边权上
那么代价就是树上路径+p的那条不完整的边
$O(n \sqrt n)$

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
//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;
int qread()
{
int 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(int num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
inline void chmax(int &x,int y) {x=x>y?x:y;}
inline void chmin(int &x,int y) {x=x<y?x:y;}
const int MAX_N=110000;
int n,a[MAX_N];
int bin[30],lg[MAX_N],mm[MAX_N][30];
int gmin(int x,int y){return a[x]<a[y]?x:y;}
void pre()
{
bin[0]=1;for(int i=1;i<=20;i++) bin[i]=bin[i-1]<<1;
lg[1]=0;for(int i=2;i<MAX_N;i++) lg[i]=lg[i>>1]+1;
for(int i=1;i<=20;i++)
for(int j=0;j<n-bin[i]+1;j++)
mm[j][i]=gmin(mm[j][i-1],mm[j+bin[i-1]][i-1]);
}
int ask(int l,int r)
{
int t=lg[r-l+1];
return gmin(mm[l][t],mm[r-bin[t]+1][t]);
}
int fa[2][MAX_N];ll dis[2][MAX_N];//森林
stack<pr> sta;
void pre2()
{
sta.push(MP(a[0],0));fa[0][0]=-1;dis[0][0]=a[0];
for(int i=1;i<n;i++)
{
while(sta.size() and sta.top().FR>=a[i]) sta.pop();
fa[0][i]=sta.size()>0?sta.top().SE:-1;
if(fa[0][i]>=0) dis[0][i]=dis[0][fa[0][i]]+ll(i-fa[0][i])*a[i];
else dis[0][i]=(ll)a[i]*(i+1);
sta.push(MP(a[i],i));
}
while(sta.size()) sta.pop();
sta.push(MP(a[n-1],n-1));fa[1][n-1]=-1;dis[1][n-1]=a[n-1];
for(int i=n-2;i>=0;i--)
{
while(sta.size() and sta.top().FR>=a[i]) sta.pop();
fa[1][i]=sta.size()>0?sta.top().SE:-1;
if(fa[1][i]>=0) dis[1][i]=dis[1][fa[1][i]]+ll(fa[1][i]-i)*a[i];
else dis[1][i]=(ll)a[i]*(n-i);
sta.push(MP(a[i],i));
}
}
struct Qes{int l,r,id;ll ans;}q[MAX_N];
int T;
bool cmp(Qes a,Qes b) {return a.l/T<b.l/T or (a.l/T==b.l/T and a.r<b.r);}
bool cmp2(Qes a,Qes b) {return a.id<b.id;}
ll now=0;int fl,fr;
void movel(int f)
{
int k=ask(fl,fr);
now+=(dis[1][fl]-dis[1][k]+ll(fr-k+1)*a[k])*f;
}
void mover(int f)
{
int k=ask(fl,fr);
now+=(dis[0][fr]-dis[0][k]+ll(k-fl+1)*a[k])*f;
}
void main()
{
n=qread();T=sqrt(n);int m=qread();
for(int i=0;i<n;i++) a[i]=qread(),mm[i][0]=i;
pre();pre2();
for(int i=1;i<=m;i++) q[i].l=qread()-1,q[i].r=qread()-1,q[i].id=i;
sort(q+1,q+m+1,cmp);
fl=q[1].l,fr=q[1].l-1;
for(int i=1;i<=m;i++)
{
while(fl>q[i].l) fl--,movel(1);
while(fr<q[i].r) fr++,mover(1);
while(fl<q[i].l) movel(-1),fl++;
while(fr>q[i].r) mover(-1),fr--;
q[i].ans=now;
}
sort(q+1,q+m+1,cmp2);for(int i=1;i<=m;i++) printf("%lld\n",q[i].ans);
}
};
int main()
{
srand(time(0));
mine::main();
}

然后考虑在线,你观察一下莫队的做法,其实你需要的就是一个前缀、后缀和

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
//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;
int qread()
{
int 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(int num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
inline void chmax(int &x,int y) {x=x>y?x:y;}
inline void chmin(int &x,int y) {x=x<y?x:y;}
const int MAX_N=110000;
int n,a[MAX_N];
int bin[30],lg[MAX_N],mm[MAX_N][30];
int gmin(int x,int y){return a[x]<a[y]?x:y;}
void pre()
{
bin[0]=1;for(int i=1;i<=20;i++) bin[i]=bin[i-1]<<1;
lg[1]=0;for(int i=2;i<MAX_N;i++) lg[i]=lg[i>>1]+1;
for(int i=1;i<=20;i++)
for(int j=0;j<n-bin[i]+1;j++)
mm[j][i]=gmin(mm[j][i-1],mm[j+bin[i-1]][i-1]);
}
int ask(int l,int r)
{
int t=lg[r-l+1];
return gmin(mm[l][t],mm[r-bin[t]+1][t]);
}
int fa[2][MAX_N];ll dis[2][MAX_N];//森林
ll g[2][MAX_N];
stack<pr> sta;
void pre2()
{
sta.push(MP(a[0],0));fa[0][0]=-1;g[0][0]=dis[0][0]=a[0];
for(int i=1;i<n;i++)
{
while(sta.size() and sta.top().FR>=a[i]) sta.pop();
fa[0][i]=sta.size()>0?sta.top().SE:-1;
if(fa[0][i]>=0) dis[0][i]=dis[0][fa[0][i]]+ll(i-fa[0][i])*a[i];
else dis[0][i]=(ll)a[i]*(i+1);
sta.push(MP(a[i],i));
g[0][i]=g[0][i-1]+dis[0][i];
}
while(sta.size()) sta.pop();
sta.push(MP(a[n-1],n-1));fa[1][n-1]=-1;g[1][n-1]=dis[1][n-1]=a[n-1];
for(int i=n-2;i>=0;i--)
{
while(sta.size() and sta.top().FR>=a[i]) sta.pop();
fa[1][i]=sta.size()>0?sta.top().SE:-1;
if(fa[1][i]>=0) dis[1][i]=dis[1][fa[1][i]]+ll(fa[1][i]-i)*a[i];
else dis[1][i]=(ll)a[i]*(n-i);
sta.push(MP(a[i],i));
g[1][i]=g[1][i+1]+dis[1][i];
}
}
void main()
{
n=qread();int m=qread();
for(int i=0;i<n;i++) a[i]=qread(),mm[i][0]=i;
pre();pre2();
for(int i=1;i<=m;i++)
{
int l=qread()-1,r=qread()-1;
int k=ask(l,r);
ll ans=(ll)a[k]*(k-l+1)*(r-k+1);
ans+=g[0][r]-g[0][k]-dis[0][k]*(r-k);
ans+=g[1][l]-g[1][k]-dis[1][k]*(k-l);
printf("%lld\n",ans);
}
}
};
int main()
{
srand(time(0));
mine::main();
}

然后你会发现影魔是挺类似的,不过是排列
对于第一问,套路地选取最大点p,然后在l和r内的点对是不能跨过p的
第一问的点对,就是每个点向左向右第一个更大的,贡献为1,预处理左端点和右端点的前缀和
$A=(ls[p]-ls[l-1])+(rs[r]-rs[p])$
对于第二问,感觉不太好求,但考虑两个问的关系,可以设置第三问,就是中间比两点max小
那么B=C-A,然后这个C也是求左右两边第一个更大的,但贡献为中间长度-1
那么离线一下,从左往右扫右端点,就变成一个区间加,区间求和

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
//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;
int qread()
{
int 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(int num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
inline void chmax(int &x,int y) {x=x>y?x:y;}
inline void chmin(int &x,int y) {x=x<y?x:y;}
const int MAX_N=210000;
int n,a[MAX_N];
struct SegmentTree
{
#define lc 2*x
#define rc 2*x+1
ll lz[MAX_N*4],sum[MAX_N*4];int tl[MAX_N*4],tr[MAX_N*4];
void clear(){memset(lz,0,sizeof lz);memset(sum,0,sizeof sum);}
void build(int x,int l,int r)
{
tl[x]=l;tr[x]=r;if(l==r) return;
int mid=(l+r)>>1;
build(lc,l,mid);build(rc,mid+1,r);
}
void pd(int x)
{
sum[lc]+=lz[x]*(tr[lc]-tl[lc]+1);lz[lc]+=lz[x];
sum[rc]+=lz[x]*(tr[rc]-tl[rc]+1);lz[rc]+=lz[x];
lz[x]=0;
}
void add(int x,int fl,int fr)
{
if(fl>fr) return;
sum[x]+=(fr-fl+1);
if(tl[x]==fl and tr[x]==fr){lz[x]++;return;}
int mid=(tl[x]+tr[x])>>1;
if(fr<=mid) add(lc,fl,fr);
else if(fl>mid) add(rc,fl,fr);
else add(lc,fl,mid),add(rc,mid+1,fr);
}
ll ask(int x,int fl,int fr)
{
if(fl>fr) return 0;
if(tl[x]==fl and tr[x]==fr) return sum[x];
pd(x);int mid=(tl[x]+tr[x])>>1;
if(fr<=mid) return ask(lc,fl,fr);
if(fl>mid) return ask(rc,fl,fr);
return ask(lc,fl,mid)+ask(rc,mid+1,fr);
}
}sgt;
struct Stb
{
int mm[MAX_N][20],bin[20],lg[MAX_N];
int gmin(int x,int y) {return a[x]>a[y]?x:y;}
void pre()
{
bin[0]=1;for(int i=1;i<20;i++) bin[i]=bin[i-1]<<1;
lg[1]=0;for(int i=2;i<MAX_N;i++) lg[i]=lg[i>>1]+1;
for(int i=1;i<20;i++) for(int j=1;j<=n-bin[i]+1;j++)
mm[j][i]=gmin(mm[j][i-1],mm[j+bin[i-1]][i-1]);
}
int ask(int x,int y)
{
int t=lg[y-x+1];
return gmin(mm[x][t],mm[y-bin[t]+1][t]);
}
}stb;
int p1[MAX_N],p2[MAX_N];stack<pr> sta;
void pre()
{
p1[1]=0;sta.push(MP(1,a[1]));
for(int i=2;i<=n;i++)
{
while(sta.size() and sta.top().SE<=a[i]) sta.pop();
p1[i]=sta.size()>0?sta.top().FR:0;sta.push(MP(i,a[i]));
}
while(sta.size()) sta.pop();
p2[n]=n+1;sta.push(MP(n,a[n]));
for(int i=n-1;i>=1;i--)
{
while(sta.size() and sta.top().SE<=a[i]) sta.pop();
p2[i]=sta.size()>0?sta.top().FR:n+1;sta.push(MP(i,a[i]));
}
}
vector<pr> fl[MAX_N],fr[MAX_N];
ll ct1[MAX_N],ct2[MAX_N];
int ls[MAX_N],rs[MAX_N];
void work()
{
for(int i=1;i<=n;i++)
{
if(p2[i]<=n) ls[i]++,rs[p2[i]]++;
if(p1[i]>=1) ls[p1[i]]++,rs[i]++;
}
for(int i=2;i<=n;i++) ls[i]+=ls[i-1],rs[i]+=rs[i-1];
sgt.clear();sgt.build(1,1,n);
for(int r=1;r<=n;r++)
{
sgt.add(1,p1[r]+1,r-1);
for(int t=0;t<(int)fr[r].size();t++)
{
pr now=fr[r][t];
ct2[now.SE]+=sgt.ask(1,now.FR,n);
int p=stb.ask(now.FR,r);
ct1[now.SE]+=(ls[p-1]-ls[now.FR-1])+(rs[r]-rs[p]);
}
}
sgt.clear();
for(int l=n;l>=1;l--)
{
sgt.add(1,l+1,p2[l]-1);
for(int t=0;t<(int)fl[l].size();t++)
{
pr now=fl[l][t];
ct2[now.SE]+=sgt.ask(1,1,now.FR);
}
}
}
void main()
{
int m,c1,c2;scanf("%d%d%d%d",&n,&m,&c1,&c2);
for(int i=1;i<=n;i++) a[i]=qread(),stb.mm[i][0]=i;
stb.pre();pre();
for(int i=1;i<=m;i++)
{
int l=qread(),r=qread();
fl[l].push_back(MP(r,i));
fr[r].push_back(MP(l,i));
}
work();
for(int i=1;i<=m;i++) printf("%lld\n",ct1[i]*c1+(ct2[i]-ct1[i])*c2);
}
};
int main()
{
srand(time(0));
mine::main();
}

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