ZOJ 4003 Distance双指针维护区间

传送门：https://zoj.pintia.cn/problem-sets/91827364500/problems/91827370154

题意

对于两个长度相同的区间a和b，如果$\suma_i-b_i^p\leq V$，则成这两个区间为good 区间. 给出两个长度相同的数列，在这两个数列中分别选择两个区间，存在多少个good区间。

思路

因为$\suma_i-b_i^p$有绝对值，所以每增加一个值，都会增加。 假设我们找到一个区间$[l1,r1]、[l2,r2]$，则$l\in [l1,r1]，l’\in [l2,r2]$都是可以的。

所以我们可以枚举区间起点，然后计算终点，最后维护区间，更新和统计答案即可。

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
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
##include "bits/stdc++.h"

using namespace std;

typedef long long ll;

ll quick_pow(ll a, ll b) {
    ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}

void solve() {
    int _; cin >> _;
    while(_--) {
        int n; ll V, p;
        cin >> n >> V >> p;
        vector<ll> x(n + 10);
        vector<ll> y(n + 10);
        for(int i = 1;i <= n; i++) cin >> x[i];
        for(int i = 1;i <= n; i++) cin >> y[i];
        ll ans = 0;
        for(int len = 0;len <= n - 1; len++) { // 枚举指针距离
            int l1 = 1, r1 = 1; // a
            int l2 = 1 + len, r2 = 1 + len; // b
            ll cnt = quick_pow(abs(x[l1] - y[l2]), p);
            while(r2 <= n) { // 先让b动区间
                if(cnt <= V) {
                    ans += r1 - l1 + 1;
                    r1++;
                    r2++;
                    cnt += quick_pow(abs(x[r1] - y[r2]), p);
                }
                else {
                    cnt -= quick_pow(abs(x[l1] - y[l2]), p);
                    l1++;
                    l2++;
                    if(l1 > r1) {
                        r1++;
                        r2++;
                        cnt += quick_pow(abs(x[r1] - y[r2]), p);
                    }
                }
            }
            if(len == 0) continue;
            l1 = 1 + len; r1 = 1 + len;
            l2 = 1; r2 = 1;
            cnt = quick_pow(abs(x[l1] - y[l2]), p);
            while(r1 <= n) {
                if(cnt <= V) {
                    ans += r2 - l2 + 1;
                    r1++;
                    r2++;
                    cnt += quick_pow(abs(x[r1] - y[r2]), p);
                }
                else {
                    cnt -= quick_pow(abs(x[l1] - y[l2]), p);
                    l1++;
                    l2++;
                    if(l2 > r2) {
                        r1++;
                        r2++;
                        cnt += quick_pow(abs(x[r1] - y[r2]), p);
                    }
                }
            }
        }
        cout << ans << endl;
    }
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/04/08/zoj-4003-distance/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！