Atcoder abc282

發表於 更新於 分類於 ， Disqus： 文章字數： 1.3k 所需閱讀時間 ≈ 4 分鐘
G(DP,前缀和)Ex(二分,分治)

https://atcoder.jp/contests/abc282/tasks

G - Similar Permutation

两个长n排列A,B

相似度为 相邻同增次数 + 相邻同减次数, (A[i+1]-A[i])(B[i+1]-B[i]) > 0

问 相似度为k的有序对 (A,B) 有多少个, mod p

范围

n 100

p [1e8~1e9]

4s

1024mb

我的思路

看这 n, 感觉有可能就要到4次方, 想一维度的排列,每次 从N-1到n, 就是考虑n的插入位置

但是两个序列的话

a0 a1 a2…..

b0 a1 b2…..

插入一个值, 会让后面的值平移, 增减关系会错位

变一变, f(k) = 至少k个位置增减关系一致, 那么ans = f(k) - f(k+1)

但这样也不知道怎么统计

因为

1 2 3, 假设定了第一个位置是增

那么

1-2 3

2-3 1

1-3 2

第二个位置并不是增 减 数量相等的

如果a和b在从n-1变到n时, 插入位置相同, 那么这个位置的左右增减都是相等的, 但是插入前可能相等可能不等,增量是1, 但不同怎么处理

再就是不要插入n, 而是末尾插入一个

f(len a, last a, len b, last b), 似乎可以搞?, 注意到两个len是相等的

插入 x, 等于 原来 [1…x-1] 不变, [x..n-1] 平移1变成[x+1,n]

f(len, last a, last b,同增减k)

f[n][a1][b1][k1] += f[n-1][a0][b0][k0] , k1 = k0+ bool( (a1 <= a0)^(b1 <= b0) )

这样状态是 O(n^4) 转移是 O(n^2) 一共O(n^6) 过不了

可能需要二维前缀和搞一搞?, 实际就是一条纵线 a1 = a0 和 b1 = b0 划分的

题解

恩 类似的 就是需要二维前缀和搞一搞

dp[长i][当前相似度j][k个大于Ai][l个大于Bi]

Ex - Min + Sum

给两个长n序列, A,B

问有多少 (l,r) 满足

min(A[l..r]) + sum(B[l..r]) <= S

范围

n 2e5

s 3e14

ai [0,1e14]

bi [0,1e9]

我的思路

当固定了l以后, 随着r增大, min(A[l..]) 非严格单调递减, sum(B[l..]) 非严格单调递增

这穿插着不知道怎么搞

但是 考虑l 时 算出了多个可行的r

那么 l 变成 l+1,

对于一个r, 如果原来 min = A[l], 那么 A[l1] + (B[l+1…r] = A[l] + B[l…r] + (A[l1]-A[l] - B[l]), 主要考察A[l1]-A[l] - B[l] 的大小,

对于一个r, 如果原来min != A[l], 那么 A[l1] + B[l+1..r] = A[l1]+B[l..r] - B[l] <= S 一定成立

所以l -> l+1 时, 从可行变成不可行的r一定是 被a[l] min覆盖了 A[l1]-A[l]-B[l] , 而 不可行变为可行的A[l1]-A[l]-B[l] < 0

题解

分治?!

考虑 统计 [L,R] 中的合法对

令 M为(L+R)/2 (中点)

然后 a[..m] 为 后缀min, a[m..] 为前缀min

考虑如何找 l \in [L,M], r \in [M,R] 的合法对

1
2
3
4
5
6
7
双指针 p=m, q=m
if a[p-1..m] >= a[m..q+1]:
  p = p-1
  统计 l=p, r\in [M,q] ?????
else
  q = q+1
  统计 l \in [p,M]
1
2
3
4
5
6
7
8
9
10
        m
1 3 5 7 9 8 6 4 2
        p q       (固定q)
      p . q       (固定p)
      p .   q     (固定q)
    p   . . q     (固定p)
    p . .     q   (固定q)
  p     . . . q   (固定p)
  p . . .       q (固定q)
p       . . . . q (固定p)

换句话说, 就是从中间向两边 扩散, 固定最小值, 另一半用二分, 这样就是 O(n (log n)^2)

不要选中点m, 而是选最小值m来划分, 这样 怎么保证复杂度呢

[L..l..m..r…R] 那么这时 每次选长度更小的枚举, 而另一侧用 二分找(因为min确定了)

这样 O(n (log n)^2)

代码

指定最小值的 https://atcoder.jp/contests/abc282/submissions/37530192

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
ll read(){ll r;scanf("%lld",&r);return r;}

ll ans=0;
ll s;
vector<pair<int,int>> to;
vector<ll> a,b,c;
void dc(int v, int l, int r) { // [l,r)
  if (v == -1) return;
  if (v-l < r-v) { // for 短的, 二分长的
    rep(i,l,v+1) ans += upper_bound(begin(c)+v+1,begin(c)+r+1,s-a[v]+c[i])-begin(c)-(v+1);
  } else {
    rep(j,v+1,r+1) ans += v+1-(lower_bound(begin(c)+l,begin(c)+v+1,-s+a[v]+c[j])-begin(c));
  }
  dc(to[v].first,l,v);
  dc(to[v].second,v+1,r);
};

int main() {
  int n=read();
  s=read();
  a=vector<ll>(n);
  b=vector<ll>(n);
  c=vector<ll>(n+1);
  rep(i,0,n) a[i]=read();
  rep(i,0,n) b[i]=read();
  rep(i,0,n) c[i+1] = c[i]+b[i]; // b的前缀和

  a.push_back(-1);
  to=vector(n+1,pair<int,int>(-1,-1)); // 记录最小值 [左侧切割的最小值, 右侧切割的最小值)
  {
    stack<int> st; // 单调增栈
    rep(i,0,n+1) {
      int l = -1; // 最后一个出栈的
      while (st.size() && a[st.top()] > a[i]) {
        int j = st.top();
        st.pop();
        to[j].second = l;
        l = j;
      }
      to[i].first = l;
      st.push(i);
    }
  }

  dc(to[n].first,0,n);
  printf("%lld\n",ans);
  return 0;
}

总结

G

dp + 前缀和

Ex

emmm, 题做少了, 这种固定最小值(不论直接选还是从中间双指针), 事后看起来就很自然且无脑啊

参考

官方题解