题解：P10798 「CZOI-R1」消除威胁

xiaozhao_ · 2024-07-22 10:33:34 · 题解

猜你想要：更好的阅读体验。

题目大意:

给出一个有 n（1 \le n \le 5 \times 10^5）个整数的序列 A，我们可以对他进行任意次将 A_i 变成 -A_i 的操作，求最少的区间 [l,r] 满足 A_l=A_r 且 A_l（或者说 A_r）是区间 [l,r] 中最大的。

比赛时 AC 过程：

骗分思路（10 pts）：

读完题后，暂时没有什么思路。看到数据范围，突然发现：Subtask #4 中 |A_i| 均相等！这不妥妥的给我们骗分用的。

推导：

假设现有一个满足 |A_i| 均相等的序列 A。

如果 A_i 均为正数（或负数），那么具有”威胁“的区间的数量是 \sum_{i = 1}^{n} i（或者说是 \frac{n(n+1)}{2}）。

那么我们可以很容易地想到对于 A 来说，想要得到最少具有"威胁“的区间,我们需要让 \frac{n}{2} 个数字变成正数，让剩下的数变成负数。

寻找规律：

假设 k=|A_i|。

1. 当 n=1 时，由于题目规定了 l<r 所以”威胁“总数为 0。
2. 当 n=2 时，根据上面推导的方法，将 A 变为 \{k,-k\}，”威胁“总数为 0。
3. 当 n=3 时，将 A 变为 \{k,k,-k\}，”威胁“总数为 1。
4. 以此类推，当 n=4 时，”威胁“总数为 2；当 n=5 时，”威胁“总数为 3；当 n=6 时，”威胁“总数为 6；当 n=7 时，”威胁“总数为 9；当 n=8 时，”威胁“总数为 12。

将上面得出的”威胁“总数放在序列 F 中，得 \{0,0,1,2,4,6,9,12\}。把每两项之间的差值求出，得 \{0,1,1,2,2,3,3\}，规律这不就来了吗。根据规律我们可以列出递推式：F_i=F_{i-1}+\frac{i-1}{2}。

骗分代码：

#include<bits/stdc++.h>
using namespace std;
const int N=500860;
int n,t; //t表示 (i-1)/2 的值 
long long f[N];
int main(){
    cin>>n;
    for(int i=3;i<=n;i++){
        if(i&1) t++; //当i为奇数（也就是 (i-1)/2 的值会增加时）t++
        f[i]=f[i-1]+t; //上面推导的 f[i]=f[i-1]+(i-1)/2 
    }
    cout<<f[n]; 
    return 0;
}

未优化的正解思路（40 pts）：

1. 根据上面骗分总结出的序列 F 的思路可以发现，F_i 并不只适用于 |A_i| 均相等的情况，还适用于在具有”威胁“的区间 [l,r] 中所有数的绝对值中与 |A_l| 相等的总数。因此，对于一个数 A_i，我们只需用变量 cnt 记录以 i 为起点到最后一个绝对值与 |A_i| 相等的区间中的所有绝对值与 |A_i| 相等的总数，再让答案加上 F_{cnt}，最后就得出了最终答案。
2. 考虑到题目说 |A_l| 必须是区间 [l,r] 中最大的，所以当遇到 |A_i|>|A_l| 时，我们需要停止寻找后面绝对值与 |A_l| 相等的数字。
3. 由于我们可以进行任意次的将 A_i 变成 -A_i，并且为了方便后面的比大小，所以我们统一将 A_i 变成 |A_i|。

   未优化的正解代码：

#include<bits/stdc++.h>
using namespace std;
const int N=500860;
int n,t,a[N];
long long ans,f[N];
bool v[N]; //v用来标记已用过的 a[i] 防止重复计算。
int main(){
    cin>>n;
    for(int i=3;i<=n;i++){
        if(i&1) t++;
        f[i]=f[i-1]+t;
    }
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        a[i]=abs(a[i]); //如上面第 3 点所说。
    }
    for(int i=1;i<=n;i++){
        if(!v[i]){
            int cnt=1;
            for(int j=i+1;j<=n;j++){
                if(a[j]>a[i]) break; //如上面第 2 点所说。
                if(a[i]==a[j]) cnt++,v[j]=1;
            }
            ans+=f[cnt];
        }
    }
    cout<<ans;
    return 0;
}

优化的正解思路（AC）：

序言（可跳过）：

本来写完上面未优化的正解 （我比赛时不知到这是正解） 正准备关闭 luogu，打开 steam，享受美好人生的。但看到这个记录详情只 TLE 了两个点,并且还分别是最后两组时，我心中突然涌现出一股力量，这股力量告诉我，这道题我可以 AC！

优化方法：

1. 我们可以用一个数组储存与 A_i 相同的下一个数字的位置，这样就可以省去遍历一遍序列 A 的时间。
2. 因为我们不再遍历序列 A，所以我们需要快速求出区间 [l,r] 中的最大值，以便我们判断 A_l 是否是[l,r] 中的最大值。这里我推荐用 st 表来求。

屏幕前的洛友不会 st 表？讲解 + 模板题迅速入门！

比赛 AC 代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=500860;
unordered_map<int,vector<int> > m; //m[a[i]] 用来记录与 a[i] 相同的下一个数字的位置。
unordered_map<int,int> l; //记录 m[a[i]] 用到哪了，与之前 v 的作用相似。
//不开 unordered_map 会炸(MLE 或 TLE)。
int n,t,a[N],s[N][20]; //log2(500000)大约是19。
LL ans,f[N];
inline int qy(int l,int r){ //查询区间 [l,r] 的最大值。
    int t=log2(r-l+1);
    return max(s[l][t],s[r-(1<<t)+1][t]);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        a[i]=abs(a[i]);
        m[a[i]].push_back(i); //记录 m[a[i]] 的位置。
    }
    for(int j=0;j<20;j++) //st 表预处理。
        for(int i=1;i+(1<<j)-1<=n;i++)
            if(!j) s[i][j]=a[i];
            else s[i][j]=max(s[i][j-1],s[i+(1<<j-1)][j-1]);
    for(int i=3;i<=n;i++){
        if(i&1) t++;
        f[i]=f[i-1]+t;
    }
    for(int i=1;i<=n;i++){
        int cnt=0,j=l[a[i]]; //j 记录 m[a[i]] 用到哪了。
        for(;j<m[a[i]].size();j++){
            if(qy(i,m[a[i]][j])>a[i]) break; //判断 a[i] 是否是最大的。
            else cnt++;
        }
        l[a[i]]=j; //记录 m[a[i]] 用到的位置。
        ans+=f[cnt];
    }
    cout<<ans;
    return 0;
}

AC 喽ヾ(≧▽≦*)o，完结撒花。

本题的 AC 过程：

序言（还是可跳过）：

第二天起来一看，这道题进题库了，真的太好了，打比赛还送 AC 率。一交上去，WA 了两个点,仅仅 90pts？一看题目，改了一个设定，即规定了 0=-0（昨天规定 0\ne-0），又被背刺了啊(っ °Д °;)っ。

处理 0 的情况：

因为 0=-0，所以以 0 为左右端点的区间中具有”威胁“的区间的数量是 \sum_{i = 1}^{n} i（或者说是 \frac{n(n+1)}{2}），其递推式为 F2_i=F2_{i-1}+i-1。

本题 AC 代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=500860;
unordered_map<int,vector<int> > m;
unordered_map<int,int> l;
int n,t,a[N],s[N][20];
LL ans,f[N],f2[N]; //f2 专门用来处理 0 的情况。
inline int qy(int l,int r){
    int t=log2(r-l+1);
    return max(s[l][t],s[r-(1<<t)+1][t]);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        a[i]=abs(a[i]);
        m[a[i]].push_back(i);
    }
    for(int i=3;i<=n;i++){
        if(i&1) t++;
        f[i]=f[i-1]+t;
    }
    for(int i=2;i<=n;i++)
        f2[i]=f2[i-1]+i-1; //如题推导的左右端点为 0 的情况。
    for(int j=0;j<20;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            if(!j) s[i][j]=a[i];
            else s[i][j]=max(s[i][j-1],s[i+(1<<j-1)][j-1]);
    for(int i=1;i<=n;i++){
        int cnt=0,j=l[a[i]];
        for(;j<m[a[i]].size();j++){
            if(qy(i,m[a[i]][j])>a[i]) break;
            else cnt++;
        }
        l[a[i]]=j;
        if(!a[i]) ans+=f2[cnt]; //特殊情况特殊对待ψ(｀∇´)ψ。
        else ans+=f[cnt];
    }
    cout<<ans;
    return 0;
}

后序：题解有界，帮助无限，希望这篇题解可以帮助屏幕前的你ヾ(≧▽≦*)o。