0%

Information

  • Title: Spectral Normalization for Generative Adversarial Networks
  • Author: Takeru Miyato, Toshiki Kataoka, Masanori Koyama, Yuichi Yoshida
  • Institution: Preferred Networks, Inc.(PFN, 日本最大人工智能企业)
  • Year: 2018
  • Journal: ICLR
  • Source: Arxiv, Official code, OpenReview, Other materials
  • Idea: 利用 SN 约束鉴别器的 Lipschitz 常数稳定 GAN 的训练
阅读全文 »

前言

CSP 2022-03 算法题解析

阅读全文 »

前言

CSP 2022-06 算法题解析

能力有限仅能做出前 3 题

阅读全文 »

前言

线段树

模板

C++ 实现:

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
#include <cstdio>
#include <iostream>
using namespace std;

#define MAXN 100007
using ll = long long; // 64 bits

// 线段树可以在 O(log N) 的时间复杂度内实现单点修改、区间修改、区间查询(区间求和,求区间最大值,求区间最小值)等操作
// 注意:为了保持树中孩子结点和父节点的下标对应关系,线段树的下标从 1 开始
// 模板中的是区间求和

// 源数组
ll nums[100007];

// 分别存 值,懒惰标记
ll val[MAXN * 4], tag[MAXN * 4];

// 左孩子结点下标
inline ll lc(ll x) {
return x << 1;
}

// 右孩子结点下标
inline ll rc(ll x) {
return x << 1 | 1;
}

// 向上合并
inline void push_up(ll idx) {
val[idx] = val[lc(idx)] + val[rc(idx)];
}

// 更新懒惰标记
inline void update_tag(ll idx, ll left, ll right, ll k) {
tag[idx] += k;
val[idx] += k * (right - left + 1);
}

// 下传懒惰标记
inline void push_down(ll idx, ll left, ll right) {
ll mid = left + (right - left >> 1);
update_tag(lc(idx), left, mid, tag[idx]);
update_tag(rc(idx), mid + 1, right, tag[idx]);
tag[idx] = 0;
}

// 当前根下标为 idx,递归对 [left, right] 区间建树
// 调用: build(1, 1, n) - 注意数组也要从下标 1 开始
void build(ll idx, ll left, ll right) {
if (left == right) {
val[idx] = nums[left];
}
else {
tag[idx] = 0;
ll mid = left + (right - left >> 1);
build(lc(idx), left, mid);
build(rc(idx), mid + 1, right);
push_up(idx);
}
}

// 更新区间 [left, right], 当前区间 [cur_left, cur_right], 修改变化量
// 调用: update(1, 1, n, left, right)
void update(ll idx, ll cur_left, ll cur_right, ll left, ll right, ll c) {
if (left <= cur_left && right >= cur_right) {
val[idx] += c * (cur_right - cur_left + 1);
tag[idx] += c;
}
else {
ll mid = cur_left + (cur_right - cur_left >> 1);
if (tag[idx] != 0) push_down(idx, cur_left, cur_right);
if (left <= mid) update(lc(idx), cur_left, mid, left, right, c);
if (right > mid) update(rc(idx), mid + 1, cur_right, left, right, c);
push_up(idx);
}
}

// 区间查询 [left, right] 是查询区间,当前区间 [cur_left, cur_right]
// 调用: query(1, 1, n, left, right)
ll query(ll idx, ll cur_left, ll cur_right, ll left, ll right) {
if (left <= cur_left && right >= cur_right) return val[idx];
ll mid = cur_left + (cur_right - cur_left >> 1), ans = 0;
push_down(idx, cur_left, cur_right);
if (left <= mid) ans += query(lc(idx), cur_left, mid, left, right);
if (right > mid) ans += query(rc(idx), mid + 1, cur_right, left, right);
return ans;
}

/**
* 输出线段树存储的数组
*
* @param size: 数组长度
* @param idx 当前下标
* @param left, right 当前范围
* @param t 下传的懒惰标记
*
* 调用方式: print_nums(n, 1, 1, n, 0), putchar('\n');
*/
ll print_nums(ll size, ll idx, ll left, ll right, ll t) {
if (left == right) {
printf("%lld ", val[idx] + t);
return 1;
}
ll mid = left + (right - left >> 1);
ll cnt = 0;
if (cnt < size) cnt += print_nums(size - cnt, lc(idx), left, mid, t + tag[idx]);
if (cnt < size) cnt += print_nums(size - cnt, rc(idx), mid + 1, right, t + tag[idx]);
return cnt;
}

/**
* @brief 输出整颗线段树(层序遍历)
*
* @return int
*/
void print_tree(ll size) {
printf("---------- Tree ----------\n");
ll cur = 1, idx = 1;
while (cur <= size) {
for (int i = 0; i < cur; ++i) {
printf("(%lld, %lld) ", val[idx], tag[idx]);
idx++;
}
cur *= 2;
putchar('\n');
}
printf("---------- end ----------\n");
}