# 题目

{% fold 点击显/隐题目 %}

5 5 3 4 9 2 7 2 3 4 1 4 5 2 1 5 1 3 4 2 3 5
11 20 7
{% endfold %}

# 代码

{% fold 点击显/隐代码 %}```cpp 最讨厌的“2” https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
#include
#include
#include
const int maxn = 2e5 + 5;

typedef long long LL;

int n, m;
LL a[maxn];

char c;
LL ans = 0;
while (c = getchar(), !(c >= '0' && c <= '9'))
;
while (c >= '0' && c <= '9') {
ans *= 10;
ans += (int)c - '0';
c = getchar();
}
return ans;
}
long long add(long long a, long long b) { return a + b; }

class ST {
struct Tree {
int l, r;
LL n;
};

``````Tree T[maxn * 8];
``````

public:
inline static int getLastRowBeginPosition(int n) {
int ans = 1 << ((int)(log(n) / log(2)));
if (ans < n)
ans <<= 1;
return ans;
}
LL BuildTree(int a, int b, LL (*compare)(LL, LL), LL *num, int pos = 1) {
// printf("build(%d,%d,%d)\n", a, b, pos);

``````    T[pos].l = a;
T[pos].r = b;

if (a == b) {
if (a > n)
return T[pos].n = 0;
else
return T[pos].n = num[a];
}

int mid = (a + b) >> 1;
int leftchild = pos << 1;
int rightchild = (pos << 1) + 1;

return T[pos].n =
compare(BuildTree(a, mid, compare, num, leftchild),
BuildTree(mid + 1, b, compare, num, rightchild));
}

LL query(int a, int b, LL (*compare)(LL, LL), LL *num, int pos = 1) {
// printf("query(%d,%d,%d)\n", a, b, pos);

if (a == b)
return T[getLastRowBeginPosition(n) - 1 + a].n;

if (T[pos].n == 0)
return 0;

int &l = T[pos].l;
int &r = T[pos].r;

if (a == l && b == r)
return T[pos].n;

int mid = (l + r) >> 1;
int leftchild = pos << 1;
int rightchild = (pos << 1) + 1;

if (b <= mid)
return query(a, b, compare, num, leftchild);
if (a > mid)
return query(a, b, compare, num, rightchild);
return compare(query(a, mid, compare, num, leftchild),
query(mid + 1, b, compare, num, rightchild));
}

LL update(int a, int b, LL (*compare)(LL, LL), LL *num, int pos = 1) {
// printf("     update(%d,%d,%d)\n", a, b, pos);

int &l = T[pos].l;
int &r = T[pos].r;

if (l == r)
return T[pos].n >>= 1;

if (T[pos].n == 0)
return 0;

int mid = (l + r) >> 1;
int leftchild = pos << 1;
int rightchild = (pos << 1) + 1;

if (b <= mid) {
T[pos].n =
compare(update(a, b, compare, num, leftchild), T[rightchild].n);
} else if (a > mid) {
T[pos].n =
compare(T[leftchild].n, update(a, b, compare, num, rightchild));
} else {
T[pos].n = compare(update(a, mid, compare, num, leftchild),
update(mid + 1, b, compare, num, rightchild));
}
return T[pos].n;
}

void printTree() {
for (int i = 1; i < getLastRowBeginPosition(n) << 1; ++i) {
if ((i > 0) && (i & (i - 1)) == 0)
printf("\n");
printf("[%d (%d,%d) %I64d] ", i, T[i].l, T[i].r, T[i].n);
}
printf("\n");
}
``````

};

ST tree;

int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
//int START = clock();
while (~scanf("%d%d", &n, &m)) {
for (int i = 1; i <= n; ++i) {
scanf("%I64d", &a[i]);
// printf("%d\n",i);
}
// tree.printTree();
for (int i = 1; i <= m; ++i) {
int c, l, r;
scanf("%d%d%d", &c, &l, &r);
if (c == 1)
`{% endfold %}`