Atcoder abc237

發表於 更新於 分類於 ， Disqus： 文章字數： 1.9k 所需閱讀時間 ≈ 6 分鐘
G(线段树,摘要表示)Ex(回文串,Dilworth定理,二分图)

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

G - Range Sort Query

给你一个1-N的排列

Q次操作, 每次指定区间排成指定升序/降序

问所有操作结束后,X的位置

范围

n 2e5

q 2e5

8s

1024mb

我的思路

先考虑特殊情况

X=1

那么只用持续跟踪它的位置就好了, 每次有覆盖的区间,计算新位置

而如果X=2

会发现, 每次排序与,1是否在其中有关, 维护量变成2个位置

这样下去3,就是3个位置

x就是x个位置

但其实一想, 整个排序,对X位置有影响的可以只考虑< X的个数, 或者说只考虑> x的个数

那么每次对含X的排序 = [l…r] 变成 < x的个数,X,> x的个数

啊不就是区间查询和连续区间修改

segment tree + lazy tag 就可以了?

代码

https://atcoder.jp/contests/abc237/submissions/34842993

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
93
94
95
96
97
98
99
100
101
102
103
104
#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;} // read


int a[200010];
struct node{
  int lazy = 0; // 0 no lazy, 1lazy 1, 2lazy2
  array<int,3> c = {0,0,0};
};

node seg[800010]; // seg[o] = []

array<int,3> add(const array<int,3> &a0,const array<int,3> &a1){
  return {a0[0]+a1[0],a0[1]+a1[1],a0[2]+a1[2]};
}

void build(int o,int l,int r){
  if(l == r){
    seg[o].c[a[l]]++;
    return;
  }
  build(SEG_L_CHILD);
  build(SEG_R_CHILD);
  seg[o].c = add(seg[SEG_L].c,seg[SEG_R].c);
}

void down(int o,int l,int r){
  if(seg[o].lazy == 0)return ;
  int v = seg[o].lazy;
  seg[SEG_L].lazy = v;
  seg[SEG_L].c = {0,0,0};
  seg[SEG_L].c[v] = (mid-l+1);

  seg[SEG_R].lazy = v;
  seg[SEG_R].c = {0,0,0};
  seg[SEG_R].c[v] = (r-mid);
  seg[o].lazy = 0;
}

array<int,3> query(int o,int l,int r,int ql,int qr){
  if(ql <= l && r <= qr) return seg[o].c;
  down(o,l,r);
  array<int,3> res = {0,0,0};
  if(ql <= mid) res = add(res,query(SEG_L_CHILD,ql,qr));
  if(qr >  mid) res = add(res,query(SEG_R_CHILD,ql,qr));
  return res;
}

void setRange(int o,int l,int r,int ql,int qr,int v){
  if(ql <= l && r <= qr) {
    seg[o].lazy = v;
    seg[o].c = {0,0,0};
    seg[o].c[v] = r-l+1;
    return ;
  }
  down(o,l,r);
  if(ql <= mid) setRange(SEG_L_CHILD,ql,qr,v);
  if(qr >  mid) setRange(SEG_R_CHILD,ql,qr,v);
  seg[o].c = add(seg[SEG_L].c,seg[SEG_R].c);
}

int find0(int o,int l,int r){
  if(l == r) return l;
  down(o,l,r);
  return seg[SEG_L].c[0]?find0(SEG_L_CHILD):find0(SEG_R_CHILD);
}

int main(){
  int n = read();
  int q = read();
  int x = read();
  rep(i,0,n) a[i] = read();
  rep(i,0,n) a[i] = a[i]==x?0: (a[i]<x?1:2); // <x:1,=x:0,>x:2
  build(SEG_ROOT);
  while(q--){
    int o = read();
    int l = read()-1;
    int r = read()-1;
    auto res = query(SEG_ROOT,l,r);
    if(o == 1){ // 1 0 2
      if(res[0]) setRange(SEG_ROOT,l+res[1]  ,l+res[1]  ,0);
      if(res[1]) setRange(SEG_ROOT,l         ,l+res[1]-1,1);
      if(res[2]) setRange(SEG_ROOT,r-res[2]+1,r         ,2);
    }else{ // 2 0 1
      if(res[0]) setRange(SEG_ROOT,l+res[2]  ,l+res[2]  ,0);
      if(res[1]) setRange(SEG_ROOT,r-res[1]+1,r         ,1);
      if(res[2]) setRange(SEG_ROOT,l         ,l+res[2]-1,2);
    }
  }
  printf("%d\n",find0(SEG_ROOT)+1);
  return 0;
}

ftiasch (摘要表示)

https://atcoder.jp/contests/abc237/submissions/30817031

对于连续的一段 只需要记录开头的位置和内容, 再配上map+lower_bound 即可, 相当于表示从 当前位置到下一个位置之间都是val

显然每次操作完后 不多于3个,

假设每次操作是对i个段, +t, +r

t是对原来的切割[0~2]

r是剩余的段个数[1~3]

总的操作代价是 (i+t+r)

对总体段的改变是 减少 (i-(t+r))个

有 sum(i-(t+r)) <= n

sum(i+(t+r)) == sum(i-(t+r) + 2(t+r)) <= n + 2(t+r)q <= n + 10q

均谈O(n+q)

Ex - Hakata

https://atcoder.jp/contests/abc237/tasks/abc237_h

小写字母的字符串S

选出尽量多的 回文子串 集合T, 问有最多有多少个满足

连续子串是回文串,且不是其它选中的T中的连续子串的回文串的子串

范围

|S| 200

2s

1024mb

我的思路

显然可以先插入#号来不用分类奇偶,以每个点为中心的最长串才有可能是答案

这样我们可以暴力n^2 得到n个候选回文串

问题变成说其中一个是否是另一个的子串

暴力 = n^3 ?

题解

结论1: S中的不同的 回文子串 的个数 $N \le |S|$

证明:

字符串s末尾增加一个字符(s1 = s+char(?)), 至多 产生一个之前不存在的回文串

若新增的字符未出现过, 则多了它自己

若该字符出现过, 那么本身不会是新的, 那么产生的是 [i0….n+1], [i1…..n+1], 这些以n+1结尾的 回文串

注意到 最小的i, 对应的[i….n+1] 包含了其余的[i…n+1]所以其余的都不会是新产生的.

因此一个字符串的不同回文串个数$\le |S|$ 得证

比如 A,B 都是C的子串,你可以选A,B不选C达到更多

所以看成把N个回文看成点,建立DAG,问选最多的点,让任意两点之间没有直接路径

而对于这个DAG,如果有 i->j,j->k,那么必然存在i->k,(传递闭包), 所以根据Dilworth定理, 问题变成最小路径覆盖(选最少的路径, 覆盖所有点)

DAG的选点互斥需要满足 i->j,j->k 则i->k也可以比较大小(存在偏需)

然后可以用二分图最大匹配来做

具体操作

  1. 求传递闭包就是如果i->j,j->k那么就要有i->k的边,(本题目本身处理时就有不需要额外求)
  2. 拆点成入点 出点, 变成二分图

因为每个点的出入度在二分图最大匹配中为1或0, 所以对应原拓扑图一定是多个链（匹配的方案一定对应原图的一个方案）

又因为可以看成原图每个点是一个链,每次连接就让链数量减一, 要尽可能多的减1

而这正好一个连接对应二分图的一个匹配, 所以

最小覆盖 = 点数 - 二分图最大匹配数

代码

https://atcoder.jp/contests/abc237/submissions/34871954

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i < (int)n; i++)
int read(){int r;scanf("%d",&r);return r;} // read

int vis[210]; // vis[右侧点]
int from[210]; // from[右侧点] = 左侧点
vector<string> a;
vector<int> p2[210];
bool dfs(int u,int now){ // bool 返回 0/1
  for(auto v:p2[u]) if(vis[v]!=now){ // 左侧u -> 右侧v
    vis[v]=now;
    if(from[v]==0 || dfs(from[v],now)) return from[v]=u;
  }
  return 0;
}
char s[210];
int main(){
  scanf("%s",s);
  int n = strlen(s);
  rep(i,0,n){ // 暴力n^3
    string t;
    rep(j,i,n){
      string t_ = t+=s[j];
      reverse(t_.begin(),t_.end());
      if(t==t_) a.push_back(t);
    }
  }
  sort(a.begin(),a.end(),[](const string&x,const string&y){return x.size()==y.size()?x<y:x.size()>y.size();});
  a.resize(unique(a.begin(),a.end()) - a.begin()); // 排序去重, 长度从大到小
  rep(i,0,a.size()) rep(j,i+1,a.size()) if(a[i].find(a[j]) != string::npos) p2[i+1].push_back(j+1);// 暴力 n^3?n^4?
  int ans = 0;
  rep(i,1,a.size()+1) ans+=dfs(i,i);
  printf("%d\n",(int)a.size()-ans);
  return 0;
}

总结

G

线段树数据结构,没啥难的

Ex

  1. 字符串与其不同回文串的个数关系 $\le |S|$ 这个性质看上去还是很神奇
  2. 偏序图中选两两无无法比较的点的最大点集的Dilworth定理
  3. 偏序图的最小链覆盖和二分图的关系

emmmmm 二分图可以只做一侧点的vis吗?

参考

官方题解

https://repub.eur.nl/pub/23112/EI2011-13.pdf

https://www.sciencedirect.com/science/article/pii/0012365X79901572