YeXiaoRain Blog(hexo的搜索高亮会破坏latex)

發表於 更新於 分類於 ， Disqus： 文章字數： 2.1k 所需閱讀時間 ≈ 7 分鐘
F(无向图,图,奇数环,偶数环,树上差分)

题目

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

给一个连通无向图,n点,m 边

点覆盖: (所有边至少一个点属于点集

lenient点覆盖: 是点覆盖,且至多一条边两个点都在点集中

找出一个 lenient点覆盖

范围

t 1e4

n 1e6

5s

512MB

我的思路

首先 如果能黑白染色,成功,那么也就是每个边一端黑一端白, 全选黑或全选白都是一个答案

如果 黑白染色出现冲突,那么这两个点一定在一个奇环上

也就是这个奇环上存在两个点都是黑色, 最可以先把这个环上的边全部当作不存在,重新做染色,如果能成功, 计算这个环上同一个并查集点的颜色关系,

如果两两都不在同一个集合中那么说明拆了环都是独立的部分,那么任意染黑白即可

如果存在 a—–b 同集合中

a,b 同色 , [a..b]个数奇数的一半一定是黑白间隔

a,b 异色 , [a..b]个数偶数的一半一定是黑白间隔

换句话说, 其实原图去掉那个两个点都在集合中的边, 剩下的满足黑白染色,现在则是看哪些确定可以连起来

过程中检查冲突

如果剩余还有没连的 任选一个作为分割即可

但是 实现上能找环但如何找奇环

独立染色可以写,但合并时如何实现?

题解

前面几段和我想的一样, 奇偶黑白染色, 也就是需要在奇数环上剪断一条边,让整个染色合法

这里主要是 对无向图做dfs建立树

那么出现环的时候就是子节点指向父节点的时候

我们在dfs过程中黑白染色,那么出现回边时根据染色就可以知道它是奇环还是偶环,

如果我们统计了每条边出现在我们找到的奇环上的次数,和偶环上的次数,那么 如果一条边出现在奇数环上次数等于所有奇环次数,偶数环次数为零,那么删除这条边即可(可能有多个满足,任意删除一条)

// 必要性proof见下面, 充分显然

所以接下来就是当发生回环时,如何统计边在奇环偶环上出现次数了,如果直接对边计数,那么复杂度就过不了

树上差分, cnt[id]表示边id到根的所有边都 进行了+cnt[id],这样 当有点u到点v的回边时,就 cnt[faedge[u]]++,cnt[faedge[v]]–, 对于不在树上的回边edge[id] = {u,v}不需要差分直接统计, cnt[id]++

最后统计完后整理具体次数

然后找满足的边拆掉,再染色即可(注意拆掉边两端需要是黑色

性质证明

这里 显然的是 如果是两端同色的点, 那么它一定在所有奇环中,不在所有偶环中

也就是必要性显然

如果我们枚举了所有的环,那么拆掉它,所有奇数环也被拆掉了, 所以充分性也成立

问题是上面的实现 并没有枚举所有的环,枚举的只是树边+一条回边的所有环, 而环可能是由多条回边构成的

引理1: 如果环A和环B的一部分拼成环C,那么ABC中要么全是偶环,要么其中两个是奇环,

(这里拼成的意思是 A 和 B 有共用的一条链, C= (A-共用链)+(B-共用链)

那么要证明的是两部分, 这个两端同色的边也在未统计到的多回边的奇数环中,不在未统计到的多回边偶数环中

如果它(两端同色的边)不在未统计到的多回边奇数环中

那么这个环H(奇,回边=n) 可以拆成一个H1(奇,回边n-1) + H(偶,回边1)

因为H(偶,回边1) 我们一定计算到了, 只能递归下降, 且不会在 它们两的重复边上,因为它不在偶环上

那么这个环H(奇,回边=n) 可以拆成一个H1(偶,回边n-1) + H(奇,回边1)

因为H(奇,回边1) 我们一定计算到了 所以它在奇数环中

综上它一定在 未统计到的多回边奇数环中

如果它在未统计到的多回边偶数环中

那么这个环H(奇,回边=n) 可以拆成一个H1(偶,回边n-1) + H(偶,回边1)

它一定不在 H(偶,回边1) 中, 所以递归下降,且它也不在 两个环共用的边上

那么这个环H(偶,回边=n) 可以拆成一个H1(奇,回边n-1) + H(奇,回边1)

注意到上述结论, 这个边一定在这两个环里都有,因此这个边在它们重复的边上而不在偶环里

因此 得证

代码

https://codeforces.com/contest/1680/submission/158000410

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i = (a);i<(b);i++)
#define all(v) (v).begin(),(v).end()
const int N = 1000000;
int n,m;
int odd; // 奇环个数
int cnt0[N+10]; // cnt0[边]偶环个数，
int cnt1[N+10]; // cnt1[边]奇环个数，
int c[N+10]; //c节点颜色，
bool vis[N+10]; // dfs中访问过, 多次复用
int fe[N+10]; //fe父边
// 读入
pair<int,int> e[N+10]; // [边] = {点id,点id}
vector<pair<int,int>> G[N+10]; // [点] = 数组 {点id,边id}
//二分图染色同时找环
void dfs(int u,int p/*父边*/,int cl /*颜色*/ ) {
  c[u]=cl;
  vis[u]=1; // 管的当前到根的链上是否有, 减少重复计算 简化差分统计
  fe[u]=p;
  for(auto [v,id]:G[u]){
    if (id==p)continue;
    if (c[v]==-1){ // 未访问过
      dfs(v,id,cl^1);
    } else if(!vis[v]){ // 非父节点
      continue;
    } else if (c[v]==(cl^1)) { //偶环
      cnt0[id]++; // 不在树上的回边
      cnt0[p]++; // 树上边 差分统计 表示这个边到根的次数都+1
      if(~fe[v])cnt0[fe[v]]--; // 这个边到根的次数都-1
    } else { // if (c[v]==cl) {//奇环
      odd++; // 奇环个数
      cnt1[id]++;
      cnt1[p]++;
      if(~fe[v])cnt1[fe[v]]--;
    }
  }
  vis[u]=0;//回溯时撤销访问标记
}
// 整理差分数组，得到每条边的计数, 只用处理树边,递归, 不用处理非树的回边
void dfs2(int u) {
  vis[u]=1;
  for(auto [v,_]:G[u]){
    if (vis[v]) continue;
    dfs2(v);
    if (fe[u]!=-1&&fe[v]!=-1){
      cnt0[fe[u]]+=cnt0[fe[v]];
      cnt1[fe[u]]+=cnt1[fe[v]];
    }
  }
}
void dfs3(int u,int cl) { //二分图染色
  c[u]=cl;
  for(auto [v,_]:G[u]){
    if (c[v]!=-1) continue;
    dfs3(v,cl^1);
  }
}
void run(){
  // 一系列初始化
  odd=0;
  scanf("%d %d",&n,&m);
  rep(i,0,n) G[i].clear();
  fill(cnt0,cnt0+m+3,0);
  fill(cnt1,cnt1+m+3,0);
  fill(c,c+n+3,-1);
  fill(vis,vis+n+3,0);
  // 读入
  rep(i,0,m){
    int u,v;
    scanf("%d %d",&u,&v);
    e[i]={--u,--v};
    G[u].pb({v,i});
    G[v].pb({u,i});
  }
  dfs(0,-1,0); // 以0 为根染色0搜索
  // 整理树上差分数组 变成每个边的统计
  fill(vis,vis+n+3,0);
  dfs2(0);
  int id=-1;
  if (odd) {//存在奇环
    rep(i,0,m){
      // 需要完全相等 所有已知奇环都覆盖了它, 且没有偶环覆盖了它, proof? 必要性显然, 充分性呢?
      if (cnt1[i]==odd && cnt0[i]==0) {
        id = i; // 任选一条
        break;
      }
    }
    if (id == -1) {
      printf("NO\n");
      return;
    }
    //删边
    auto [u,v] = e[id];
    sort(all(G[v]));
    sort(all(G[u]));
    G[u].erase(lower_bound(all(G[u]),make_pair(v,-1)));
    G[v].erase(lower_bound(all(G[v]),make_pair(u,-1)));
  }
  // 再次染色
  fill(c,c+n+3,-1);
  dfs3(0,1);
  int f=(id==-1?0:c[e[id].first]^1); //保证被删边的端点颜色为1
  printf("YES\n");
  rep(i,0,n){
    printf("%d",c[i]^f);
  }
  printf("\n");
}
int main() {
  int T;
  scanf("%d",&T);
  while(T--)run();
  return 0;
}

// 1-2-3-4,3-1,4-1
// 奇边切 3-1在回边上
//
// 1-2-3-4-5, 3-1, 5-1
//
// 奇边切 1-2或2-3,在树边上
//

总结

知识点

无向图 = dfs -> 树+回边

而一部分无向图的环 = 多个树边+一条回边? 也可能由回边组成的环

树上差分 = 记录当前点到根的所有边的统一操作,如+1/-1

学了一手fill()函数,看起来很好用啊

然后 无向图 树上dfs, 的父边而不是父点 dfs(int u,int fe /*father edge*/)

参考

官方

csdn 修复了一些越界和等式操作, 修改了部分变量和包裹逻辑,整体

發表於 更新於 分類於 Disqus： 文章字數： 285 所需閱讀時間 ≈ 1 分鐘

set+lower_bound

http://www.cplusplus.com/reference/algorithm/lower_bound/

On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average.

set不支持随机访问,所以std::lower_bound 用在set上就不再是log级别了, 而是均摊n级别了,所以要用set::lower_bound而不是std::lower_bound

动态开点线段树

一般来说 空间够常见是开4N大小

但是如果空间很大但是点是离散的又需要在线处理(不能离线离散化)的情况

每个点记录左右节点+lazytag+没有节点要访问时,动态开点idx, 查询时对于没有开点的直接返回空,而不是开点

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
int idx = 0;

// N 按照预估点数而不是 l r 的范围了
int lc[N]; // 点的左子点
int rc[N]; // 点的右子点

void update(int &o,int l,int r,...){
  if(!o) o = ++idx; // 动态开点
  if(l == r){
    // ...
    return ;
  }
  update(lc[o],l,mid,...);
  update(rc[o],mid+1,r,...);
  // ...
}

... query(int o,int l,int r,int ql,int qr){
  if(!o){ // 查询不用创建点
    //....
    return 空状态;// 
  }
  if(ql <= l && r <= qr){ // [ql.. [l..r].. qr]
    // ...
    return //;
  }
  auto resl = query(lc[o],l,mid,ql,qr);
  auto resr = query(lr[o],mid+1,r,ql,qr);
  return ...;
}



發表於 更新於 分類於 Disqus： 文章字數： 1k 所需閱讀時間 ≈ 3 分鐘

比赛总结

比赛id 11200

B:

数组空间没开够等未定义行为,不会像Codeforces报overflow等,而是默认执行报WA.

D:

TLE+WA 只会报WA

竞赛图不能创造大小为2的scc

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
/**
 * @author      : cromarmot (yexiaorain@gmail.com)
 * @file        : D
 * @created     : 星期五 5月 13, 2022 20:35:36 CST
 */

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (int i=a;i<n;i++)

// 竞赛图 任意不同两点间都有恰好一条单向边
int n,m; // n 1e5, m 2e5
vector<int>p2[100010];

// scc -> 成链?

class Tarjan{
  vector<int> low;
  vector<int> dfn;
  stack<int> stk;
  vector<int> res;
  int n;
  int id = 0;
  void scc(int v) {
    low[v] = dfn[v] = ++id;
    stk.push(v);
    for(auto w:p2[v]){
      if(!dfn[w]){ // 未访问过
        scc(w);
        low[v] = min(low[v],low[w]);
      } else if(!res[w]){ // 访问过但没有结果(在栈中)
        low[v] = min(low[v],dfn[w]);
      }
    }
    int u;
    if(low[v] == dfn[v])  {
      do{
        res[u = stk.top()] = v;
        stk.pop();
      }while(u != v);
    }
  }
public:
  Tarjan(int SZ):n(SZ){
    low = vector<int>(n+1,0);
    dfn = vector<int>(n+1,0);
    stk = {};
    res = vector<int> (n+1,0);
  }
  vector<int> calc(){
    rep(i,1,n+1){
      if(!res[i]){
        scc(i);
      }
    }
    return res;
  }
};

vector<int> p3[100010];
int du[100010];

void work(){
  scanf("%d %d",&n,&m);
  Tarjan tarjan(n);
  rep(i,1,n+1){
    p2[i] = {};
    p3[i] = {};
    du[i] = 0;
  }
  rep(i,0,m){
    int u,v;
    scanf("%d %d",&u,&v);
    p2[u].push_back(v);
  }
  // a->b / b->a 至少满足一条
  // scc 成链? 唯一拓扑顺序
  vector<int> num = tarjan.calc(); // scc 联通分量 标识
  vector<int> sccsz(n+1,0);
  rep(i,1,n+1){
    sccsz[num[i]]   ++;
  }
  rep(i,1,n+1){
    if(sccsz[i] == 2){
      // 竞赛图不能创造大小为2的scc!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
      printf("NO\n");
      return ;
    }
  }

  // rep(i,1,n+1){
  //   printf("scc: %lld: %d\n",i,num[i]);
  // }
  // 转化为联通分量关系
  rep(i,1,n+1){
    for(auto item:p2[i]){
      if(num[i] == num[item])continue;
      p3[num[i]].push_back(num[item]);
    }
  }
  rep(i,1,n+1){
    if(num[i] != i)continue;
    sort(p3[i].begin(),p3[i].end());
    int itr = 0;
    rep(j,0,(int)p3[i].size()){
      if(j==0 || p3[i][j] != p3[i][j-1]){ // 去重
        p3[i][itr++] = p3[i][j];
        // i -> p3[i][j]
        du[p3[i][j]]++; // 入度
      }
    }
    p3[i].resize(itr);
  }
  // 拓扑 联通分量中 唯一顺序
  // 入度为0
  vector<int> d0;
  rep(i,1,n+1){
    if(num[i] != i)continue;
    if(du[i] == 0)d0.push_back(i);
  }
  while(d0.size()) { // == 1
    if(d0.size() > 1){
      printf("NO\n");
      return ;
    }
    int i = d0[0];
    // printf("D0:%d\n",i);
    d0.pop_back();
    rep(j,0,(int)p3[i].size()){
      // i -> p3[i][j]
      du[p3[i][j]]--;
      if(du[p3[i][j]] == 0){
        d0.push_back(p3[i][j]);
        if(d0.size() > 1){
            printf("NO\n");
            return ;
        }
      }
    }
  }
  printf("YES\n");
}


int main(){
  int t;
  scanf("%d",&t);
  while(t--){
    work();
  }
  return 0;
}

C题目

https://ac.nowcoder.com/acm/contest/11200/C

大意

从1开始

  1. 每次可以移动 x = x+1
  2. 如果当前格子未被染色, 则染色当前格子并且设置 x = a[x]

a[x]保证非严格单调递增

n<=1e6

输出把所有格子都染色的方案数

题解

设 f(x)把前x个格子全部染色的方案数, 注意到虽然顺序上可能 在染前x个格子过程中,已经把后面的格子染色了,但是后面这个被染色的不计入方案统计

  • x 如果是最后一个被染色的,那么方案数为f(x-1)
  • x 如果不是最后一个被染色的, 那么对于f(x-1)中, 相当于 ? -> x -> y, $y \in [a_x,x-1]$, 所以它可以放在$x-a_x$个位置的前面

所以方案数 = $\prod_{i=1}^n(i-a_i+1)$

代码

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;

typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
const double pi = acos(-1.0);

int n;
int a[1000010];

int main(){
  ll ans = 1;
  cin>>n;
  rep(i,1,n+1){
    scanf("%d",a+i);
    if(i-a[i]+1 <= 0){
      ans = 0;
    }else{
      (ans*=i-a[i]+1)%=MOD;
    }
  }
  printf("%lld\n",ans);
  return 0;
}

总结

状态转移的过程中, 对于上面这种,实际上也可以和方案描述不一致, 统计的时候不会包含超过当前位置的移动方案,而后面的移动方案是可以等价的插入到前面的方案中的(才可以乘法)

不过现在好的是,我能判断这个类型算是数学和转移的题了,也想到这样设计状态,但是没有细想

参考

https://ac.nowcoder.com/discuss/952589

發表於 更新於 分類於 ， Disqus： 文章字數： 1.7k 所需閱讀時間 ≈ 6 分鐘
C (trie树, bit flip)

C

https://atcoder.jp/contests/agc057/tasks/agc057_c

0~ 2^N - 1的排列

问能否通过多次任选操作(每次操作独立,在上一次操作结果基础上), 让数列单调递增, 给出方案

操作1: a[i] = (a[i]+1)%(2^n) , 所有值循环+1

操作2: a[i] = a[i] xor x , 选定一个值,所有值异或它

限制

n<=18

我的思路

显然连续的异或没意义,甚至题目可以改成不是+1,+任意

所以问题变成 穿插的正数个+1和xor能否让数列单调递增, 若能给出方案

考虑所有+1/xor 末尾是1, 都是让所有末尾翻转, 因此结论是 末位前两个互为0/1,后面循环这两个

同理考察第二位,发现(0和2)(1和3)两对,互为0/1,后面的同样按照4个一组循环

同理考察第三位,发现(0和4)(1和5)(2和6)(3和7)四对,互为0/1,后面的同样按照8个一组循环

换句话说, 最低位1个自由元,其它由它决定,第2低位两个自由元,剩余的也是由它决定,第低3位4个自由元,低4位8个自由元…

我想先弄好一部分位再弄剩下的,从高位到低位或从低位到高位,但是 没想到实际怎么操作

题解

设计结构

trie tree

先不看方框, 看树上的边, 从根向叶子的方向, 对应值的从低到高的位

然后关注叶子方框,例如上面的6,二进制下是110,和它的路径是一样的

再看带有n的方框,意思是如果从树上截取某个点作为根来看,如果根表示的是n,那么一条边权是0子节点是2n+0,边权是1的子节点是2n+1, 注意的是这里并不是左右节点,而是由边权决定的

树的结构建好以后, 那么把叶子中再填入初始每个值所在的位置,完成初始化

接下来看+1和xor操作对树进行怎样的修改

+1

+1

因为我们的树是越接近根,对应的位越低,所以+1带来的进位效果也是从根向叶子前进的

如果我们以改变树上边的权值,而不是改变左右指向的视角来看,

那么对于根

0变成1

1变成0且它的子树受到和根一样的处理

这样发现改动的实际上只有log级别个

xor

xor

xor 比 +1 其实好观察,

对于xor二进制对应位为1的层级的0变成1,1变成0

实现

现在我们再回头看目标呢, 也就是位置上和它对应的值是一样的

这里可以思考为啥,是按边上的值来描述而不是左右描述的, 考虑不按照涂上那样初始摆,而是按照叶子直接放初始的值,比如这里0 4 2 6 1 5 3 7位置上对应的值, 在放值时就能明确的知道冲突的情况,排除一些不可能

问题变成了,如何让二叉树边上的0/1 变回 完全二叉树的位置对应的值

考虑把叶子变成 0,1 序列.

如果叶子是反着的1,0, 那么只需要把上面的路径变成 从根到它都是1,这样+1 就能完成修正

修正了所有叶子以后, 问题来了, 还可以通过+1/xor的组合修正非叶子吗

1
2
3
   1       0
 1   0   0   1 ( 其它位还有 不是xor 能解决的情况
0 1 0 1 0 1 0 1 ( 高位全部0,1顺序了

证明不可能, 首先 这种情况, 如果能修正,必定是奇数次操作到该层, 因为 xor不改相对一致性,+每次操作到这两个中的一个就会改,所以这两个操作次数总和必为奇数,考虑它们所覆盖的叶子节点,总操作次数也为奇数

因此要么 xor翻转能得到,要么就是不可能

从逻辑上, 已经完成了,还有个实现问题,如果通过枚举导数第二层,再模拟xor和+1, 虽然+1代价小,但是xor的代价可能达到O(n)的级别, 总的会变成n方

简单的增加一个翻转标识记录行的翻转状态, 因为+1是对单个点翻转,xor是行翻转,翻转两次等于未翻转,都是翻转,所以+1直接让对应位置的节点翻转, 而xor 通过行标识记录,

代码

https://atcoder.jp/contests/agc057/submissions/31596691

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
105
106
107
108
109
110
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

const int N = 262144;

vector<int> lr(N*4+10,-1); // -1 unset 0:01, 1:10

int a[N+10];

int n;
bool build(int pos,int val,int idx = 1,int pwr = 0){
  if(pwr == n)return true;
  int direction = pos%2;
  int v = direction != val%2;
  if(lr[idx] != -1 && lr[idx] != v){
    return false;
  }
  lr[idx] = v;
  return build(pos/2,val/2,idx*2+direction,pwr+1);
}

int xorcache[20] = {0}; // 不要实际的xor, 修改代价大

vector<int>ans;

void fix(int val){
  // printf("Fix %d\n",val);
  int x = 0;
  {
    int pwr = n-1;
    int v = val;
    while(pwr--){
      if(v%2 == (lr[v/2] ^ xorcache[pwr])){
        x |= (1<<(pwr));
      }
      v/=2;
    }
  }
  // printf("xor %d\n",x);
  if(x){
    ans.push_back(x);
    rep(pwr,0,n){
      if((1<<pwr) & x)xorcache[pwr]^=1; // 标记
    }
  }
  // printf("+1\n");
  {
    int idx = 1;
    rep(pwr,0,n){
      if(lr[idx]^xorcache[pwr]){
        idx=idx*2;
      }else{
        idx=idx*2+1;
      }
      lr[idx/2] ^= 1;
    }
  }
  ans.push_back(-1);
}


int main(){
  cin>>n;
  rep(i,0,(1<<n)){
    scanf("%d",a+i);
  }
  rep(i,0,(1<<n)){
    int r = build(i,a[i]);
    if(!r){
      printf("No\n");
      return 0;
    }
  }
  // rep(i,1,8){
  //   printf("lr[%lld]= %d\n",i,lr[i]);
  // }
  rep(i,(1<<(n-1)),(1<<n)){
    if(lr[i] == 0)continue;
    fix(i);
  }
  int x = 0;
  rep(pwr,0,n){
    if(lr[1<<pwr] ^ xorcache[pwr]){
      x |= 1<<pwr;
      xorcache[pwr] ^= 1;
    }
  }
  if(x){
    ans.push_back(x);
  }
  rep(pwr,0,n){
    rep(i,(1<<pwr),(1<<(pwr+1))){
      if(lr[i]^xorcache[pwr]){
        printf("No\n");
        return 0;
      }
    }
  }
  printf("Yes\n");
  printf("%d\n",(int)ans.size());
  rep(i,0,(int)ans.size()){
    printf("%d ",ans[i]);
  }
  printf("\n");
  return 0;
}

总结

其实我的思路和题解中trie树的结论是一致的,但是我的思路不是trie树形状的,所以再往后推导的阻力更大

一个经验就是对于这种2的幂次的 xor 或 加减操作,可以放在trie树中批量操作, 比如稍微变一变, 就可以变成给你+1/-1/xor操作序列,和询问第idx位置是什么,这样多个操作询问交替的题目

参考

官方题解 https://atcoder.jp/contests/agc057/editorial/3925

發表於 更新於 分類於 ， Disqus： 文章字數： 3.1k 所需閱讀時間 ≈ 10 分鐘
D(冒泡排序, 排列),E(线段树,倍数,贡献,单调栈,离线)

D

https://codeforces.com/contest/1677/problem/D

1到n的排列,进行k次冒泡排序(for i = 0..n-1{if a[i] > a[i+1]: swap(a[i],a[i+1])})以后

每一位与它前面的逆序对个数为v[i]

v[i] = count(a[j] > a[i] && j < i)

现在给定数组v,其中-1表示任意值, 求有多少个原始序列 能k次冒泡排序后,逆序对满足v

答案mod 998244353

保证-1<= vi <=i

范围

t <= 1000

k < n <= 1e6

2s

256MB

题解

观察冒泡排序过程中 逆对的变化

如果a[i]前面有比它大的, 那么一次冒泡排序后,至多有一个移动到它后面, 且a[i]移动到了a[i-1]

因此对于逆序对 v[0] v[1] v[2] ... v[n] 的变化是

如果v[i] > 0 , 那么一次排序后 v[i-1] = v[i]-1

对于v[i] == 0, 0 v[i+1] v[i+2] v[i+3] ... v[j-2] v[j-1] 0, 两个0之间其它非零

注意到上面 非0的结论, (v[i+1]-1) (v[i+2]-1) (v[i+3]-1) ... (v[j-2]-1) (v[j-1]-1) 0 (v[?j+1]-1),

即是这个0会移动到下一个0的前一个位置,a[j-1] = a[i]

所以0-index

最终v[i] == 0 操作前 v[i+k] <= k(反证法) , <= min(k,i)

最终v[i] > 0 操作前 v[i+k] = k

最终v[i] == -1 操作前 v[i+k] 任意(<=i)

最后k位一定是0

综上, 我们可以求得初始的v数组

其中 [0..k-1] 任意

其中 [k..n] 由按上述 平移确定具体情况

接下来讨论排列方案计算方式

如果完全自由就是n!,

考虑从后向前选, 如果位置i不受限制, 那么它有i+1种选法, 相当于每个位置的方案数和下标同增 w[i] = i+1(0-index)

如果它明确知道前面有几个比它小的, 那么只有唯一选法

如果它前面比它小的允许<=k, 那么它有k+1种选法, 相当于[0..k]每个一种

题目保证了v[i] 的范围,所以最多判断一下后k位是否为0即可

代码

https://codeforces.com/contest/1677/submission/156367090

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

typedef long long ll;
#define MOD 998244353
#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;)

int n,k;
int v[1000010];

int main(){
  int t;
  cin>>t;
  while(t--){
    scanf("%d %d",&n,&k);
    rep(i,0,n){
      scanf("%d",v+i);
    }
    ll ans = 1;
    rep(i,0,n){
      if(i < k){ // 前k个自由
        (ans*=i+1)%=MOD;
      }else if(v[i-k] == -1){ // -1 自由
        (ans*=i+1)%=MOD;
      }else if(v[i-k] == 0){ // <=k 即 [0..k] , k+1种
        (ans*=k+1)%=MOD;
      } // v[i-k] != 0 , 唯一选择(从后向前)
    }
    // 最后k个一定是0(也可以-1表示0)
    rep(i,0,k){
      if(v[n-1-i] > 0)ans = 0;
    }
    printf("%lld\n",ans);
  }
  return 0;
}

总结

感觉还是考察 冒泡排序及其性质

参考

https://www.bilibili.com/video/BV1GS4y1b7SD

E

https://codeforces.com/contest/1677/problem/E

给定1到n的排列

q个询问

每次问[l..r] 中有多少子区间, 满足 子区间存在不同的两个数的乘积 等于 子区间最大值

范围

n <= 2e5

q <= 1e6

4s

1024MB

题解

a[1..n]为给的排列

离线, 把所有查询[l..r] 按r升序

for(i = 1..n) 在i == r 时,回答查询[l..r]

线段树, 叶子节点记录[l..j], (j<=r) 有多少个是满足的, 答案就是线段树的区间求和query(o,1,n,l,r)

问题: 遍历过程中i=>i+1时,也就是以i==r作为区间结束时,合法的区间起始l需要+1,但合法的l是散的,不是一个连续的区间, 这样更新复杂度高

考虑加入r时, 左侧比它大的端点的贡献, 首先用单调栈记录(坐标增加,值减少)

vector<pair<value,position>> stk, 其中(stk[i].value = a[stk[i].position])

那么加入{a[r],r} 后会移除值比它小的, 变成

stk[0] ... stk[i-1] stk[i] ... stk[j] {a[r],r}

讨论3部分贡献

  1. 以a[r] 为区间最大值, 那么必然 $(stk[j].position, r]$ 中找最右侧的位置k让a[k..r]中能有两个乘起来等于a[r], 这样, 就有$k-stk[j].position$ 个合法方案

  2. 以stk[i].value为区间最大值, 且stk[i].value 不是a[r]的倍数, $max(k) ,k \in (stk[i-1].position,stk[i].position]$, 贡献为$k-stk[i-1].position$, 因为不是倍数, 显然并不会因为多了a[r] 影响以这个值为最大值的左侧选取的$k$, 所以换个说法就是, 它以原来的贡献又贡献了一轮

  3. 以stk[i].value为区间最大值, 且stk[i].value 是a[r]的倍数, $max(k) ,k \in (stk[i-1].position,stk[i].position]$, 贡献为$k-stk[i-1].position$, 是倍数, 所以需要看stk[i].value/a[r]这个值所在的位置是否会更新k

这样去统计, 单调队列中

考虑变化

如果我们每个线段树节点记录了 (对右侧贡献的左端点数量x, 总贡献数c)

(x0,c0) => (x1,c1) 是怎么变化的呢

x1 = x0 + 那些a[r]倍数中超出来的长度

c1 = c0 + x1

注意的是, 可以lazytag记录有多少轮没有向下, 每次修改log级别个节点就行了

(这个方法感觉有实现问题, 我尝试做了一下,发现每次需要 c += x, 但是因为lazytag 的关系, 你一个节点上只能保存常数个x 和 常数个次数记录, 对于在 dep 层 的变化, lazytag down到dep+1层会覆盖x, 换句话说 lazy 的部分和历史每个节点内的x相关

官方的代码, 记录的是(x0,y0)

y0 = c0 - x0 * 轮次, y1 = c1 - x1*(轮次+1) = (x1+c0) - x1*(轮次+1) = y0 - (x1-x0) * 轮次

比记录和好的是,在不更新时(x,y)不会变,而c会变, 每次更新后所有节点都是正确的值, 因为lazy的部分只和当前轮次相关, 而这些轮次加和以后, 就是y的变化量

注意到 lazy的部分 (x1-x0) 要么是len要么是-len, 所以把符号给到轮次上, lazy轮次的和即可

而不是全覆盖的部分, 直接去更新到准确的(x,y)

代码

官方代码+注释

https://codeforces.com/contest/1677/submission/156392477

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
const int N=2e5;
#define SEG_ROOT 1,1,n
#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
#define SEG_L_CHILD_Q SEG_L,l,mid,ql,qr
#define SEG_R_CHILD_Q SEG_R,mid+1,r,ql,qr
int n; // 数组长度
int a[N+10]; // 原始排列 1-index
int a2i[N+10]; // 值到下标 a2i[value] = index
int di; // 单调栈的尾部下标
int d[N+10]; // 单调栈,存的原数组的下标 1-index, d[stack-index] = a-index
int i2di[N+10]; // [a中下标] = 栈中下标 映射  i2di[a-index] = stack-index , 0(表示不在栈中)
int ti; // 当前遍历的个数 = i-1 or i
int p[N+10]; // p[stack-index] = 左侧最大合法a-index
ll ans[1000005]; // 询问的答案数组
vector<pair<int,int> >q[1000005]; // 询问 q[right] = vector<pair<left,query index> >
vector<int> w[N + 10]; // 因数分解 w[value]= vector<value的因数>
struct seg {
  // 答案 = x * ti + y
  ll x; // 合法的左端点位置数
  ll y; // (真实答案 与 x*ti 之间补充的差), 辅助变量, 因为直接记录答案无法维护x, 同理也可以记录(真实答案,x), y = 该段贡献 - x*ti, (x0,y0)=>(x1,y1) : (y0+x0*ti) + x1 = (y1+x1*(ti+1)), y1 = y0 - (x1-x0)*ti
  ll tg; // 未向下传递的ti的和, y += (+/- ti) * len
  ll len; // 对应区间长度 简化书写
} tr[N*4 + 10];
// 初始化 线段树, 只有设置len = 区间长度,其它x,y,tg全为0
void make(int o,int l,int r){
  tr[o].len=r-l+1;
  if (l==r) return;
  make(SEG_L_CHILD);
  make(SEG_R_CHILD);
}
// lazy tag 下降
void down(int o) {
  // x
  if (tr[o].x == tr[o].len) {
    tr[SEG_L].x = tr[SEG_L].len;
    tr[SEG_R].x = tr[SEG_R].len;
  }
  if (tr[o].x==0) {
    tr[SEG_L].x=0;
    tr[SEG_R].x=0;
  }
  // 能向下的tag一定是区间全覆盖的
  if(tr[o].tg != 0){
    assert(tr[o].x == tr[o].len || tr[o].x == 0);
    // y, 如下clear和add 同样的 y += tg * len
    tr[SEG_L].y+=tr[o].tg*tr[SEG_L].len;
    tr[SEG_R].y+=tr[o].tg*tr[SEG_R].len;
    // tg
    tr[SEG_L].tg+=tr[o].tg;
    tr[SEG_R].tg+=tr[o].tg;
    tr[o].tg=0;
  }
}
// 更新 o
void up(int o) {
  tr[o].x=tr[SEG_L].x+tr[SEG_R].x; // 贡献数
  tr[o].y=tr[SEG_L].y+tr[SEG_R].y; // 修正值
}
// 保证 tr[o].x == tr[o].len
void clear(int o,int l,int r,int ql,int qr) {
  if (ql <= l && r <= qr) {
    // 贡献变化 tr[o].x * ti + tr[o].y => 0 * ti (当前轮) + (tr[o].y + ti * tr[o].len)
    // (tr[o].y + ti * tr[o].len) - (tr[o].x * ti + tr[o].y)
    // = ti * (tr[o].len - tr[o].x)
    // = 0
    assert(tr[o].x == tr[o].len);
    tr[o].tg+=ti; // 选中 -> 未选 未向下传递的, 对于下一级来说,也是 y+=ti*(len-x), 所以+ti传下去
    tr[o].y += ti*tr[o].len;// y += ti * x => y += ti * len
    tr[o].x=0;
    return;
  }
  down(o);
  if (ql<=mid) clear(SEG_L_CHILD_Q);
  if (qr>mid) clear(SEG_R_CHILD_Q);
  up(o);
}
// [ql..qr] 现在合法
// 保证了 tr[o].x == 0
void add(int o,int l,int r,int ql,int qr) {
  if (ql <= l && r <= qr) {
    // 贡献变化 tr[o].x * ti + tr[o].y => tr[o].len * (ti+1) 下一轮 + (tr[o].y - ti * tr[o].len)
    // (tr[o].len * (ti+1) + tr[o].y - ti * tr[o].len) - (tr[o].x * ti + tr[o].y)
    // = tr[o].len - (tr[o].x * ti)
    // = tr[o].len
    assert(tr[o].x == 0);
    tr[o].tg += -ti; // 未选 -> 选中 未向下传递的
    tr[o].y += -ti*tr[o].len; // y += -ti*(len - x) => y+= -ti * len
    tr[o].x=tr[o].len;
    return;
  }
  down(o);
  if (ql<=mid) add(SEG_L_CHILD_Q);
  if (qr>mid) add(SEG_R_CHILD_Q);
  up(o);
}
ll find(int o,int l,int r,int ql,int qr) {
  if (ql <= l && r <= qr) return tr[o].y+ti*tr[o].x; // 如segtree的设计定义
  down(o);
  ll ret = 0;
  if (ql<=mid) ret+=find(SEG_L_CHILD_Q);
  if (qr>mid) ret+=find(SEG_R_CHILD_Q);
  return ret;
}
int main() {
  int m; // 询问次数
  scanf("%d%d",&n,&m);
  // 读入排列
  rep(i,1,n+1){
    scanf("%d",&a[i]);
    a2i[a[i]]=i;
  }
  // 读入询问
  rep(i,1,m+1) {
    int l,r;
    scanf("%d%d",&l,&r);
    q[r].emplace_back(l,i);
  }
  // 因数
  rep(i,1,n+1)
    for (int j=i;j<=n;j+=i)
      w[j].emplace_back(i);
  // 初始化 线段树, 只有设置len = 区间长度,其它x,y,tg全为0
  make(SEG_ROOT);
  rep(i,1,n+1) { // a[i]
    while (di && a[d[di]]<a[i]) { // 新加入的值, 比单调栈中的最小的小, 移除操作
      if (p[di]>d[di-1]) clear(SEG_ROOT,d[di-1]+1,p[di]); // 从贡献标记为不贡献, 但是对于总的贡献不变
      // 出栈
      i2di[d[di]]=0;
      di--;
    }
    for (int j=a[i];j<=n;j+=a[i]) { // j = a[i] 的倍数, j 作为最大值时
      int k=i2di[a2i[j]]; // j在栈中下标
      if (!k) continue; // 不在栈中
      int l=d[k-1]+1,r=d[k]; // 左端点在范围 a[l..r] 中
      int e=a2i[j/a[i]]; // 乘起来等于j的另一个因数在a中的下标
      if (e<l || e>=i) continue; // e 在范围 a[l..i) 中, 不能选同一个ie平方
      e=min(e,r); // 左端点范围的最大值 a[l..e]
      if (e<=p[k]) continue; // p[k] 最大值不更新
      // a[l..p[k]] 合法 => a[l..e] 合法
      add(SEG_ROOT,p[k]+1,e); // 把[p[k]+1,e] 从不贡献变成贡献, 更新到本轮结束时该有的(x,y)
      p[k]=e;
    }
    // 入栈
    d[++di]=i;
    i2di[i]=di;
    p[di]=d[di-1]; // 初始化p[di]表示以a[i]作为峰, 左侧端点不贡献
    for (auto j:w[a[i]]) { // 枚举 因子对 (j,a[i]/j)
      int l=d[di-1]+1;
      // int r=i;
      int e1=a2i[j];
      int e2=a2i[a[i]/j];
      if (e2<=e1) continue; // 减少重复计算,主要是不等于
      if (e1<l || e2>i) continue; // [l-1..e1..e2..i+1]
      if (e1<=p[di]) continue; // 不会更新可行值 [p[di] .. e1 .. i]
      add(SEG_ROOT,p[di]+1,e1); // 从不贡献记为贡献, 更新到本轮结束时该有的(x,y)
      p[di]=e1; // 更新
    }
    ti++;
    for (auto t:q[i]) ans[t.second] = find(SEG_ROOT,t.first,i); // 查询[l = t.first,r = i]
  }
  rep(i,1,m+1) printf("%lld\n",ans[i]);
  return 0;
}

总结

学会了一下新的线段树写法,以前我在左右拆点的时候, 会根据覆盖决定是

(ql,qr) => (ql,qr) 还是(ql,qr) => (ql,mid) 还是 (ql,qr) => (mid+1,qr) 终止条件是l == ql && r == qr

这里学到了把终止条件改成ql <= l && r <= qr, 这样的话, 传参就不用拆了(ql,qr) => (ql,qr)

参考

https://codeforces.com/contest/1678/attachments/download/16086/Codeforces%20Round%20789%20Editorial%20in%20Chinese.pdf

https://codeforces.com/blog/entry/102631

https://www.bilibili.com/video/BV1GS4y1b7SD

0%