题解 CF1400D 【Zigzags】

发表于

考场上想到做法没调出来，自闭了。

题意

给定长度为 $n$ 的数组 $a$，询问有多少组 $(i,j,k,l)$ 满足：

  • $1\le i<j<k<l\le n$
  • $a_i=a_k$ 且 $a_j=a_l$

$n\le 3000$

$\operatorname{Sol}$

先看到这个数据范围，显然暗示着我们去寻找 $\Theta(n^2)$ 的做法，再不难猜测，做法应当是枚举四元组中的两个，再 $\Theta(1)$ 计算贡献。如果我们枚举 $i,j$，我们会发现很难处理 $k$ 和 $l$ 的相对位置关系，所以做法应当是枚举 $i,k$，这样 $j\in (i,k),l\in(k,n]$，达到了我们的预期。

我们在枚举 $i,k$ 的同时对 $(i,k)$ 区间和 $(k,n]$ 区间维护两个桶 $t1,t2$，显然此处的贡献为 $\sum t1_i\times t2_i$，如果在转移的同时更新桶，再计算贡献，发现这样做是 $\Theta (n^3)$ 的，考虑优化。可以发现，在转移过程中，一次 $k$ 的移动只会造成两个桶中分别一个元素的变化，也就是说，在计算贡献的 $\sum$ 中，一次转移最多伴随着两项值的变化，让总贡献直接更新即可。

时间复杂度 $\Theta(Tn^2)$。

$\operatorname{Code}$

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
#include <bits/stdc++.h>
using namespace std;
int a[3001], t1[3001], t2[3001];
int main (){
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)cin >> a[i];
        long long ans = 0;
        for (int i = 1; i <= n; i++){
            memset(t1, 0, sizeof(t1));
            memset(t2, 0, sizeof(t2));
            long long tmp = 0;//贡献
            for (int j = i + 1; j <= n; j++)t2[a[j]]++;
            for (int j = i + 1; j < n; j++){
                
                tmp -= t1[a[j]], t2[a[j]]--;//此处贡献变为t1[a[j]] * (t2[a[j]] - 1)
                if (a[i] == a[j])ans += tmp;
                tmp += t2[a[j]], t1[a[j]]++;//注意此处加上的贡献在下一个循环才是合法的
                                            //所以在计算对答案的贡献之后再更新
            }
        }
        cout << ans << endl;
    }
    return 0;
}
+ +