Educational Codeforces Round 131

發表於 更新於 分類於 ， Disqus： 文章字數： 971 所需閱讀時間 ≈ 3 分鐘
F(线段树,贡献变化)

CF tracker

Edu List

https://codeforces.com/contest/1701

F. Points

如果 i < j < k 且 k-i <= d 则 称作美丽

初始没有点, q次操作, 每次操作3种可能

  1. 增加一个点
  2. 删除一个点

保证 集合中不会有相同点

每次操作后 计算 美丽的三元组个数

范围

q 2e5

d 2e5

a[i] 点坐标 [1,2e5]

6.5 s

512 mb

我的思路

简单讲, 就是 选两个距离小于d的点作为首尾, 然后问它们之间其它点的个数 作为贡献, 的贡献和

维护

其实增加一个点, 和删除一个点, 并不会影响其它点的组合,

影响的 三元组一定和操作的这个点有关

如果它是 最小的

= sum_{l=2~d} count(i,i+l) * c[l]

如果暴力算, 需要 O(d)

如果它在中间

= sum_{l=1~d-1} count(i,i-l) * c[i+d-l]

也是O(d)

感觉 似乎可能按照sqrt(max{a}) 分块

分块 对于不在中间的情况还好, 因为 相当于计算 (i,i+d] 之间 的不同值的点对个数, 在一个块里 预计算了, 在不同块里, 通过前缀和 可以算掉,

问题是 当加入的/删除的 为中间点时, 那么要找的就是 i < point < k, 且 k-i <= d

不知道有啥办法搞

题解

没那么麻烦 甚至还要简单

和上面我想的一样, 注意到关键的 不会点重复, 所以如果我们选定左侧点, 那么j和k的选择 就是binom( [i+1..i+d] 中点的个数,2)

ans = sum_i有点 binom(count[i+1,i+d],2)

考虑增加点x, 那么就是 x-d ~ x-1 对应的count 都+1了

而binom(v+1,2) - binom(v,2) = v, 相当于增加count的和

还要增加 对于 点x 的统计

删除是对称的

v -> v-1 , binom(v-1,2) - binom(v,2) = v-1, 相当与减少 (减少以后v-1)的和

还要减少对于 点x 的统计

代码

https://codeforces.com/contest/1701/problem/F

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#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 SEG_ROOT 1,0,n-1
#define SEG_L (o<<1)
#define SEG_R (o<<1|1)
#define mid (l+r)/2
#define SEG_L_CHILD SEG_L,l,mid
#define SEG_R_CHILD SEG_R,mid+1,r

ll read(){ll r;scanf("%lld",&r);return r;}

const int n=200001;
struct SEG_NODE{
  ll s; // sum, [l..r]为起点(存在)的v的和
  ll v; // [+1...+d] 叶子:个数, 非叶子:lazy inc
  ll c; // [l..r] 点的个数
} seg[800010];
bool p[200010];

void down(int o){
  if(int v=seg[o].v){
    seg[SEG_L].v += v;
    seg[SEG_L].s += seg[SEG_L].c * v;
    seg[SEG_R].v += v;
    seg[SEG_R].s += seg[SEG_R].c * v;
    seg[o].v=0;
  }
}

SEG_NODE up(const SEG_NODE&l,const SEG_NODE&r){
  return SEG_NODE{l.s+r.s,0,l.c+r.c};
}

void add(int o,int l,int r,int ql,int qr,int v){
  if(ql<=l and r<=qr){
    seg[o].v += v;
    seg[o].s+=seg[o].c*v;
    return ;
  }
  down(o);
  if(ql <= mid) add(SEG_L_CHILD,ql,qr,v);
  if(qr >  mid) add(SEG_R_CHILD,ql,qr,v);
  seg[o]=up(seg[SEG_L],seg[SEG_R]);
}

void addp(int o,int l,int r,int x,int v){
  if(l==r) {
    seg[o].c+=v;
    seg[o].s=(ll)seg[o].v * seg[o].c;
    return ;
  }
  down(o);
  (x <= mid) ? addp(SEG_L_CHILD,x,v) : addp(SEG_R_CHILD,x,v);
  seg[o]=up(seg[SEG_L],seg[SEG_R]);
}

SEG_NODE sum(int o,int l,int r,int ql,int qr){
  if(ql <= l and r <= qr) return seg[o];
  down(o);
  if(qr <= mid) return sum(SEG_L_CHILD,ql,qr);
  if(ql >  mid) return sum(SEG_R_CHILD,ql,qr);
  return up(sum(SEG_L_CHILD,ql,qr),sum(SEG_R_CHILD,ql,qr));
}

int main(){
  int q=read();
  int d=read();
  ll ans=0;
  while(q--){
    int x=read();

    if(p[x]){ // 减少
      add(SEG_ROOT,x-d,x-1,-1);
      ans-=sum(SEG_ROOT,x-d,x-1).s; // 后取和
      ll cx=sum(SEG_ROOT,x,x).v; // x为最左
      ans-=cx*(cx-1)/2;
      addp(SEG_ROOT,x,-1);
    }else{ // 增加
      ans+=sum(SEG_ROOT,x-d,x-1).s; // 先取和
      add(SEG_ROOT,x-d,x-1,1);
      ll cx=sum(SEG_ROOT,x,x).v; // x为最左
      ans+=cx*(cx-1)/2;
      addp(SEG_ROOT,x,1);
    }
    p[x]=!p[x];
    printf("%lld\n",ans);
  }
  return 0;
}

总结

评分2500

F

唉, 这感觉一上来就往复杂的想, 其实还挺基础了, 不应该不会

参考

官方