分类： 分块

YZOJ P4637 [CSP-S 2019 五校联训 Round 2]由比滨结衣(sqrt)

YZOJ P4637 [CSP-S 2019 五校联训 Round 2]由比滨结衣(sqrt)

时间限制：2000MS      内存限制：524288KB

难度：\(6.5\)

  • 题目描述

给定一个长度为 \(n\) 的正整数序列 \(\{a_i\}\)，有 \(m\) 次操作。格式如下：

1 l r x 将区间 \([l,r]\) 中的所有数变为 \(x\)。

2 l r x 查询区间 \([l,r]\) 中数字 \(x\) 的出现次数。

  • 输入格式

第一行两个正整数 \(n,m\)，表示序列长度和操作次数。

第二行 \(n\) 个正整数，第 \(i\) 个数为 \(a_i\)，表示序列初始值。

接下来 \(m\) 行每行四个正整数，表示操作，含义如题目所示。

  • 输出格式

对于每个询问，输出一行一个正整数表示答案。

  • 样例 1 输入

  • 样例 1 输出

  • 数据规模与约定

对于 \(20\%\) 的数据，\(1 \leq …

YZOJ P3371 简单计数问题

YZOJ P3371 简单计数问题

时间限制：3000MS      内存限制：262144KB

难度： \(6.0\)          出题人：zzx

  • 问题描述

给定正整数序列 \(a[1], a[2], \cdots , a[n]\)，你需要依次解决 \(m\) 个询问，每个询问用两个正整数 \(L, R\) 描述， 请求出有多少个数在 \(a[L],a[L+1],\cdots,a[R]\) 中出现正偶数次。

  • 编程任务

求出每个查询的结果。

  • 数据输入

输入第一行四个整数 \(n\)、\(c\)、\(m\) 以及 \(t\) 。

第二行 \(n\) 个整数 \(a[1],a[2],\cdots,a[n]\)，每个数在 \([1,c]\) 间。

接下来 \(m\) 行每行两个整数 \(l\) 和 \(r\)，设上一个询问的答案为 \(ans\) (第一个询问时 \(ans=0\) )，令 \(L=(l+t \times ans) \bmod n+1, R=(r+t \times ans) \bmod n+1\)，若 \(L>R\)，交换 \(L\) 和 \(R\)，则本次询问为 \([L,R]\) 。

  • 结果输出

对于每个询问， 输出一行对应的答案。

  • 样例输入

  • 样例输出

  • 数据范围

对于 \(50\%\) 的数据，有 \(t=0\) 。

对于另外 \(50\%\) 的数据，有 \(t=1\) …

YZOJ P3846 [2018省队集训]Yist

YZOJ P3846 [2018省队集训]Yist

时间限制：1000MS      内存限制：524288KB

难度： \(7.0\)

  • 题目描述

有一个 \(n\) 个点 \(m\) 条边的无向图，结点从 \(1\) 到 \(n\) 标号，点 \(u\) 的初始权值为 \(w_u\)。你可以对任意结点 \(u\) 进行操作，将你的得分（初始为 \(0\)）加上 \(\sum_\limits{(u,v) \in E}w_v\) ，并将 \(w_u\) 除以 \(2\) 。

给定一个长度为 \(k\) 的结点序列 \(s_1,s_2,\cdots,s_k\) （\(1 \leq s_i \leq n\)），在一轮操作中，你需要依次对 \(s_1,s_2,\cdots,s_k\) 进行操作。你想知道，在进行了无限轮操作后，你得分的极限是多少。

显然答案一定可以表示成 \(P/Q\) 的形式，你需要输出 \(P \times Q^{-1}\) 在模 \(998244353\) 意义下的值。特别的，如果得分并不收敛，输出 \(-1\) 。

  • 输入格式

本题有多组数据，请读入到文件结束。

对于每组数据，第一行三个整数 \(n,m,k\) ，含义如题所述。

第二行 \(n\) 个整数 \(w_1,w_2,\cdots,w_n\)，表示结点的初始权值。

第三行 \(k\) 个正整数 \(s_1,s_2,\cdots,s_k\) 。

接下来 \(m\) 行，每行两个整数 \(u,v\)，描述了一条无向边。

  • 输出格式

对于每组数据，输出一行一个整数，表示答案。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(20\%\) 的数据，\(n,m \leq 5\)，\(k \leq 10\)；

对于 \(40\%\) 的数据，\(n,m \leq 1000\)，\(k \leq 2000\)；

对于另外 \(20\%\) 的数据，数据为随机生成；

对于 \(100\%\) 的数据，\(1 \leq …

YZOJ P3484 子树求和

YZOJ P3484 子树求和

时间限制：2000MS      内存限制：262144KB      出题人：lgj

难度： \(6.0\)

  • 题目描述

已知一棵树有 \(n\) 个节点，并且根节点是固定的。

每个节点上都有一个权值 \(w_i\) ，记 \(s_i\) 为 以 \(i\) 为根的子树中，所有节点的 \(w_i\) 的和。

由于询问 \(s_i\) 太简单了，不能将 AKIOI 的你的高智商体现出来，所以每次询问给定 \(l, r\) ，求 \(\sum\limits_{i=l}^{r}{s_i}\) 。

为了避免此题难度太低，不能将 AKIOI 的你的高智商体现出来，所以的询问的过程中还可能修改某个节点的 \(w_i\) 。

为了将 AKIOI 的你的高智商体现出来，你要写一个程序来实时给出询问的答案。

  • 输入格式

第一行为两个整数 \(n\) 和 \(q\)，分别表示节点数和操作的次数；

第二行 \(n\) 个正整数，表示序列 \(w\) ；

接下来 \(n\) 行，第 \(i\) 行两个正整数 \(u_i\) 和 \(v_i\)，描述一条树上的边。特别地，\(u_i=0\) 时，表示 \(v_i\) 为树的根节点；

接下来 \(q\) 行，每行三个正整数 \(op, l, r\) 。描述 \(q\) 组操作。 \(op=1\) 表示 \(w_l\) 修改为 \(r\)，\(op=2\) 表示询问 \(\sum\limits_{i=l}^{r}{s_i}\) 的值。

  • 输出格式

对于每组询问操作，你需要依据当前树的情况输出该组询问的标准答案，每次询问的答案独占一行。…