线段树及主席树

CF438D The Child and Sequence

At the children’s day, the child came to Picks’s house, and messed his house up. Picks was angry at him. A lot of important things were lost, in particular the favorite sequence of Picks.

Fortunately, Picks remembers how to repair the sequence. Initially he should create an integer array a[1],a[2],...,a[n]a[1], a[2], ..., a[n]. Then he should perform a sequence of m operations. An operation can be one of the following:

  1. Print operation l,rl, r. Picks should write down the value of i=lra[i]\sum_{i=l}^r a[i].
  2. Modulo operation l, r, x. Picks should perform assignment a[i]=a[i]modxa[i] = a[i] \mod x for each ii (lirl \leq i \leq r).
  3. Set operation k,xk, x. Picks should set the value of a[k]a[k] to xx (in other words perform an assignment a[k]=xa[k] = x).

Can you help Picks to perform the whole sequence of operations?

Input

The first line of input contains two integer: n,m(1n,m105)n, m (1 \leq n, m \leq 10^5). The second line contains n integers, separated by space: a[1],a[2],...,a[n](1a[i]109)a[1], a[2], ..., a[n] (1 \leq a[i] \leq 10^9) — initial value of array elements.

Each of the next mm lines begins with a number type(type{1,2,3})type (type\in \{1, 2, 3\}).

  • If type=1type = 1, there will be two integers more in the line: l,r(1lrn)l, r (1 \leq l \leq r \leq n), which correspond the operation 1.
  • If type=2type = 2, there will be three integers more in the line: l,r,x(1lrn;1x109)l, r, x (1 \leq l \leq r \leq n; 1 \leq x \leq 10^9), which correspond the operation 2.
  • If type=3type = 3, there will be two integers more in the line: k,x(1kn;1x109)k, x (1 \leq k \leq n; 1 \leq x \leq 10^9), which correspond the operation 3.

Output

For each operation 1, please print a line containing the answer. Notice that the answer may exceed the 32-bit integer.

Examples

1
2
3
4
5
6
7
5 5
1 2 3 4 5
2 3 5 4
3 3 5
1 2 5
2 1 3 3
1 1 3
1
2
8
5
1
2
3
4
5
6
7
8
9
10
11
12
10 10
6 9 6 7 6 1 10 10 9 5
1 3 9
2 7 10 9
2 5 10 8
1 4 7
3 3 7
2 7 9 9
1 2 4
1 6 6
1 5 9
3 1 10
1
2
3
4
5
49
15
23
1
9

Note

Consider the first testcase:

  • At first, a={1,2,3,4,5}a = \{1, 2, 3, 4, 5\}.
  • After operation 1,a={1,2,3,0,1}1, a = \{1, 2, 3, 0, 1\}.
  • After operation 2,a={1,2,5,0,1}2, a = \{1, 2, 5, 0, 1\}.
  • At operation 3,2+5+0+1=83, 2 + 5 + 0 + 1 = 8.
  • After operation 4,a={1,2,2,0,1}4, a = \{1, 2, 2, 0, 1\}.
  • At operation 5,1+2+2=55, 1 + 2 + 2 = 5.

题意

给定一个序列aa,对其进行以下几种操作:

  1. 求出序列aa在给定区间[l,r][l, r]中的和
  2. 对序列aa在给定区间[l,r][l, r]中的每一个数进行取模操作
  3. 为序列aa中的第kk个数设置新的值xx

分析

问题涉及区间查询、区间修改、单点修改,故可用线段树进行维护,线段树上的每个节点维护一段区间和。对于区间上的取模操作,可类比区间上的开根操作,对单个数取模/开根一定次数后,其值将不会再发生改变。因此,区间取模可转换为单点取模暴力计算。

  • 当数小于模数时,取模不会改变值
  • 当数小于1时,开根不会改变值

由上可知,当区间内的数都小于一定值后,便无需再进行单点修改操作。因此,我们让线段树上的每个节点再维护一个区间最大值,若区间最大值小于模数/1,则不再往下递归进行取模/开根操作。

AC代码

代码头部

1
2
3
4
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAXN = 1e5 + 10;

线段树结构体设置

1
2
3
4
struct node
{
ll l, r, mx, sum;
} tree[MAXN << 2];

线段树基本操作

孩子节点合并

1
2
3
4
5
void pushup(ll p)
{
tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;
tree[p].mx = max(tree[p << 1].mx, tree[p << 1 | 1].mx);
}

构建线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
void build(ll s, ll t, ll p)
{
tree[p].l = s;
tree[p].r = t;
if (s == t)
{
tree[p].mx = tree[p].sum = a[s];
return;
}
ll mid = (s + t) >> 1;
build(s, mid, p << 1), build(mid + 1, t, p << 1 | 1);
pushup(p);
}

查询区间和

1
2
3
4
5
6
7
8
9
10
11
12
ll query(ll p, ll s, ll t)
{
if (tree[p].l >= s && tree[p].r <= t)
return tree[p].sum;
ll mid = (tree[p].l + tree[p].r) >> 1;
ll sum = 0;
if (s <= mid)
sum = query(p << 1, s, t);
if (t > mid)
sum += query(p << 1 | 1, s, t);
return sum;
}

区间取模

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void mod(ll p, ll s, ll t, ll x)
{
if (x > tree[p].mx)
return;
if (tree[p].l == tree[p].r)
{
tree[p].sum %= x;
tree[p].mx = tree[p].sum;
return;
}
ll mid = (tree[p].l + tree[p].r) >> 1;
if (s <= mid)
mod(p << 1, s, t, x); // note: please use [s, t] for all functions
if (t > mid)
mod(p << 1 | 1, s, t, x);
pushup(p);
}

单点修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void update(ll p, ll k, ll x)
{
if (tree[p].l == tree[p].r)
{
tree[p].sum = tree[p].mx = x;
return;
}
ll mid = (tree[p].l + tree[p].r) >> 1;
if (k <= mid)
update(p << 1, k, x);
else
update(p << 1 | 1, k, x);
pushup(p);
}

主函数

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
ll a[MAXN];
ll n, m;

int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
build(1, n, 1);
while (m--)
{
ll type;
cin >> type;
if (type == 1)
{
ll l, r;
cin >> l >> r;
cout << query(1, l, r) << endl;
}
else if (type == 2)
{
ll l, r, x;
cin >> l >> r >> x;
mod(1, l, r, x);
}
else
{
ll k, x;
cin >> k >> x;
update(1, k, x);
}
}
return 0;
}

注意事项

  • 在进行线段树的区间查询与区间修改操作时,目标区间[s,t][s, t]应始终保持不变地进行递归,切勿在递归的过程中改变值,传入类似[s,mid][s, mid][mid+1,t][mid + 1, t]的区间。递归改变的是每个节点所管控的区间范围,而在结构体封装的线段树中,是无需传入给区间查询和区间修改的递归函数的。

CF787D Legacy

Rick and his co-workers have made a new radioactive formula and a lot of bad guys are after them. So Rick wants to give his legacy to Morty before bad guys catch them.

There are nn planets in their universe numbered from 11 to nn. Rick is in planet number ss (the earth) and he doesn’t know where Morty is. As we all know, Rick owns a portal gun. With this gun he can open one-way portal from a planet he is in to any other planet (including that planet). But there are limits on this gun because he’s still using its free trial.

By default he can not open any portal by this gun. There are qq plans in the website that sells these guns. Every time you purchase a plan you can only use it once but you can purchase it again if you want to use it more.

Plans on the website have three types:

  1. With a plan of this type you can open a portal from planet vv to planet uu.
  2. With a plan of this type you can open a portal from planet vv to any planet with index in range [l,r][l, r].
  3. With a plan of this type you can open a portal from any planet with index in range [l,r][l, r] to planet vv.

Rick doesn’t known where Morty is, but Unity is going to inform him and he wants to be prepared for when he finds and start his journey immediately. So for each planet (including earth itself) he wants to know the minimum amount of money he needs to get from earth to that planet.

Input

The first line of input contains three integers nn, qq and ss (1n,q105,1sn)(1 \leq n, q \leq 10^5, 1 \leq s \leq n) — number of planets, number of plans and index of earth respectively.

The next qq lines contain the plans. Each line starts with a number tt, type of that plan (1t3)(1 \leq t \leq 3). If t=1t = 1 then it is followed by three integers vv, uu and ww where ww is the cost of that plan (1v,un,1w109)(1 \leq v, u \leq n, 1 \leq w \leq 10^9). Otherwise it is followed by four integers vv, ll, rr and ww where ww is the cost of that plan (1vn,1lrn,1w109)(1 \leq v \leq n, 1 \leq l \leq r \leq n, 1 \leq w \leq 10^9).

Output

In the first and only line of output print nn integers separated by spaces. ii-th of them should be minimum money to get from earth to ii-th planet, or 1-1 if it’s impossible to get to that planet.

Examples

1
2
3
4
5
6
3 5 1
2 3 2 3 17
2 3 2 2 16
2 2 2 3 3
3 3 1 1 12
1 3 3 17
1
0 28 12
1
2
3
4
4 3 1
3 4 1 3 12
2 2 3 4 10
1 2 4 16
1
0 -1 -1 12

Note

In the first sample testcase, Rick can purchase 44th plan once and then 22nd plan in order to get to get to planet number 22.

题意

给出一张图,图中各顶点有连续的编号1n1-n,各顶点之间的连接方式如下三种方式指定:

  1. 从顶点uu到顶点vv,边权为ww
  2. 从顶点vv到编号在区间[l,r][l, r]内的各个顶点,边权为ww
  3. 从编号在区间[l,r][l, r]内的各个顶点到顶点vv,边权为ww

求从编号为ss的顶点出发,到其余所有顶点的最短路径长度。

分析

如果将每一个顶点都独立建图,对于第2、3种连接方式来说,需要进行大量的建边操作。注意到各顶点编号连续,且有区间与点之间的连接方式,于是可以考虑使用线段树将一段区间内的点合并为一个新的点,在合并后的点上进行建图,可以大大减少第2、3种连接方式的建边操作次数。

为了能在新图上跑出相同结果的最短路,我们需要保证合并后的代表一段区间的新点与其所包含的子区间、独立点之间相通且边权为零。这样,从一个点到一个区间点的花费,就等价于从一个点到该区间所有独立点的花费;从一个区间到一个点的花费,就等价于该区间所有独立点各自到该点的花费。

于是,我们可以建得如下两棵线段树(蓝色线段边权为0):

如果外部存在一个点,对于上面这棵线段树来说,则这个点到该线段树上代表一段区间的点的花费,等价于这个点到该区间所包含的所有独立点的花费。

如果外部存在一个点,对于上面这棵线段树来说,则该线段树上代表一段区间的点到外部点的花费,等价于这段区间内所有独立点各自到外部点的花费。

事实上,两棵线段树的叶子节点等价,因此,可以将两棵线段树合并为一个图:

从区间出发到点,则从橙色区间节点向绿色叶子节点连线(绿色叶子节点与橙色叶子节点等价);从点出发到区间,则从橙色叶子节点向绿色区间节点连线。最后,从代表起点的叶子节点出发跑最短路即可。

AC代码

代码头部

1
2
3
4
5
6
7
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll INF = 1e18 + 5;
const int MAXN = 1e5 + 10;

int tot, cnt, head[MAXN << 3], leaf1[MAXN << 3], leaf2[MAXN << 3]; // note: do not forget the head array length

在构建线段树的时候,我们需要为每个节点进行重新编号,方便后续建图操作。这里变量tot用于构建线段树时进行编号,变量cnt用于链式前向星建图编号。而leaf1leaf2数组则存储独立点在建树后的新编号,以原节点编号为地址查找。

线段树结构体设置

1
2
3
4
struct node
{
int l, r, id;
} tree1[MAXN << 2], tree2[MAXN << 2];

链式前向星边结构体设置

1
2
3
4
5
6
7
struct edge
{
int to, next;
ll val;
};

vector<edge> Edge;

构建线段树

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
void build_up(int p, int s, int t)
{
tree1[p].l = s;
tree1[p].r = t;
tree1[p].id = ++tot;
if (s == t)
{
leaf1[s] = tree1[p].id;
return;
}
int mid = (s + t) >> 1;
build_up(p << 1, s, mid), build_up(p << 1 | 1, mid + 1, t);
addEdge(tree1[p << 1].id, tree1[p].id, 0);
addEdge(tree1[p << 1 | 1].id, tree1[p].id, 0);
}

void build_down(int p, int s, int t)
{
tree2[p].l = s;
tree2[p].r = t;
tree2[p].id = ++tot;
if (s == t)
{
leaf2[s] = tree2[p].id;
return;
}
int mid = (s + t) >> 1;
build_down(p << 1, s, mid), build_down(p << 1 | 1, mid + 1, t);
addEdge(tree2[p].id, tree2[p << 1].id, 0);
addEdge(tree2[p].id, tree2[p << 1 | 1].id, 0);
}

图建边函数

1
2
3
4
5
6
7
8
9
void addEdge(int u, int v, ll val)
{
edge e;
e.to = v;
e.val = val;
e.next = head[u];
Edge.emplace_back(e);
head[u] = ++cnt;
}

建图函数

1
2
3
4
5
6
7
8
9
void build_map(int n)
{
edge e;
Edge.emplace_back(e);
build_up(1, 1, n);
build_down(1, 1, n);
for (int i = 1; i <= n; i++)
addEdge(leaf2[i], leaf1[i], 0);
}

区间连点、点连区间

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
void add_section_to_dot(int p, int l, int r, int v, ll val)
{
if (tree1[p].l >= l && tree1[p].r <= r)
{
addEdge(tree1[p].id, leaf1[v], val);
return;
}
int mid = (tree1[p].l + tree1[p].r) >> 1;
if (l <= mid)
add_section_to_dot(p << 1, l, r, v, val);
if (r > mid)
add_section_to_dot(p << 1 | 1, l, r, v, val);
}

void add_dot_to_section(int p, int u, int l, int r, ll val)
{
if (tree2[p].l >= l && tree2[p].r <= r)
{
addEdge(leaf1[u], tree2[p].id, val);
return;
}
int mid = (tree2[p].l + tree2[p].r) >> 1;
if (l <= mid)
add_dot_to_section(p << 1, u, l, r, val);
if (r > mid)
add_dot_to_section(p << 1 | 1, u, l, r, val);
}

最短路算法(迪杰斯特拉)

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
bool vis[MAXN << 3];
ll dis[MAXN << 3];

void dijkstra(ll start)
{
memset(vis, 0, sizeof(vis));
for (int i = 0; i < (MAXN << 3); i++)
dis[i] = INF;
dis[start] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
q.push({0, start});
while (q.size())
{
int u = q.top().second;
q.pop();
if (vis[u])
continue;
vis[u] = true;
for (int e = head[u]; e; e = Edge[e].next)
{
if (vis[Edge[e].to])
continue;
dis[Edge[e].to] = min(dis[Edge[e].to], dis[u] + Edge[e].val);
q.push({dis[Edge[e].to], Edge[e].to});
}
}
}

主函数

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
int n, q, s;

int main()
{
cin >> n >> q >> s;
build_map(n);
while (q--)
{
int t;
cin >> t;
if (t == 1)
{
int v, u;
ll w;
cin >> v >> u >> w;
addEdge(leaf1[v], leaf2[u], w);
}
else
{
int v, l, r;
ll w;
cin >> v >> l >> r >> w;
if (t == 2)
add_dot_to_section(1, v, l, r, w);
else
add_section_to_dot(1, l, r, v, w);
}
}
dijkstra(leaf1[s]);
for (int i = 1; i <= n; i++)
{
if (dis[leaf1[i]] != INF)
cout << dis[leaf1[i]] << " ";
else
cout << "-1 ";
}
cout << endl;
return 0;
}

注意事项

  • 重新合并区间为点后,图中含有的点数要多于原来的点数,故链式前向星中的head数组长度要大于MAXN

CF787E Till I Collapse

Rick and Morty want to find MR. PBH and they can’t do it alone. So they need of Mr. Meeseeks. They Have generated n Mr. Meeseeks, standing in a line numbered from 11 to nn. Each of them has his own color. ii-th Mr. Meeseeks’ color is aia_i.

Rick and Morty are gathering their army and they want to divide Mr. Meeseeks into some squads. They don’t want their squads to be too colorful, so each squad should have Mr. Meeseeks of at most kk different colors. Also each squad should be a continuous subarray of Mr. Meeseeks in the line. Meaning that for each 1iejn1 \leq i \leq e \leq j \leq n, if Mr. Meeseeks number ii and Mr. Meeseeks number jj are in the same squad then Mr. Meeseeks number ee should be in that same squad.

Also, each squad needs its own presidio, and building a presidio needs money, so they want the total number of squads to be minimized.

Rick and Morty haven’t finalized the exact value of kk, so in order to choose it, for each k between 11 and nn (inclusive) need to know the minimum number of presidios needed.

Input

The first line of input contains a single integer n(1n105)n (1 \leq n \leq 10^5) — number of Mr. Meeseeks.

The second line contains nn integers a1,a2,...,ana_1, a_2, ..., a_n separated by spaces (1ain)(1 \leq a_i \leq n) — colors of Mr. Meeseeks in order they standing in a line.

Output

In the first and only line of input print nn integers separated by spaces. ii-th integer should be the minimum number of presidios needed if the value of kk is ii.

Examples

1
2
5
1 3 4 3 3
1
4 2 1 1 1 
1
2
8
1 5 7 8 1 7 6 1
1
8 4 3 2 1 1 1 1 

Note

For the first sample testcase, some optimal ways of dividing army into squads for each kk are:

  1. [1],[3],[4],[3,3][1], [3], [4], [3, 3]
  2. [1],[3,4,3,3][1], [3, 4, 3, 3]
  3. [1,3,4,3,3][1, 3, 4, 3, 3]
  4. [1,3,4,3,3][1, 3, 4, 3, 3]
  5. [1,3,4,3,3][1, 3, 4, 3, 3]

For the second testcase, some optimal ways of dividing army into squads for each kk are:

  1. [1],[5],[7],[8],[1],[7],[6],[1][1], [5], [7], [8], [1], [7], [6], [1]
  2. [1,5],[7,8],[1,7],[6,1][1, 5], [7, 8], [1, 7], [6, 1]
  3. [1,5,7],[8],[1,7,6,1][1, 5, 7], [8], [1, 7, 6, 1]
  4. [1,5,7,8],[1,7,6,1][1, 5, 7, 8], [1, 7, 6, 1]
  5. [1,5,7,8,1,7,6,1][1, 5, 7, 8, 1, 7, 6, 1]
  6. [1,5,7,8,1,7,6,1][1, 5, 7, 8, 1, 7, 6, 1]
  7. [1,5,7,8,1,7,6,1][1, 5, 7, 8, 1, 7, 6, 1]
  8. [1,5,7,8,1,7,6,1][1, 5, 7, 8, 1, 7, 6, 1]

题意

给定一个长为lenlen的序列aa,将其划分为nn个连续子序列,每个子序列中数字种类不能超过kk。当1klen1 \leq k \leq len时,分别求出nn的最小值。

分析

从序列的最左边开始,每次贪心地选择当前kk的限制下,所能到达的最远距离,直至序列末尾。对于计算种类问题来说,从左端点出发,每个数第一次出现的位置才是有效的贡献,将这些具有有效贡献的位置抽取出来组成一个新序列,序列的第k+1k+1个位置就是下一个连续子序列左端点所在的位置(左端点能到达的最远距离)。

因此,问题转换如何构建一个有效贡献位置的序列,以及如何在该序列上快速查找第k+1k+1个位置的信息。

构建有效贡献位置的序列我们容易想到使用线段树或树状数组,从左往右扫描,第一次出现则记为1,若非第一次出现则将先前出现的位置记为0,当前出现的位置记为1。如此扫描至序列末尾,则序列中所有标记为1的位置就是该数最后一次出现的位置,也就是有效贡献位置。线段树或树状数组的特性利于我们单点修改和查询前缀和值,从而快速计算种类数。

本题我们需要记第一次出现的位置为有效贡献位置,只需要按上述方法从右往左扫描序列即可。

构建好序列后,快速查询第k+1k+1个位置的信息,便可以利用线段树进行。如此综合起来,我们就解决了固定序列的构建和查询问题。但在本题中,随着左端点不断往右移动,用于构建有效贡献的序列在发生变化,因此,我们需要在从右往左扫描的过程中保存每个序列所构建起来的有效贡献线段树,在查询时,找到相应版本的线段树即可。

于是本题采用可持久化线段树解决。

AC代码

代码头部

1
2
3
4
5
6
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAXN = 1e5 + 10;

int tot, n, a[MAXN], last[MAXN], rt[MAXN << 1];

可持久化线段树结构体设置

1
2
3
4
struct node
{
int l, r, lson, rson, val;
} tree[MAXN << 7];

可持久化线段树基本操作

构建可持久化线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
int build(int s, int t)
{
int rt = tot++;
tree[rt].l = s;
tree[rt].r = t;
tree[rt].val = 0;
if (s == t)
return rt;
int mid = (s + t) >> 1;
tree[rt].lson = build(s, mid);
tree[rt].rson = build(mid + 1, t);
return rt;
}

单点修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int update(int p, int k, int v)
{
int rt = tot++;
tree[rt] = tree[p];
tree[rt].val += v;
if (tree[rt].r == tree[rt].l)
return rt;
int mid = (tree[rt].l + tree[rt].r) >> 1;
if (k <= mid)
tree[rt].lson = update(tree[rt].lson, k, v);
else
tree[rt].rson = update(tree[rt].rson, k, v);
return rt;
}

查询区间第k小值

1
2
3
4
5
6
7
8
9
int query(int p, int k) // k-th small
{
if (tree[p].l == tree[p].r)
return tree[p].l;
if (k <= tree[tree[p].lson].val)
return query(tree[p].lson, k);
else
return query(tree[p].rson, k - tree[tree[p].lson].val);
}

主函数

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
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
rt[n + 1] = build(1, n + 1); // n + 1
for (int i = n; i >= 1; i--)
{
if (last[a[i]])
{
rt[i] = update(rt[i + 1], last[a[i]], -1);
rt[i] = update(rt[i], i, 1);
}
else
{
rt[i] = update(rt[i + 1], i, 1);
}
last[a[i]] = i;
}
for (int k = 1; k <= n; k++)
{
int l = 1, ans = 0;
while (l <= n)
{
l = query(rt[l], k + 1);
ans++;
}
printf("%d ", ans);
}
return 0;
}

注意事项

  • 建树时在序列末尾创建一个哨兵节点,使其能够正确划分最后一组

HDU2665 Kth number

Problem Description

Give you a sequence and ask you the kth big number of a inteval.

Input

The first line is the number of the test cases.

For each test case, the first line contain two integer nn and mm (n,m100000)(n, m \leq 100000), indicates the number of integers in the sequence and the number of the quaere.

The second line contains nn integers, describe the sequence.

Each of following mm lines contains three integers ss, tt, kk.

[s,t][s, t] indicates the interval and kk indicates the kth big number in interval [s,t][s, t]

Output

For each test case, output mm lines. Each line contains the kth big number.

Sample Input

1
2
3
4
1 
10 1
1 4 2 3 5 6 7 8 9 0
1 3 2

Sample Output

1
2

题意

注意:本题实际上求的是“第k小的数”,即从小到大第k个数

给出一个序列aa,求在给定区间[l,r][l, r]中第kk大的数的值。

分析

我们知道,线段树将区间二分地分成了一块一块。对于维护着区间[1,n][1, n]的线段树而言,如果我们将其叶子节点视作桶,即每个叶子节点维护着值为该区间下标的数的个数,则该线段树的根节点所维护的和值一定为nn。根节点的左孩子所维护的和值为区间[1,n][1, n]内值小于等于n2\frac{n}{2}的数的个数,右孩子维护的和值为区间[1,n][1, n]内值大于n2\frac{n}{2}的数的个数。

因此,当我们需要寻找第kk小的数时,如果kk小于等于左孩子维护的和值,意味着第kk小的数小于等于n2\frac{n}{2},我们需要递归地往左子树寻找;否则意味着第kk小的数大于n2\frac{n}{2},则需要递归地往右子树寻找。

对于本题而言,查找的区间[l,r][l, r]并非总是从1开始,为了实现查找,我们需要一棵由维护区间为[1,l1][1, l - 1]的线段树与维护区间为[1,r][1, r]的线段树作差而得到的差分线段树。因此,我们需要利用主席树,在向线段树中从左往右地插入序列值的同时,保存每一个维护区间为[1,i][1, i]的线段树版本(1in)(1 \leq i \leq n)

另外,此题数据需要进行离散化处理。

AC代码

头部代码

1
2
3
4
5
6
#include <bits/stdc++.h>
typedef int ll; // note: long long will cause MLE
using namespace std;
const int MAXN = 1e5 + 10;

ll tot, lson[MAXN << 5], rson[MAXN << 5], sum[MAXN << 5], T, rt[MAXN];

离散化相关

1
2
3
4
5
6
7
8
9
ll origin[MAXN]

struct node
{
ll idx, rnk, val;
} a[MAXN];

bool cmp1(const node &a, const node &b) { return a.val < b.val; }
bool cmp2(const node &a, const node &b) { return a.idx < b.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
ll update(ll p, ll s, ll t, ll k)
{
ll rt = ++tot;
lson[rt] = lson[p], rson[rt] = rson[p], sum[rt] = sum[p] + 1;
if (s == t)
return rt;
ll mid = (s + t) >> 1;
if (k <= mid)
lson[rt] = update(lson[rt], s, mid, k);
else
rson[rt] = update(rson[rt], mid + 1, t, k);
return rt;
}

ll query(ll p1, ll p2, ll s, ll t, ll k)
{
if (s == t)
return s;
ll mid = (s + t) >> 1;
ll d = sum[lson[p2]] - sum[lson[p1]];
if (d >= k)
return query(lson[p1], lson[p2], s, mid, k);
else
return query(rson[p1], rson[p2], mid + 1, t, k - d);
}

主函数

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
int main()
{
cin >> T;
while (T--)
{
tot = 0;
ll n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i].val;
a[i].idx = i;
}
sort(a + 1, a + 1 + n, cmp1);
ll rnk = 0;
for (int i = 1; i <= n; i++)
{
if (i != 1 && a[i].val == a[i - 1].val)
a[i].rnk = a[i - 1].rnk;
else
a[i].rnk = ++rnk;
}
sort(a + 1, a + 1 + n, cmp2);
for (int i = 1; i <= n; i++)
{
rt[i] = update(rt[i - 1], 1, n, a[i].rnk);
origin[a[i].rnk] = a[i].val;
}
while (m--)
{
ll s, t, k;
cin >> s >> t >> k;
ll rnk = query(rt[s - 1], rt[t], 1, n, k);
cout << origin[rnk] << endl;
}
}
return 0;
}

注意事项

  • 查询操作中,返回的是区间下标,而非节点值。节点值代表的是出现次数,而下标代表着值(这里是离散后的值)

HDU3074 Multiply game

Problem Description

Tired of playing computer games, alpc23 is planning to play a game on numbers. Because plus and subtraction is too easy for this gay, he wants to do some multiplication in a number sequence. After playing it a few times, he has found it is also too boring. So he plan to do a more challenge job: he wants to change several numbers in this sequence and also work out the multiplication of all the number in a subsequence of the whole sequence.
To be a friend of this gay, you have been invented by him to play this interesting game with him. Of course, you need to work out the answers faster than him to get a free lunch, He he…

Input

The first line is the number of case T(T<=10)T (T<=10).

For each test case, the first line is the length of sequence n(n<=50000)n (n<=50000), the second line has nn numbers, they are the initial nn numbers of the sequence a1,a2,,ana_1,a_2, …,a_n

Then the third line is the number of operation q(q50000)q (q \leq 50000), from the fourth line to the q+3q+3 line are the description of the qq operations. They are the one of the two forms:

0 k1k_1 k2k_2; you need to work out the multiplication of the subsequence from k1k_1 to k2k_2, inclusive. (1k1k2n)(1 \leq k_1 \leq k_2 \leq n)

1 kk pp; the kth number of the sequence has been change to p.(1kn)p. (1 \leq k \leq n)

You can assume that all the numbers before and after the replacement are no larger than 1 million.

Output

For each of the first operation, you need to output the answer of multiplication in each line, because the answer can be very large, so can only output the answer after mod1000000007\mod 1000000007.

Sample Input

1
2
3
4
5
6
7
1
6
1 2 4 5 6 3
3
0 2 5
1 3 7
0 2 5

Sample Output

1
2
240
420

题意

给定一个序列aa,对其进行以下两种操作:

  1. 计算序列aa在给定区间[l,r][l, r]中的数的乘积,结果取余10000000071000000007
  2. 将序列aa中的第kk个数更改为pp

分析

很明显的区间查询+单点修改的线段树模板题,线段树上的每一个节点维护一段区间的乘积,最后注意一下取余即可。

AC代码

代码头部

1
2
3
4
5
6
7
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define MOD 1000000007
const int MAXN = 5e4 + 10;

ll a[MAXN], T;

线段树结构体设置

1
2
3
4
struct node
{
ll l, r, ans;
} tree[MAXN << 2];

线段树基本操作

孩子节点合并

1
2
3
4
void pushup(ll p)
{
tree[p].ans = tree[p << 1].ans * tree[p << 1 | 1].ans % MOD;
}

构建线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
void build(ll p, ll s, ll t)
{
tree[p].l = s;
tree[p].r = t;
if (s == t)
{
tree[p].ans = a[s];
return;
}
ll mid = (tree[p].l + tree[p].r) >> 1;
build(p << 1, s, mid), build(p << 1 | 1, mid + 1, t);
pushup(p);
}

查询区间乘积

1
2
3
4
5
6
7
8
9
10
11
12
ll query(ll p, ll s, ll t)
{
if (tree[p].l >= s && tree[p].r <= t)
return tree[p].ans;
ll mid = (tree[p].l + tree[p].r) >> 1;
ll ans = 1;
if (s <= mid)
ans = (ans * query(p << 1, s, t)) % MOD;
if (t > mid)
ans = (ans * query(p << 1 | 1, s, t)) % MOD;
return ans;
}

单点更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void update(ll p, ll k, ll x)
{
if (tree[p].l == tree[p].r)
{
tree[p].ans = x;
return;
}
ll mid = (tree[p].l + tree[p].r) >> 1;
if (k <= mid)
update(p << 1, k, x);
else
update(p << 1 | 1, k, x);
pushup(p);
}

主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int main()
{
scanf("%lld", &T);
while (T--)
{
ll n;
scanf("%lld", &n);
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
build(1, 1, n);
ll q;
scanf("%lld", &q);
while (q--)
{
ll cmd, k1, k2;
scanf("%lld%lld%lld", &cmd, &k1, &k2);
if (cmd == 0)
cout << query(1, k1, k2) % MOD << endl;
else
update(1, k1, k2);
}
}
return 0;
}

注意事项

  • 对于加减乘法运算(无除法),每进行一次运算就做一次取模不会影响最终的取模结果。注意,应当为运算后取模,如:v×vmodp×vmodpv \times v \mod p \times v \mod p,而不是单个值取模,如:vmodp×vmodp×vmodpv \mod p \times v \mod p \times v \mod p

HDU4348 To the moon

Problem Description

To The Moon is a independent game released in November 2011, it is a role-playing adventure game powered by RPG Maker.

The premise of To The Moon is based around a technology that allows us to permanently reconstruct the memory on dying man. In this problem, we’ll give you a chance, to implement the logic behind the scene.

You‘ve been given N integers A[1],A[2],...,A[N]A[1], A[2],..., A[N]. On these integers, you need to implement the following operations:

  1. CC ll rr dd: Adding a constant d for every {Ailir}\{A_i \mid l \leq i \leq r\}, and increase the time stamp by 1, this is the only operation that will cause the time stamp increase.
  2. QQ ll rr: Querying the current sum of {Ailir}\{A_i \mid l \leq i \leq r\}.
  3. HH ll rr tt: Querying a history sum of {Ailir}\{A_i \mid l \leq i \leq r\} in time tt.
  4. BB tt: Back to time tt. And once you decide return to a past, you can never be access to a forward edition anymore.

..N,M105.. N, M \leq 10^5, A[i]109|A[i]| \leq 10^9, 1lrN1 \leq l \leq r \leq N, d104..|d| \leq 10^4 .. the system start from time 00, and the first modification is in time 11, t0t \geq 0, and won’t introduce you to a future state.

Input

nn mm

A1A2...AnA_1 A_2 ... A_n

… (here following the m operations. )

Output

… (for each query, simply print the result. )

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

2 4
0 0
C 1 1 1
C 2 2 -1
Q 1 2
H 1 2 1

Sample Output

1
2
3
4
5
6
7
4
55
9
15

0
1

题意

给出一个序列AA,对其进行以下几种操作:

  1. 为给定区间[l,r][l, r]中的每一个数加上一个值,同时当前时间加1。
  2. 查询当前时间下,给定区间[l,r][l, r]中所有数的和。
  3. 查询tt时间下,给定时间[l,r][l, r]中所有数的和。
  4. 将序列的状态回溯到tt时间下,且不允许再回到较新的时间状态。

分析

区间修改、区间查询,可以想到用线段树进行维护。又由于需要回溯版本,故需要用到可持久化线段树来进行维护。本题重点在于对于可持久化线段树来说,如何处理普通线段树下的懒惰标记问题。

在普通的线段树中,递归更新孩子节点前,需要先将懒惰标记下放至孩子节点。对于可持久化线段树来说,一个节点可能被多个父亲节点共用,因此下放标记显得十分困难,我们可以考虑更新时不下放懒惰标记,而在查询操作时沿路增加懒惰标记的贡献。

可以得出以下区间修改的过程:

  1. 更新该节点所维护的区间值。
  2. 如果所维护的区间包含于修改区间,修改该节点的懒惰标记,返回,不再向下递归
  3. 如果所维护的区间不完全包含于修改区间,则选择向左子树或右子树继续向下递归修改。

区间查询过程如下:

  1. 将该节点懒惰标记的贡献计入ans
  2. 如果所维护的区间包含于修改区间,返回维护的和值
  3. 如果所维护的区间与左子树所维护的区间有交集,递归获取左子树的查询值,计入ans
  4. 如果所维护的区间与右子树所维护的区间有交集,递归获取右子树的查询值,计入ans
  5. 返回ans

AC代码

代码头部

1
2
3
4
5
6
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAXN = 1e5 + 5;

int tot, a[MAXN], n, m, rt[MAXN], tim;

可持久化线段树结构体设置

1
2
3
4
5
struct node
{
int l, r, lson, rson;
ll sum, add;
} tree[MAXN << 5];

线段树基本操作

构建可持久化线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int build(int s, int t)
{
int rt = ++tot;
tree[rt].l = s;
tree[rt].r = t;
tree[rt].lson = tree[rt].rson = tree[rt].add = 0;
if (s == t)
{
tree[rt].sum = a[s];
return rt;
}
int mid = (s + t) >> 1;
tree[rt].lson = build(s, mid);
tree[rt].rson = build(mid + 1, t);
tree[rt].sum = tree[tree[rt].lson].sum + tree[tree[rt].rson].sum;
return rt;
}

区间更新操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int update(int p, int s, int t, ll v)
{
int rt = ++tot;
tree[rt] = tree[p];
tree[rt].sum += v * (min(tree[rt].r, t) - max(tree[rt].l, s) + 1); // note: update all the sum on the way
if (tree[rt].l >= s && tree[rt].r <= t)
{
tree[rt].add += v; // note: sum has been updated above, so just update the tag
return rt;
}
int mid = (tree[rt].r + tree[rt].l) >> 1;
if (s <= mid)
tree[rt].lson = update(tree[rt].lson, s, t, v);
if (t > mid)
tree[rt].rson = update(tree[rt].rson, s, t, v);
// note: sum has been updated above, so don't have to push up
return rt;
}

沿路更新时,对于父亲节点而言,所加的值只是一部分区间的长度,切勿使用总长度相乘。

区间查询操作

1
2
3
4
5
6
7
8
9
10
11
12
13
ll query(int p, int s, int t)
{
if (tree[p].l >= s && tree[p].r <= t)
return tree[p].sum;
int mid = (tree[p].r + tree[p].l) >> 1;
ll ans = tree[p].add * (min(tree[p].r, t) - max(tree[p].l, s) + 1); // note: smaller field
// sum all the tag on the way
if (s <= mid)
ans += query(tree[p].lson, s, t);
if (t > mid)
ans += query(tree[p].rson, s, t);
return ans;
}

主函数

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
int main()
{
while (scanf("%d%d", &n, &m) != EOF)
{
tot = 0;
tim = 0;
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
rt[0] = build(1, n);
while (m--)
{
char o[2];
scanf("%s", &o);
if (o[0] == 'C')
{
int l, r;
ll d;
scanf("%d%d%lld", &l, &r, &d);
rt[tim + 1] = update(rt[tim], l, r, d);
++tim;
}
else if (o[0] == 'Q')
{
int l, r;
scanf("%d%d", &l, &r);
printf("%lld\n", query(rt[tim], l, r));
}
else if (o[0] == 'H')
{
int l, r, t;
scanf("%d%d%d", &l, &r, &t);
printf("%lld\n", query(rt[t], l, r));
}
else
{
scanf("%d", &tim);
tot = rt[tim + 1]; // note: recyle memory (important)
}
}
}
return 0;
}

注意事项

  • 本题需要回溯版本,且不会再回到新版本,因此完成回溯后新版本的内存可以被回收使用。若不回收,会造成MLE
文章作者: 会思考的下丘脑
文章链接: https://magicalsheep.cn/1173771742/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 小羊圈