快速读入一个整数
int read() {
char c = getchar();
int ret = 0, sign = 1;
while (c < '0' || c > '9') {
if (c == '-') sign = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
// 相当于 ret = ret * 10 + (c - '0')
ret = (ret<<3) + (ret<<1) + (c^48);
c = getchar();
}
return ret * sign;
}
由于平时输入输出都是十进制格式, 此方法简化了输入输出的操作.
#include <stdio.h>
#include <string.h>
#define N 4010
char buf[N];
// bigint 表示非负整数
// 低位在先, 高位在后
typedef struct {
int data[N];
int len;
} bigint;
bigint A, B, C;
bigint *a = &A, *b = &B, *c = &C;
void clear(bigint *a) {
memset(a->data, 0, sizeof(a->data));
}
void read(bigint *a) {
fgets(buf, N, stdin);
int len = strlen(buf);
while (buf[len-1] < '0') --len; // 去掉换行符
clear(a);
for (int i = 0; i < len; ++i) {
a->data[i] = buf[len-1-i] - '0';
}
a->len = len;
}
void print(bigint *a) {
for (int i = a->len-1; i >= 0; --i) {
putchar(a->data[i] + '0');
}
putchar('\n');
}
// 相加结果保存在 a
void add(bigint *a, bigint *b) {
int carry = 0;
if (b->len > a->len) a->len = b->len; // 长度取最大
for (int i = 0; i < a->len; ++i) {
carry += a->data[i] + b->data[i];
a->data[i] = carry % 10;
carry /= 10;
}
// 处理进位
if (carry) {
a->data[a->len++] = 1;
}
}
int iszero(bigint *a) {
return a->len == 1 && a->data[0] == 0;
}
// a 乘 b 结果保存在 c
void mul(bigint *a, bigint *b, bigint *c) {
clear(c);
if (iszero(a) || iszero(b)) {
c->len = 1;
return;
}
int carry = 0;
c->len = a->len + b->len - 1;
for (int k = 0; k < c->len; ++k) {
// 卷积公式
int start = k - b->len + 1;
if (start < 0) start = 0;
for (int i = start; i <= k && i < a->len; ++i) {
carry += a->data[i] * b->data[k-i];
}
c->data[k] = carry % 10;
carry /= 10;
}
// 处理进位
if (carry) {
c->data[c->len++] = carry;
}
}
int main() {
read(a);
read(b);
//add(a, b);
//print(a)
mul(a, b, c);
print(c);
return 0;
}
class SegmentTree:
def __init__(self, arr):
self.arr = arr
n = self.n = len(arr) - 1 # arr 的 0 位空出不用
N = 2**n.bit_length() # N = 2**ceil(log2(n))
self.tree = [0 for i in range(2*N)] # tree 的 0 位空出不用
self.mark = self.tree.copy()
self.init(1, n)
def init(self, l, r, p = 1):
if l == r:
self.tree[p] = self.arr[l]
return
mid = (l + r) // 2
self.init(l, mid, p * 2)
self.init(mid + 1, r, p * 2 + 1)
self.tree[p] = self.tree[p * 2] + self.tree[p * 2 + 1]
# 目标区间 [l, r], 当前区间 [cl, cr]
def update(self, l, r, d, p = 1, cl = 1, cr = None):
if cr is None:
cr = self.n
if cl > r or cr < l: # 区间无交集
return
elif cl >= l and cr <= r: # 当前区间含于目标区间
self.tree[p] += (cr - cl + 1) * d
if cr > cl: # 如果不是叶子节点
self.mark[p] += d # 给当前区间打上(懒)标记
else: # 其他情况
self.push_down(p, cr - cl + 1)
# 递归, 区间细分下去, 最终会归结到无交集和包含两种情形
mid = (cl + cr) // 2
self.update(l, r, d, p * 2, cl, mid)
self.update(l, r, d, p * 2 + 1, mid + 1, cr)
# 根据子节点更新当前节点的值
self.tree[p] = self.tree[p * 2] + self.tree[p * 2 + 1]
def push_down(self, p, length):
# 向下更新一层
self.tree[p * 2] += self.mark[p] * (length - length // 2)
self.tree[p * 2 + 1] += self.mark[p] * (length // 2)
# 标记向下传递
self.mark[p * 2] += self.mark[p]
self.mark[p * 2 + 1] += self.mark[p]
# 清除标记
self.mark[p] = 0
def query(self, l, r, p = 1, cl = 1, cr = None):
if cr is None:
cr = self.n
if cl > r or cr < l:
return 0
elif cl >= l and cr <= r:
return self.tree[p]
else:
self.push_down(p, cr - cl + 1)
mid = (cl + cr) // 2
left = self.query(l, r, p * 2, cl, mid)
right = self.query(l, r, p * 2 + 1, mid + 1, cr)
return left + right
def test_segment_tree():
arr = [i for i in range(10)]
t = SegmentTree(arr)
print(t.tree) # [0, 45, 15, 30, 6, 9, 13, 17, 3, 3, 4, 5, 6, 7, 8, 9, 1, 2]
print(t.query(2, 2)) # 2
print(t.query(3, 7)) # 25
t.update(3, 7, 1)
print(t.query(3, 7)) # 30
t.update(2, 5, 1)
print(t.query(3, 7)) # 33
test_segment_tree()
'''
9 节点的线段树:
45
15 30
6 9 13 17
3 3 4 5 6 7 8 9
1 2
6 节点的线段树:
6
3 3
2 1 2 1
1 1 1 1
'''