内容发布更新时间 : 2024/11/15 21:29:55星期一 下面是文章的全部内容请认真阅读。

输入格式

第一行一个整数n。

下面每行，一个数x。

如果x=0，表示这个节点非叶子节点，递归地向下读入其左孩子和右孩子的信息，如果x≠0，表示这个节点是叶子节点，权值为x。 输出格式

输出一个整数，表示最少有多少逆序对。 样例输入 3 0 0 3 1 2 样例输出 1

数据规模与约定

对于20%的数据，n <= 5000。

对于100%的数据，1 <= n <= 200000，0 <= a[i]<2^31。 该题暂时没有人完全正确，暂时没有该语言的参考程序。

编号：ALGO-8 题目：操作格子 关键字：线段树 类型：普通试题

问题描述

有n个格子，从左到右放成一排，编号为1-n。

共有m次操作，有3种操作类型：

1.修改一个格子的权值，

2.求连续一段格子权值和，

3.求连续一段格子的最大值。

对于每个2、3操作输出你所求出的结果。 输入格式

第一行2个整数n，m。

接下来一行n个整数表示n个格子的初始权值。

接下来m行，每行3个整数p,x,y，p表示操作类型，p=1时表示修改格子x的权值为y，p=2时表示求区间[x,y]内格子权值和，p=3时表示求区间[x,y]内格子最大的权值。 输出格式

有若干行，行数等于p=2或3的操作总数。

每行1个整数，对应了每个p=2或3操作的结果。 样例输入 4 3 1 2 3 4 2 1 3

1 4 3 3 1 4 样例输出 6 3

数据规模与约定

对于20%的数据n <= 100，m <= 200。 对于50%的数据n <= 5000，m <= 5000。

对于100%的数据1 <= n <= 100000，m <= 100000，0 <= 格子权值 <= 10000。 本题的Java参考代码如下： import .*; import .*;

public class Main {

final static int MAX_N = 100007;

class Node {

int l, r; int sum, max; Node () { }

Node (int _l, int _r, int _s, int _m) {

l = _l; r = _r; sum = _s; max = _m;

}

}

int n, m;

Node tree[] = new Node[MAX_N << 2]; int a[] = new int[MAX_N];

void up(int id) { }

void build(int id, int l, int r) { }

void update(int id, int pos, int val) {

if (tree[id].l == tree[id].r) {

tree[id].sum = tree[id].max = val; return ;

tree[id] = new Node(l, r, 0, 0); if (l == r) { }

int mid = (l + r) >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); up(id);

tree[id].sum = tree[id].max = a[l]; return ;

tree[id].sum = tree[id << 1].sum + tree[id << 1 | 1].sum; tree[id].max = (tree[id << 1].max, tree[id << 1| 1].max);

}

}

int mid = (tree[id].l + tree[id].r) >> 1; if (pos <= mid) update(id << 1, pos, val); else update(id << 1 | 1, pos, val); up(id);

int sum(int id, int l, int r) { }

int max(int id, int l, int r) {

if (l <= tree[id].l && tree[id].r <= r) { }

int mid = (tree[id].l + tree[id].r) >> 1; if (r <= mid) return max(id << 1, l, r); else if (l > mid) return max(id << 1 | 1, l, r); else {

return tree[id].max;

if (l <= tree[id].l && tree[id].r <= r) { }

int mid = (tree[id].l + tree[id].r) >> 1; if (r <= mid) return sum(id << 1, l, r); else if (l > mid) return sum(id << 1 | 1, l, r); else { }

return sum(id << 1, l, mid) + sum(id << 1 | 1, mid + 1, r); return tree[id].sum;