「成都七中D5T3」第三题 - 分治+Hash | Bill Yang's Blog

「成都七中D5T3」第三题 - 分治+Hash

题目大意

    这是第三题,有趣的是这套题都是送分题。
    给出一个$1$到$N$的排列,你需要求出有多少个区间$[L,R]$,满足这个区间的值是连续的。比如$2,3,1$是一个合法的区间,而$3,1$不是。

题目分析

原题维护的信息很难处理。
考虑转化维护的信息。
不难发现我们可以将问题转化为极差=区间长度。(achen:显然)
然后就和本题一模一样了。

代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=300005,Delta=200000;
int n,LMin[maxn],LMax[maxn],RMin[maxn],RMax[maxn],a[maxn],Hash[maxn*4];
long long ans=0;
void Solve(int Left,int Right) {
if(Left==Right) {
ans++;
return;
}
int mid=(Left+Right)>>1;
for(int i=Left; i<=Right; i++)LMin[i]=RMin[i]=0x7fffffff/2,LMax[i]=RMax[i]=-0x7fffffff/2;
for(int i=mid; i>=Left; i--)LMin[i]=min(LMin[i+1],a[i]),LMax[i]=max(LMax[i+1],a[i]);
for(int i=mid+1; i<=Right; i++)RMin[i]=min(RMin[i-1],a[i]),RMax[i]=max(RMax[i-1],a[i]);
int l=mid+1,r=mid+1;
for(int i=mid; i>=Left; i--) {
int pos=LMax[i]-LMin[i]+i; //Max/Min左
if(pos>mid&&pos<=Right&&LMax[i]>=RMax[pos]&&LMin[i]<=RMin[pos])ans++;
while(r<=Right&&LMax[i]>=RMax[r]) {
Hash[r+RMin[r]]++;
r++;
}
while(l<=Right&&LMin[i]<RMin[l]) {
Hash[l+RMin[l]]--;
l++;
}
if(Hash[i+LMax[i]]>0)ans+=Hash[i+LMax[i]];
}
while(r>mid+1) {
r--;
Hash[r+RMin[r]]--;
}
while(l>mid+1) {
l--;
Hash[l+RMin[l]]++;
}
l=mid,r=mid;
for(int i=mid+1; i<=Right; i++) {
int pos=i-RMax[i]+RMin[i]; //Max/Min右
if(pos>=Left&&pos<=mid&&RMax[i]>=LMax[pos]&&RMin[i]<=LMin[pos])ans++;
while(l>=Left&&RMax[i]>=LMax[l]) {
Hash[LMin[l]-l+Delta]++;
l--;
}
while(r>=Left&&RMin[i]<LMin[r]) {
Hash[LMin[r]-r+Delta]--;
r--;
}
if(Hash[RMax[i]-i+Delta]>0)ans+=Hash[RMax[i]-i+Delta];
}
while(l<mid) {
l++;
Hash[LMin[l]-l+Delta]--;
}
while(r<mid) {
r++;
Hash[LMin[r]-r+Delta]++;
}
Solve(Left,mid);
Solve(mid+1,Right);
}
int main() {
n=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
Solve(1,n);
printf("%lld\n",ans);
return 0;
}
本篇文章有用吗?有用还不快点击!
0%