#C241029B. 吉他(guitar)
标签（Label）
- 模拟
- 观察+分析
网址（Website）
#3609. 「PA 2021」Ranking sklepów internetowych - LibreOJ
题目（Problem）
样例
输入数据 1
5
1 4 3 5 2输出数据 1
11 5样例2
见选手目录下的 guitar/guitar2.in 与 guitar/guitar2.ans 。
数据规模与约定
对于 $20%$ 的数据：$n \leq 400$ 。
对于 $40%$ 的数据：$n \leq 2000$ 。
对于另外 $20%$ 的数据：$p_i = i$ 。
对于另外 $20%$ 的数据：$p_i$ 在给定 $n$ 的所有合法的输入中均匀随机。
对于 $100%$ 的数据：$1 \leq n \leq 10^6$；$p_i$ 为一个 $1$ 到 $n$ 排列。
评分方式
若输出的第一个值错误，则获得该测试点 $0$ 的分数。
若输出的第一个值正确，第二个值错误，则获得该测试点 $40$ 的分数。
若输出的两个值均正确，则获得该测试点 $100$ 的分数。
请务必保证输出为两个整数，否则校验器无法保证你提交的代码能获得正确的分数。
题解（Solution）
88分
$\qquad$容易发现 $f(a)$ 的最大值一定是 $2\times n + 1$ ，考虑计算可能的区间数，从排列的最大值开始拓展区间，每次考虑向外拓展 $1$ 的长度，可以发现，当长度为 $siz$ 时，此时必须满足 $x\ge\lfloor\frac{2\times n+1-siz}{2}\rfloor$ 的数都存在，于是每次暴力拓展，枚举每个满足条件的区间，可以使用类似深搜的方式扩展区间，并且记录计算过的区间，时间复杂度 $O(ans\times\log ans)$ ， $ans$ 表示满足条件的区间数量。
100分
$\qquad$枚举 $siz$ ，如果当前需要的数不在区间里面，直接拓展区间，令当前 $siz$ 拓展后的区间为 $[l,r]$ 如果 $r-l+1>siz$ ，则当前 $siz$ 不存在可行方案，否则所有的长度为 $siz$ 且包含区间 $[l,r]$ 的区间都能对答案产生贡献，统计的最后的答案。
$\qquad$时间复杂度 $O(n)$ 。
出题者题解
【第一问】
有：
$f(a_1\ldots n) = n + \lceil m/2 \rceil + \lceil (m+1)/2 \rceil = 2n + 1$
另外，长度为 $m$ 的连续子序列答案可能的最大值为：
$f(b) = m + 2(n - m) + \lceil m/2 \rceil + \lceil (m+1)/2 \rceil = 2n + 1$
因此，第一问的答案一定为 $2n + 1$。
【第二问】
考虑长度为 $m$ 的连续子序列取到最大值的条件是什么。
$a_{\lceil m/2 \rceil}$ 和 $a_{\lceil (m+1)/2 \rceil}$ 要取到最大值，也就是不小于 $n - m + \lceil m/2 \rceil$ 的数都要出现。
记不小于 $n - m + \lceil m/2 \rceil$ 的数出现的最左最右的位置分别为 $l, r$，合法区间要满足长度为 $m$，且包含区间 $[l, r]$。
算这个数量是简单的。那么我们从小到大枚举 $m$，从大到小加入不小于 $n - m + \lceil m/2 \rceil$ 的数（信息从上一个 $m$ 继承过来），维护 $l, r$，即可得到答案。
时间复杂度 $O(n)$。
代码（Code）
80分
#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i==)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1012345;
bool ST;
int n,ans,a[N],b[N];
struct BAOLI{
inline bool check0(){return is_sorted(a+1,a+n+1);}
void Solve0(){printf("%lld\n",n);}
}Gan;
map<P,bool> mp;
void calc(int l,int r){
if(mp.count({l,r})) return;
mp[{l,r}] = true;ans++;//µ±Ç°Çø¼ä±Ø¶¨Âú×ãÌõ¼þ
if(l==1 && r==n) return;
int nd = (2*n+1 - (r-l+1+1))/2, lmt = nd;
if(in(b[nd],l,r)){
if(in(l-1,1,n)) calc(l-1,r);
if(in(r+1,1,n)) calc(l,r+1);
}else{
while(nd >= lmt){
if(!in(b[nd],l,r)){
l = min(b[nd], l), r = max(b[nd], r);
lmt = (2*n+1 - (r-l+1))/2;
}nd --;
}calc(l,r);
}
}
void Solve(){
n=rd();For(i,1,n) a[i]=rd(),b[a[i]]=i;
printf("%lld ",n<<1|1);
if(Gan.check0()) return Gan.Solve0();
int p = max_element(a+1,a+n+1)-a;
calc(p,p);
printf("%lld\n",ans);
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("guitar.in","r",stdin);
freopen("guitar.out","w",stdout);
int T=1;double Tim=clock();
while(T--) Solve();
return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}100分
#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i==)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
#define inn(x,l,r) (l<=x && x<=r)
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1012345;
bool ST;
int n,ans,a[N],b[N];
void calc(int p){
for (int i=1,j=0,l=n,r=1;i<=n;i++) {
while (j*2<=i) {
j++;
l=min(l,b[n-j+1]);
r=max(r,b[n-j+1]);
}
if (r-l+1<=i) {
int L=max(r-i+1,1ll),R=min(l,n-i+1);
if (L<=R) {
ans+=R-L+1;
}
}
}
}
void Solve(){
n=rd();For(i,1,n) a[i]=rd(),b[a[i]]=i;
printf("%lld ",n<<1|1);
int p = max_element(a+1,a+n+1)-a;
calc(p), printf("%lld\n",ans);
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("guitar.in","r",stdin);
freopen("guitar.out","w",stdout);
int T=1;double Tim=clock();
while(T--) Solve();
return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}
