P11670 [USACO25JAN] Cow Checkups S 题解

· · 题解

P11670 [USACO25JAN] Cow Checkups S 题解

Preface

这场太难了。本来以为进金稳了，结果前两题做出来之后剩 45 分钟第三题愣是第一个点都没拿到。650 分数线也太高了吧。

这道题还是有一些思维的，非常 USACO。

Problem statement

P11670。

Solution

首先面对这种每个区间的贡献求和的问题，套路就是考虑每一个位置对哪些区间做贡献。

这道题也不例外， 对于原序列里的第 i 个位置，种类为 a_i，发现它能做出贡献当切仅当它被调换后的位置 j 有 a_i = b_j。 此时便有了第一个思路， 对于 a 数组中的每一个位置，枚举 b 数组中所有种类和它相同的位置，并记录有几个区间会导致翻转后这两个位置重合，贡献加一。

这种思路对于随机生成数据的前几组测试数据没问题，但是对于后几个小问，只有几个种类时复杂度可达 n^2。

如果想要优化需要找到一种方法，能够迅速把所有符合条件的 j 的贡献和加起来。想到用类似前缀和的方式，因为对于一个 i 之前的 j，它们两个会对 \min(j, n - i + 1) 个区间做出贡献，对总和就加了这么多。

也就是说对于一个种类 x 可以从左往右扫并把目前出现的所有 b_j = x 的 j 放进一个数组记录起来，同时还维护它们的和 sum。

扫到一个 a_i = x 就给答案加上 sum，除非 n - i + 1 < 目前最大的 j，如果是的话以后再扫到 b_j = x 就不再计入 sum += j 了，而是 cnt += 1，这样以后每次再碰到一个 a_i = x 就是给答案加上 sum，和 cnt \cdot (n - i + 1)。而且还要记得更新我们用来记录所有 b_j = x 的 j 的那个数组。具体就是从后往前如果这个 j 小于了 n - i + 1 就把它从 sum 中减去并把 cnt 加一，因为这个 i 都有 (n - i + 1) 比它大，以后的 i 也一定满足。

注意这样扫完一遍我们只记录了每个 i 和他之前的 j 的贡献，因此还要倒着扫一遍，注意若出现 a_i = b_i 不要算两遍导致多算。

总体复杂度能优化到 O(n) 主要靠的是前缀和和单调性。

Code

/*
yes, 1h 20min
*/
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("O3,unroll-loops")
//you may choose to use the line above
//it doesn't work on luogu though
#define int long long
//memset(f, 0x3f, sizeof f);
//memset(f, 0, sizeof f);
//static_cast<long long>(    )强制转换
//int pos = lower_bound(a + 1, a + n + 1, x) - a;
//that finds the first greater than or equalto x
//pos - 1 = the greatest that's <= x;
//当降序时需要加greater<int>(), 返回 = first that's <= x
//unique(a + 1, a + n + 1) - a; 去重
//去重前必须先排序
//next_permutation(a + 1, a + n + 1)
//return 1 if it exist, 0 otherwise.
//after calling the function
//a would already be the nextpermutation
//double stores 1e308, 12 digits percision
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
void write(int x){
    if(x < 0){putchar('-'); x = -x;}
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}//for outputting __int128
struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        // Hash the first element
        size_t hash1 = hash<T1>{}(p.first);
        // Hash the second element
        size_t hash2 = hash<T2>{}(p.second);
        // Combine the two hash values
        return hash1
               ^ (hash2 + 0x9e3779b9 + (hash1 << 6)
                  + (hash1 >> 2));
    }
};
//unordered_map<pair<int, int>, int, hash_pair> m;
/*
struct edge{
    int x, y;
    const bool operator<(const edge &a) const{
priority queue is different, descending is <, ascending is >.
while the function name doesn't change still <
        if(x != a.x)return x<a.x;
        //if you're not writing the else, don't write the if!!!!!!
        //cuz if you do, the function might not return anything!!!
        else return y < a.y;
        //always remember to write the ELSE!!!!!!!
    }
} a[M];
struct node{
    int x, y;
}a[100005];
int cmp1(node &u, node &v){//for sort
    if(u.x != v.x)return u.x < v.x;
    else return u.y < v.y;
}
结构体排序
*/
int cmp(int &x,int &y){//for sort
    return x>y;
}
int n, a[500005], b[500005], sum[500005], ans;
//sum[i] = the sum of the coordinates of all occurence of 
//breed i in b up to right now
int la[500005], cnt[500005], exc[500005];
//la is the last in array A
vector<int> pre[500005];
signed main(){
    cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
        exc[i] = 0;
        //havn't exceeded yet
    }
    for(int i = 1; i <= n; i++){
        cin>>b[i];
    }
    for(int i = 1; i <= n; i++){
        if(exc[b[i]]){
            //i exceeded (n - j + 1) for the last j where
            //a[j] == b[i]
            cnt[b[i]]++;
        }else{
            //currently all a[i]s in b are more restrictive
            //then a[i]         
            pre[b[i]].push_back(i);
            sum[b[i]] += i;
        }

        while(pre[a[i]].size() && pre[a[i]].back() > (n - i + 1)){
            exc[a[i]] = 1;
            sum[a[i]] -= pre[a[i]].back();
            //the last one exceeded, disqualified from sum and
            //is now a part of cnt
            pre[a[i]].pop_back();
            cnt[a[i]]++;
        }
//      cout<<i<<" "<<sum[a[i]] + cnt[a[i]] * (n - i + 1)<<endl;
        ans += sum[a[i]] + cnt[a[i]] * (n - i + 1);
        //cnt of the previous bs are > (n - i + 1) so 
        //they're no longer in sum, but counted as cnt
    }
    for(int i = 1; i <= n; i++){
        exc[i] = 0;
        cnt[i] = 0;
        sum[i] = 0;
        while(!pre[i].empty())pre[i].pop_back();
    }
//  cout<<endl;
    for(int i = n; i >= 1; i--){
        //reverse, so can't process b first otherwise if
        //a[i] == b[i] those pair will be counted twice
        //foward and backwards
        while(pre[a[i]].size() && pre[a[i]].back() > i){
            exc[a[i]] = 1;
            sum[a[i]] -= pre[a[i]].back();
            pre[a[i]].pop_back();
            cnt[a[i]]++;
        }
//      cout<<i<<" "<<sum[a[i]] + cnt[a[i]] * i<<endl;
        ans += sum[a[i]] + cnt[a[i]] * i;
        if(exc[b[i]]){
            cnt[b[i]]++;
        }else{
            pre[b[i]].push_back(n - i + 1);
            sum[b[i]] += (n - i + 1);
        }
    }
    //above counted the number of regions that will make
    //cow i work if the region include cow i, now we have
    //to count what if the region doesn't include cow i
    //but a[i] == b[i]?
    for(int i = 1; i <= n; i++){
        if(a[i] != b[i])continue;
        //on the left, it's 1 + ... + (i - 1)
        //on the right it's 1 +... + (n - i)
        ans += (1 + (i - 1)) * (i - 1) / 2;
        ans += (1 + (n - i)) * (n - i) / 2;
    }
    cout<<ans<<endl;
    return 0;
}
/*
8
1 2 2 1 2 1 2 2
1 2 1 1 2 1 2 1
*/

赛事代码，略丑。