这里参考了一些其他dalao的一些模板
日期模板
int months[13] = {
0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
};
int is_leap(int year) // 计算是否是闰年
{
if (year % 4 == 0 && year % 100 || year % 400 == 0) return 1;
return 0;
}
int get_days(int year, int month) // 求某月有多少天
{
if (month == 2) return months[month] + is_leap(year);
return months[minth]
}
lca
给定一棵包含 n 个节点的有根无向树,节点编号互不相同,但不一定是 1∼n。
有 m 个询问,每个询问给出了一对节点的编号 x 和 y,询问 x 与 y 的祖孙关系。
输入第一行包括一个整数 表示节点个数;
接下来 n 行每行一对整数 a 和 b,表示 a 和 b 之间有一条无向边。如果 b 是 −1,那么 a 就是树的根;
第 n+2 行是一个整数 m 表示询问个数;
接下来 m 行,每行两个不同的正整数 x 和 y,表示一个询问。
对于每一个询问,若 x 是 y 的祖先则输出 1,若 y 是 x 的祖先则输出 2,否则输出 0。
const int N = 40010, M = N * 2;
int n, m;
int h[N], e[M], ne[M], idx;
int depth[N], fa[N][16];
int q[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void bfs(int root)
{
memset(depth, 0x3f, sizeof depth);
depth[0] = 0, depth[root] = 1;
int hh = 0, tt = 0;
q[0] = root;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (depth[j] > depth[t] + 1)
{
depth[j] = depth[t] + 1;
q[ ++ tt] = j;
fa[j][0] = t;
for (int k = 1; k <= 15; k ++ )
fa[j][k] = fa[fa[j][k - 1]][k - 1];
}
}
}
}
int lca(int a, int b)
{
if (depth[a] < depth[b]) swap(a, b);
for (int k = 15; k >= 0; k -- )
if (depth[fa[a][k]] >= depth[b])
a = fa[a][k];
if (a == b) return a;
for (int k = 15; k >= 0; k -- )
if (fa[a][k] != fa[b][k])
{
a = fa[a][k];
b = fa[b][k];
}
return fa[a][0];
}
int main()
{
scanf("%d", &n);
int root = 0;
memset(h, -1, sizeof h);
for (int i = 0; i < n; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
if (b == -1) root = a;
else add(a, b), add(b, a);
}
bfs(root);
scanf("%d", &m);
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
int p = lca(a, b);
if (p == a) puts("1");
else if (p == b) puts("2");
else puts("0");
}
return 0;
}
给出 n 个点的一棵树,多次询问两点之间的最短距离。
边是无向的。所有节点的编号是 1,2,…,n。
const int N = 10010, M = N * 2;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
int p[N];
int res[M];
int st[N];
vector<PII> query[N]; // first存查询的另外一个点,second存查询编号
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u, int fa)
{
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa) continue;
dist[j] = dist[u] + w[i];
dfs(j, u);
}
}
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void tarjan(int u)
{
st[u] = 1;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!st[j])
{
tarjan(j);
p[j] = u;
}
}
for (auto item : query[u])
{
int y = item.first, id = item.second;
if (st[y] == 2)
{
int anc = find(y);
res[id] = dist[u] + dist[y] - dist[anc] * 2;
}
}
st[u] = 2;
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
for (int i = 0; i < m; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
if (a != b)
{
query[a].push_back({b, i});
query[b].push_back({a, i});
}
}
for (int i = 1; i <= n; i ++ ) p[i] = i;
dfs(1, -1);
tarjan(1);
for (int i = 0; i < m; i ++ ) printf("%d\n", res[i]);
return 0;
}
// 严格次小生成树
const int N = 100010, M = 300010, INF = 0x3f3f3f3f;
int n, m;
struct Edge
{
int a, b, w;
bool used;
bool operator< (const Edge &t) const
{
return w < t.w;
}
}edge[M];
int p[N];
int h[N], e[M], w[M], ne[M], idx;
int depth[N], fa[N][17], d1[N][17], d2[N][17];
int q[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
LL kruskal()
{
for (int i = 1; i <= n; i ++ ) p[i] = i;
sort(edge, edge + m);
LL res = 0;
for (int i = 0; i < m; i ++ )
{
int a = find(edge[i].a), b = find(edge[i].b), w = edge[i].w;
if (a != b)
{
p[a] = b;
res += w;
edge[i].used = true;
}
}
return res;
}
void build()
{
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++ )
if (edge[i].used)
{
int a = edge[i].a, b = edge[i].b, w = edge[i].w;
add(a, b, w), add(b, a, w);
}
}
void bfs()
{
memset(depth, 0x3f, sizeof depth);
depth[0] = 0, depth[1] = 1;
q[0] = 1;
int hh = 0, tt = 0;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (depth[j] > depth[t] + 1)
{
depth[j] = depth[t] + 1;
q[ ++ tt] = j;
fa[j][0] = t;
d1[j][0] = w[i], d2[j][0] = -INF;
for (int k = 1; k <= 16; k ++ )
{
int anc = fa[j][k - 1];
fa[j][k] = fa[anc][k - 1];
int distance[4] = {d1[j][k - 1], d2[j][k - 1], d1[anc][k - 1], d2[anc][k - 1]};
d1[j][k] = d2[j][k] = -INF;
for (int u = 0; u < 4; u ++ )
{
int d = distance[u];
if (d > d1[j][k]) d2[j][k] = d1[j][k], d1[j][k] = d;
else if (d != d1[j][k] && d > d2[j][k]) d2[j][k] = d;
}
}
}
}
}
}
int lca(int a, int b, int w)
{
static int distance[N * 2];
int cnt = 0;
if (depth[a] < depth[b]) swap(a, b);
for (int k = 16; k >= 0; k -- )
if (depth[fa[a][k]] >= depth[b])
{
distance[cnt ++ ] = d1[a][k];
distance[cnt ++ ] = d2[a][k];
a = fa[a][k];
}
if (a != b)
{
for (int k = 16; k >= 0; k -- )
if (fa[a][k] != fa[b][k])
{
distance[cnt ++ ] = d1[a][k];
distance[cnt ++ ] = d2[a][k];
distance[cnt ++ ] = d1[b][k];
distance[cnt ++ ] = d2[b][k];
a = fa[a][k], b = fa[b][k];
}
distance[cnt ++ ] = d1[a][0];
distance[cnt ++ ] = d1[b][0];
}
int dist1 = -INF, dist2 = -INF;
for (int i = 0; i < cnt; i ++ )
{
int d = distance[i];
if (d > dist1) dist2 = dist1, dist1 = d;
else if (d != dist1 && d > dist2) dist2 = d;
}
if (w > dist1) return w - dist1;
if (w > dist2) return w - dist2;
return INF;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
edge[i] = {a, b, c};
}
LL sum = kruskal();
build();
bfs();
LL res = 1e18;
for (int i = 0; i < m; i ++ )
if (!edge[i].used)
{
int a = edge[i].a, b = edge[i].b, w = edge[i].w;
res = min(res, sum + lca(a, b, w));
}
printf("%lld\n", res);
return 0;
}
现在有 N 头牛,编号从 1 到 N,给你 M 对整数 (A,B),表示牛 A 认为牛 B 受欢迎。
这种关系是具有传递性的,如果 A 认为 B 受欢迎,B 认为 C 受欢迎,那么牛 A 也认为牛 C 受欢迎。
求有多少头牛被除自己之外的所有牛认为是受欢迎的。
const int N = 10010, M = 50010;
int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, Size[N];
int dout[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++ timestamp;
stk[ ++ top] = u, in_stk[u] = true;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
}
if (dfn[u] == low[u])
{
++ scc_cnt;
int y;
do {
y = stk[top -- ];
in_stk[y] = false;
id[y] = scc_cnt;
Size[scc_cnt] ++ ;
} while (y != u);
}
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
for (int i = 1; i <= n; i ++ )
if (!dfn[i])
tarjan(i);
for (int i = 1; i <= n; i ++ )
for (int j = h[i]; ~j; j = ne[j])
{
int k = e[j];
int a = id[i], b = id[k];
if (a != b) dout[a] ++ ;
}
int zeros = 0, sum = 0;
for (int i = 1; i <= scc_cnt; i ++ )
if (!dout[i])
{
zeros ++ ;
sum += Size[i];
if (zeros > 1)
{
sum = 0;
break;
}
}
printf("%d\n", sum);
return 0;
}
// 学校网络
N+1 行,每行包含一个或多个整数,第 i+1 行表示学校 i 应该支援的学校名单,每行最后都有一个0表示名单结束(只有一个 0 即表示该学校没有需要支援的学校)。
最少需要添加几条新的支援关系,使得将一个新软件提供给任何一个学校,其他所有学校就都可以通过网络获得该软件?
const int N = 110, M = 10010;
int n;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt;
int din[N], dout[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++ timestamp;
stk[ ++ top] = u, in_stk[u] = true;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if (in_stk[j])
low[u] = min(low[u], dfn[j]);
}
if (dfn[u] == low[u])
{
++ scc_cnt;
int y;
do {
y = stk[top -- ];
in_stk[y] = false;
id[y] = scc_cnt;
} while (y != u);
}
}
int main()
{
cin >> n;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ )
{
int t;
while (cin >> t, t) add(i, t);
}
for (int i = 1; i <= n; i ++ )
if (!dfn[i])
tarjan(i);
for (int i = 1; i <= n; i ++ )
for (int j = h[i]; j != -1; j = ne[j])
{
int k = e[j];
int a = id[i], b = id[k];
if (a != b)
{
dout[a] ++ ;
din[b] ++ ;
}
}
int a = 0, b = 0;
for (int i = 1; i <= scc_cnt; i ++ )
{
if (!din[i]) a ++ ;
if (!dout[i]) b ++ ;
}
printf("%d\n", a);
if (scc_cnt == 1) puts("0");
else printf("%d\n", max(a, b));
return 0;
}
给定一个由 n 个点 m 条边构成的无向图,请你求出该图删除一个点之后,连通块最多有多少。
const int N = 10010, M = 30010;
int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int root, ans;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++ timestamp;
int cnt = 0;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
if (low[j] >= dfn[u]) cnt ++ ;
}
else low[u] = min(low[u], dfn[j]);
}
if (u != root) cnt ++ ;
ans = max(ans, cnt);
}
int main()
{
while (scanf("%d%d", &n, &m), n || m)
{
memset(dfn, 0, sizeof dfn);
memset(h, -1, sizeof h);
idx = timestamp = 0;
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
ans = 0;
int cnt = 0;
for (root = 0; root < n; root ++ )
if (!dfn[root])
{
cnt ++ ;
tarjan(root);
}
printf("%d\n", ans + cnt - 1);
}
return 0;
}
树状数组
给定长度为 N 的数列 A,然后输入 M 行操作指令。
第一类指令形如 C l r d,表示把数列中第 l∼r 个数都加 d。
第二类指令形如 Q x,表示询问数列中第 x 个数的值。
const int N = 100010;
int n, m;
int a[N];
LL tr[N];
int lowbit(int x)
{
return x & -x;
}
void add(int x, int c)
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
LL sum(int x)
{
LL res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++ ) add(i, a[i] - a[i - 1]);
while (m -- )
{
char op[2];
int l, r, d;
scanf("%s%d", op, &l);
if (*op == 'C')
{
scanf("%d%d", &r, &d);
add(l, d), add(r + 1, -d);
}
else
{
printf("%lld\n", sum(l));
}
}
return 0;
}
给定一个长度为 N 的数列 A,以及 M 条指令,每条指令可能是以下两种之一:
C l r d,表示把 A[l],A[l+1],…,A[r] 都加上 d。
Q l r,表示询问数列中第 l∼r 个数的和。
int n, m;
int a[N];
LL tr1[N]; // 维护b[i]的前缀和
LL tr2[N]; // 维护b[i] * i的前缀和
int lowbit(int x)
{
return x & -x;
}
void add(LL tr[], int x, LL c)
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
LL sum(LL tr[], int x)
{
LL res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
LL prefix_sum(int x)
{
return sum(tr1, x) * (x + 1) - sum(tr2, x);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++ )
{
int b = a[i] - a[i - 1];
add(tr1, i, b);
add(tr2, i, (LL)b * i);
}
while (m -- )
{
char op[2];
int l, r, d;
scanf("%s%d%d", op, &l, &r);
if (*op == 'Q')
{
printf("%lld\n", prefix_sum(r) - prefix_sum(l - 1));
}
else
{
scanf("%d", &d);
// a[l] += d
add(tr1, l, d), add(tr2, l, l * d);
// a[r + 1] -= d
add(tr1, r + 1, -d), add(tr2, r + 1, (r + 1) * -d);
}
}
return 0;
}
有 n 头奶牛,已知它们的身高为 1∼n 且各不相同,但不知道每头奶牛的具体身高。
现在这 n 头奶牛站成一列,已知第 i 头牛前面有 Ai 头牛比它低,求每头奶牛的身高(第一头没标出)
const int N = 100010;
int n;
int h[N];
int ans[N];
int tr[N];
int lowbit(int x)
{
return x & -x;
}
void add(int x, int c)
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
int sum(int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main()
{
scanf("%d", &n);
for (int i = 2; i <= n; i ++ ) scanf("%d", &h[i]);
for (int i = 1; i <= n; i ++ ) tr[i] = lowbit(i);
for (int i = n; i; i -- )
{
int k = h[i] + 1;
int l = 1, r = n;
while (l < r)
{
int mid = l + r >> 1;
if (sum(mid) >= k) r = mid;
else l = mid + 1;
}
ans[i] = r;
add(r, -1);
}
for (int i = 1; i <= n; i ++ ) printf("%d\n", ans[i]);
return 0;
}
给定一个正整数数列 a1,a2,…,an,每一个数都在 0∼p−1 之间。
添加操作:向序列后添加一个数,序列长度变成 n+1;
询问操作:询问这个序列中最后 L 个数中最大的数是多少。
加入的数是 (t+a) mod p。其中,t 是输入的参数,a 是在这个添加操作之前最后一个询问操作的答案(如果之前没有询问操作,则 a=0
const int N = 200010;
int m, p;
struct Node
{
int l, r;
int v; // 区间[l, r]中的最大值
}tr[N * 4];
void pushup(int u) // 由子节点的信息,来计算父节点的信息
{
tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}
void build(int u, int l, int r)
{
tr[u] = {l, r};
if (l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
int query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].v; // 树中节点,已经被完全包含在[l, r]中了
int mid = tr[u].l + tr[u].r >> 1;
int v = 0;
if (l <= mid) v = query(u << 1, l, r);
if (r > mid) v = max(v, query(u << 1 | 1, l, r));
return v;
}
void modify(int u, int x, int v)
{
if (tr[u].l == x && tr[u].r == x) tr[u].v = v;
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
}
int main()
{
int n = 0, last = 0;
scanf("%d%d", &m, &p);
build(1, 1, m);
int x;
char op[2];
while (m -- )
{
scanf("%s%d", op, &x);
if (*op == 'Q')
{
last = query(1, n - x + 1, n);
printf("%d\n", last);
}
else
{
modify(1, n + 1, ((LL)last + x) % p);
n ++ ;
}
}
return 0;
}
给定长度为 N 的数列 A,以及 M 条指令,每条指令可能是以下两种之一:
1 x y,查询区间 [x,y] 中的最大连续子段和,即 maxx≤l≤r≤y{∑i=lrA[i]}。
2 x y,把 A[x] 改成 y。
const int N = 500010;
int n, m;
int w[N];
struct Node
{
int l, r;
int sum, lmax, rmax, tmax;
}tr[N * 4];
void pushup(Node &u, Node &l, Node &r)
{
u.sum = l.sum + r.sum;
u.lmax = max(l.lmax, l.sum + r.lmax);
u.rmax = max(r.rmax, r.sum + l.rmax);
u.tmax = max(max(l.tmax, r.tmax), l.rmax + r.lmax);
}
void pushup(int u)
{
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, r, w[r], w[r], w[r], w[r]};
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int x, int v)
{
if (tr[u].l == x && tr[u].r == x) tr[u] = {x, x, v, v, v, v};
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
}
Node query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u];
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid) return query(u << 1, l, r);
else if (l > mid) return query(u << 1 | 1, l, r);
else
{
auto left = query(u << 1, l, r);
auto right = query(u << 1 | 1, l, r);
Node res;
pushup(res, left, right);
return res;
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
build(1, 1, n);
int k, x, y;
while (m -- )
{
scanf("%d%d%d", &k, &x, &y);
if (k == 1)
{
if (x > y) swap(x, y);
printf("%d\n", query(1, x, y).tmax);
}
else modify(1, x, y);
}
return 0;
}
给定一个长度为 N 的数列 A,以及 M 条指令,
C l r d,表示把 A[l],A[l+1],…,A[r] 都加上 d。
Q l r,表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。
const int N = 500010;
int n, m;
LL w[N];
struct Node
{
int l, r;
LL sum, d;
}tr[N * 4];
LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}
void pushup(Node &u, Node &l, Node &r)
{
u.sum = l.sum + r.sum;
u.d = gcd(l.d, r.d);
}
void pushup(int u)
{
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r)
{
if (l == r)
{
LL b = w[r] - w[r - 1];
tr[u] = {l, r, b, b};
}
else
{
tr[u].l = l, tr[u].r = r;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int x, LL v)
{
if (tr[u].l == x && tr[u].r == x)
{
LL b = tr[u].sum + v;
tr[u] = {x, x, b, b};
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
}
Node query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u];
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid) return query(u << 1, l, r);
else if (l > mid) return query(u << 1 | 1, l, r);
else
{
auto left = query(u << 1, l, r);
auto right = query(u << 1 | 1, l, r);
Node res;
pushup(res, left, right);
return res;
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%lld", &w[i]);
build(1, 1, n);
int l, r;
LL d;
char op[2];
while (m -- )
{
scanf("%s%d%d", op, &l, &r);
if (*op == 'Q')
{
auto left = query(1, 1, l);
Node right({0, 0, 0, 0});
if (l + 1 <= r) right = query(1, l + 1, r);
printf("%lld\n", abs(gcd(left.sum, right.d)));
}
else
{
scanf("%lld", &d);
modify(1, l, d);
if (r + 1 <= n) modify(1, r + 1, -d);
}
}
return 0;
}
给定一个长度为 N 的数列 A,以及 M 条指令,每条指令可能是以下两种之一:
C l r d,表示把 A[l],A[l+1],…,A[r] 都加上 d。
Q l r,表示询问数列中第 l∼r 个数的和。
const int N = 100010;
int n, m;
int w[N];
struct Node
{
int l, r;
LL sum, add;
}tr[N * 4];
void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u)
{
auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
if (root.add)
{
left.add += root.add, left.sum += (LL)(left.r - left.l + 1) * root.add;
right.add += root.add, right.sum += (LL)(right.r - right.l + 1) * root.add;
root.add = 0;
}
}
void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, r, w[r], 0};
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int l, int r, int d)
{
if (tr[u].l >= l && tr[u].r <= r)
{
tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * d;
tr[u].add += d;
}
else // 一定要分裂
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, d);
if (r > mid) modify(u << 1 | 1, l, r, d);
pushup(u);
}
}
LL query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
LL sum = 0;
if (l <= mid) sum = query(u << 1, l, r);
if (r > mid) sum += query(u << 1 | 1, l, r);
return sum;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
build(1, 1, n);
char op[2];
int l, r, d;
while (m -- )
{
scanf("%s%d%d", op, &l, &r);
if (*op == 'C')
{
scanf("%d", &d);
modify(1, l, r, d);
}
else printf("%lld\n", query(1, l, r));
}
return 0;
}
有如下三种操作形式:
把数列中的一段数全部乘一个值;
把数列中的一段数全部加一个值;
询问数列中的一段数的和,由于答案可能很大,你只需输出这个数模 P 的值。
const int N = 100010;
int n, p, m;
int w[N];
struct Node
{
int l, r;
int sum, add, mul;
}tr[N * 4];
void pushup(int u)
{
tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % p;
}
void eval(Node &t, int add, int mul)
{
t.sum = ((LL)t.sum * mul + (LL)(t.r - t.l + 1) * add) % p;
t.mul = (LL)t.mul * mul % p;
t.add = ((LL)t.add * mul + add) % p;
}
void pushdown(int u)
{
eval(tr[u << 1], tr[u].add, tr[u].mul);
eval(tr[u << 1 | 1], tr[u].add, tr[u].mul);
tr[u].add = 0, tr[u].mul = 1;
}
void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, r, w[r], 0, 1};
else
{
tr[u] = {l, r, 0, 0, 1};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int l, int r, int add, int mul)
{
if (tr[u].l >= l && tr[u].r <= r) eval(tr[u], add, mul);
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, add, mul);
if (r > mid) modify(u << 1 | 1, l, r, add, mul);
pushup(u);
}
}
int query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
int sum = 0;
if (l <= mid) sum = query(u << 1, l, r);
if (r > mid) sum = (sum + query(u << 1 | 1, l, r)) % p;
return sum;
}
int main()
{
scanf("%d%d", &n, &p);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
build(1, 1, n);
scanf("%d", &m);
while (m -- )
{
int t, l, r, d;
scanf("%d%d%d", &t, &l, &r);
if (t == 1)
{
scanf("%d", &d);
modify(1, l, r, 0, d);
}
else if (t == 2)
{
scanf("%d", &d);
modify(1, l, r, d, 1);
}
else printf("%d\n", query(1, l, r));
}
return 0;
}
给定 n 个长度不超过 50 的由小写英文字母组成的单词,以及一篇长为 m 的文章。
请问,有多少个单词在文章中出现了。
const int N = 10010, S = 55, M = 1000010;
int n;
int tr[N * S][26], cnt[N * S], idx;
char str[M];
int q[N * S], ne[N * S];
void insert()
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int t = str[i] - 'a';
if (!tr[p][t]) tr[p][t] = ++ idx;
p = tr[p][t];
}
cnt[p] ++ ;
}
void build()
{
int hh = 0, tt = -1;
for (int i = 0; i < 26; i ++ )
if (tr[0][i])
q[ ++ tt] = tr[0][i];
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = 0; i < 26; i ++ )
{
int p = tr[t][i];
if (!p) tr[t][i] = tr[ne[t]][i];
else
{
ne[p] = tr[ne[t]][i];
q[ ++ tt] = p;
}
}
}
}
int main()
{
int T;
scanf("%d", &T);
while (T -- )
{
memset(tr, 0, sizeof tr);
memset(cnt, 0, sizeof cnt);
memset(ne, 0, sizeof ne);
idx = 0;
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
{
scanf("%s", str);
insert();
}
build();
scanf("%s", str);
int res = 0;
for (int i = 0, j = 0; str[i]; i ++ )
{
int t = str[i] - 'a';
j = tr[j][t];
int p = j;
while (p)
{
res += cnt[p];
cnt[p] = 0;
p = ne[p];
}
}
printf("%d\n", res);
}
return 0;
}