头像

幽梦影情结




离线:1小时前


最近来访(245)
用户头像
InvolutionZ
用户头像
R虎虎生威R
用户头像
Kazimierz
用户头像
ddddyx
用户头像
风小息
用户头像
溯月
用户头像
水木_7
用户头像
acwing_2661
用户头像
KissKernel
用户头像
狐誩.
用户头像
一吱小晨
用户头像
Aurora-
用户头像
fun
用户头像
sayoriqwq
用户头像
shengshu_
用户头像
hncsxzx
用户头像
弥弥弥弥弥弥弥弥弥弥
用户头像
辣鸡号航母
用户头像
梦忆晴天
用户头像
CE_King


事实就是,快排太难了2333(笑

快排就是分治嘛,以一个数为边界,分两边,一直分,一直排,排到最后一层有效的两个数,顺序也就出来了。
边界确实有点恶心,好吧,一年前的我也没有把题解吃透吧hh
我们要做的就是使得分治得两个区间内部不一定有序,但总体满足一个性质,左边的数<= x,右边的数>=x,这个x理论上取序列中哪个值都是可以的。但是取的不好也会影响递归的层数,往下看吧(笑
理论上如果我们每次以区间中间的数为边界进行递归,那最多就logn次,分成的同一层的区间,第一层是[0, n - 1], 第二层是[0, n / 2 - 1], [n / 2, n - 1], 第三层就是四份嘛,每一份在扫面过程中至多扫描n/(2 ^ t - 1) 次, t为层数,所以每一层还是O(n)的时间复杂度,总的时间复杂度是O(nlogn)
至于O(n^2),还是得模拟啊2333,恰好找到的数是最大的话,就会嘎嘎递归了
那就来模拟一下吧(笑
10个数
49 59 88 37 98 97 68 54 31 3
按照模板int x = a[l + r >> 1];取中间的数,会取到98
这是最大的数,所有的数都是小于等于它的
do ll++; while(a[ll] < x);
do rr--; while(a[rr] > x);
ll指针会一直走到98所在的位置,数组下标为4,而rr指针因为do while循环动一次指到3,数组下标为9,这一轮循环结束后
49 59 88 37 3 97 68 54 31 98
quick_sort(a, l, rr), quick_sort(a, rr + 1, r);
可以发现rrr相等,都是9,所以没有实现分治的目标。
进入下一次递归,rr指针至少左移一个位置,因为上一次循环已经把最大的移到最右边了,如果找的的数又是剩余的数(除去98最大的),那rr指针只会左移一个单位。这样又等价于没实现分治,这样就会有n次“递归”,时间复杂度就是O(n^2)

#include<iostream>
using namespace std;
const int N = 100010;
int a[N], b[N], c[N];
int n, cnt;
void quick_sort(int a[], int l, int r){
    if(l >= r) return;
    int ll = l - 1, rr = r + 1;
    int x = a[l + r >> 1];
    int cnt1 = 0, cnt2 = 0, cnt3 = 0;
    for(int i = l; i <= r; i++){
        if(a[i] > x) c[cnt2++] = a[i]; // b, c为辅助数组嘛
        else if(a[i] < x) b[cnt1++] = a[i];
        else cnt3++;
    }
    int k = l;
    for(int i = 0; i < cnt1; i++)
        a[k++] = b[i];
    for(int i = 0; i < cnt3; i++)
        a[k++] = x;
    for(int i = 0; i < cnt2; i++)
        a[k++] = c[i]; 
    if(cnt3 > 1) cnt3 /= 2; //保证分的区间至少有一个数,否则陷入死循环,边界问题出不来了
                            //如果分的一段区间是相同的数,我们要保证能继续分治下去
                            //为什么取中间的数呢,分治嘛,这样分的少,hack数据,都是同一个数
                            //可以用下面注释的代码打打表看看
    quick_sort(a, l, l + cnt1 - 1 + cnt3), quick_sort(a, l + cnt1 + cnt3 , r);
    //cnt++;  
    //cout<<l<<" "<<l+ cnt1 + cnt3 - 1<<" "<<r<<" "<<x<<endl;
    // for(int i = l; i <= r; i++)
    //     cout<<a[i]<<" ";
    // cout<<endl;
    // if(cnt < 10)
    // quick_sort(a, l, l + cnt1 - 1 + cnt3), quick_sort(a, l + cnt1 + cnt3, r);
}
int main(){
    cin>>n;
    for(int i = 0; i < n; i++)
        cin>>a[i];
    quick_sort(a, 0, n - 1);
    for(int i = 0; i < n; i++)
        cout<<a[i]<<" ";
    return 0;
}



M题,扣1送小布丁,大水题,然而20分钟过去,还是有很多人没过,做题偶尔看下榜单啊,看下哪一题过的多,而且这题目很明显,ACM是计时的,先过了肯定用时少
A题,打印六边形,基础水题,如果你能很快写写完,说明你训练还是可以的。
B题,游卡打钱,大水题,唯一的卡点就是long long了,如果你基础不好,这场是有很多long long的,你需要思考一下了。
E题,旋转小火锅,基础语法题,字符串能做,但用scanf也能做,又是longlong,scanf("noodles[%lld]",&x);
G题,求极限,答案是1,注意负无穷
H题,Unhappy の RLJ很水的样子,没怎么看
K题,RLJ の 平衡树,先读前面的整数,再读小数点,再读后面的整数
L题,One Piece,事先给排好序了,也把特殊样例给了,过的人还不少,前两个数一定是a, b, c中的两个,最后一个数是和,这就很好做了。(2333,好像出的样例有点水了,找出a, b, c,别忘了排序
C题,氪金玩家,2333,又是我的锅了,数据范围写错了,m最大是两千,是原题,n钱买鸡的问题,大家可以到oj找找,有好几题
D题,小鱼会有危险嘛,大家好好想,不难,文末放一份同学的代码
F题,可以正向递归,开一个全局数组储存,也可以直接正向循环,及时更新状态,这俩都是一个思想,或者逆着做也可以,思想都是一样的。文末放两份同学的代码和递归代码
I题,模拟,四舍五入那有点问题,但看样例可知没有四舍五入,想想自己平时除法怎么做的,文末放一放代码
J题,就是 Fibonacci数列,不过数据太大不能用数组,可以打表找规律,也可以不断取模,三个数循环着做,文末放代码
N题,考到了排序,先将三个数组排序,思路:先在n个水系中选A个,不足A个补0,在m个火系宠物中选B个,不足补0,由于求的是最大和,便要替换这A个水系和B个火系,自然用k个蛋替换,排序后用k中没使用的天赋最高的分别与A,B中当前最小的做差,如差值为正,则替换差值最大的那个,注意下标,小心越界。这题看标准答案有一个结论,取前A个天赋值最高的水系宠物和前B个天赋值最高的火系宠物以及所有的宠物蛋。在这A+B+k个宠物中选出A+B个天赋值最高的即可,文末放代码

D题
#include<stdio.h>
int main()
{
    double s, x;
    scanf("%lf%lf", &s, &x);
    double len = 7;
    double sum = 0;
    while (sum <= s - x) { sum += len; len *= 0.98; }
    if (sum + len >= s + x) printf("n\n");
    else printf("y\n");
}

F题
递归做法
#include<stdio.h> 
long long a[100100]; //全局变量初始化是0
int cnt[100100];    //大数组开全局变量,自己百度程序中的堆,栈
int n; 
int f(int x){
    if(x == n || a[x] > a[x + 1]) cnt[x] = 1;
    else cnt[x] = f(x + 1) + 1;
    return cnt[x]; 
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%lld", &a[i]);
    }
    for(int i = 1; i <= n; i++){
        if(!cnt[i]) f(i);
    }
    for(int i = 1; i <= n; i++){
        printf("%d\n", cnt[i]);
    }

    return 0;
}

虽然是c++代码,但只是输入输出不太一样而已,自己百度一下cin,cout吧
#include <iostream>
#include <string>

using namespace std;

long long map[100007];
int ans[100007];

int main() {
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>map[i];
    ans[n]=0;
    for(int i=n-1;i>=0;i--)
    {
        if(map[i]<=map[i+1])
        {
            ans[i]=ans[i+1]+1;
        }else{
            ans[i]=1;
        }
    }
    for(int i=0;i<n;i++)  cout<<ans[i]<<endl;
    return 0;
}


这个方法甚至不需要开数组,很不错
#include<iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    long long last;
    long long t;
    int cnt = 1;
    cin >> t;   

    for(int i = 1; i < n; i++ )
    {
        last = t;
        cin >> t;
        if(t >= last)
        {
            cnt++;

        }
        else
        {
            for(int j =cnt; j >0; j --)
                cout << j << endl;
            cnt = 1;
        }
    }
    for(int j =cnt; j >0; j --)
                cout << j << endl;
    return 0;
}

I题
#include<stdio.h>
int main(){
    int n, k, m;
    scanf("%d%d", &n, &k);
    long long t = 0;
    for(int i = 1; i <= n; i++){
        scanf("%d", &m);
        t += m;
    }
    printf("%lld", t/n);
    printf(".");
    long long temp = t % n;
    for(int i = 0; i < k; i++){
        temp *= 10;
        printf("%lld", temp/n);
        temp %= n;
    }
    return 0;
}

J题
#include<stdio.h>

int main()
{
    int n;
    while(scanf("%d", &n) != EOF)
    {
        int a = 7, b = 11, c = 0;

        if(n == 0) {
            printf("no\n");    
        }else if(n == 1) {
             printf("no\n"); 
        }else{
            for(int i = 2; i <= n; i ++) {
                c = (a+b) % 3;
                a = b % 3;
                b = c % 3;
            }
            if(c%3 == 0)  printf("yes\n");  
            else  printf("no\n");  
        }
    }
}

N题
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;  
int a[N], b[N], c[N];
bool cmp(int a, int b){
    return a > b;
}
int main(){
    int n, m, s1, s2, s3;
    cin>>n>>m>>s1>>s2>>s3;
    for(int i = 1; i <= s1; i++)
        cin>>a[i];
    for(int i = 1; i <= s2; i++)
        cin>>b[i];
    for(int i = 1; i <= s3; i++)
        cin>>c[i];
    sort(a + 1, a + s1 + 1, cmp);    // 降序排列,可用冒泡排序替换
    sort(b + 1, b + s2 + 1, cmp);
    sort(c + 1, c + s3 + 1, cmp);
    int r1 = n, r2 = m;
    for(int i = 1; i <= s3; i++){
        if(c[i] > a[r1] && c[i] > b[r2] && r1 && r2){  
            if(a[r1] > b[r2]){
                b[r2--] = c[i];  
            }else{
                a[r1--] = c[i];
            }
        }else if(c[i] > a[r1] && r1){
            a[r1--] = c[i];
        }else if(c[i] > b[r2] && r2)
            b[r2--] = c[i];

    }
    long long sum = 0;
    for(int i = 1; i <= n; i++)
        sum += a[i];
    for(int i = 1; i <= m; i++)
        sum += b[i];
    cout<<sum;
    return 0;
}


新鲜事 原文

AcWing《秋招每日一题(Java/C++)》拼团优惠!https://www.acwing.com/activity/content/introduction/2171/group_buy/95655/


新鲜事 原文

AcWing《秋招每日一题(Java/C++)》拼团优惠!https://www.acwing.com/activity/content/introduction/2171/group_buy/95655/



题目描述

You are given 4 positive integers a, b, c, d with a<c and b<d.
Find any pair of numbers x and y that satisfies the following conditions:
1. a<x≤c, b<y≤d,
2. x⋅y is divisible by a⋅b .
Note that required x and y may not exist.

样例

10
1 1 2 2
3 4 5 7
8 9 15 18
12 21 14 24
36 60 48 66
1024 729 373248 730
1024 729 373247 730
5040 40320 40319 1000000000
999999999 999999999 1000000000 1000000000
268435456 268435456 1000000000 1000000000



2 2
4 6
12 12
-1 -1
-1 -1
373248 730
-1 -1
15120 53760
-1 -1
536870912 536870912


算法

(数论) $O(sqrt(a) + sqrt(b) + 1344 ^ 2)$

① x * y % (a * b) == 0
② x * gcd(y, a * b) % (a * b) == 0
由①可以推出②,为什么呢?
将 x, y, (a * b)分解成质数相乘的形式,则一定会除完一定有剩余,
因为 x * y == k * (a * b)) (k >= 2)
gcd(y, a * b) 相当于将这两个数的共有的质数都提取出来了(一个质数可以被提取若干次),
则等价于 y 的对与①式的贡献,所以①可以推出②

所以 x % ((a * b) / gcd(y, a * b)) == 0
设(a * b) / gcd(y, a * b)为s
则 x == k * s (k >= 1)
要确保 x > a && x <= c
我们不妨找这其中满足条件的最大的一个,即为x = c / s * s,这样下取整保证了x <= c
那么只需要比较x和a的关系

至于gcd(y, a * b),
可得 a * b % (gcd(y, a * b)) == 0
为什么呢
gcd(y, a * b)属于是 a * b的因子啊(笑
根据统计10^9内的数的最多的因子的个数为1344个

我们找出 a 和 b 的所有因子,组成乘积,则为gcd(y, a * b)的值,在遍历过程中有可能遇到
其值为 y 的情况,则求出y。
同样的,找出满足条件的最大的一个,y = d / s * s;

参考文献 https://codeforces.com/blog/entry/108101

C++ 代码

#include<iostream>
using namespace std;
const int N = 1350;
long long d1[N], d2[N];
int cnt1, cnt2;
long long a, b, c, d;
void divide(long long t[], int &cnt, int k){
    for(int i = 1; i <= k / i; i++){
        if(k % i == 0){
            t[cnt++] = i;
            t[cnt++] = k / i;
        }
    }
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>a>>b>>c>>d;
        cnt1 = cnt2 = 0;
        divide(d1, cnt1, a);
        divide(d2, cnt2, b);
        long long kk = -1, uu = -1;
        bool flag = false;
        for(int i = 0; i < cnt1; i++){
            for(int j = 0; j < cnt2; j++){
                long long k = d1[i] * d2[j];
                long long u = (a * b) / k;
                u = d / u * u;
                k = c / k * k;
                if(k * u % (a * b) == 0 && k > a  && u > b ){
                    kk = k, uu = u;
                    flag = true;
                    break;
                }

            }
            if(flag) break;
        }
        cout<<kk<<" "<<uu<<endl;
    }
    return 0;
}
呜呜呜数论好难,感觉上应该写对了吧(笑,格式确实不好看,回来再改吧(笑



活动打卡代码 AcWing 484. 过河

半野生做法吧,然而我现在不想论证它的正确性2333😁

#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
const int N = 2110;
int a[N], d[N];
bool b[N];
int f[N];
int main(){
    int len;
    cin>>len;
    int l, r, t;
    cin>>l>>r>>t;
    for(int i = 1; i <= t; i++)
        cin>>a[i];
    a[t + 1] = len;
    sort(a, a + t + 2);
    int cnt = 0;
    for(int i = 0; i <= t; i++){
        int k = a[i + 1] - a[i];
        int pre = k;
        k %= r;
        if(k == 0) k = r;
        k += r;
        if(k > pre) k = pre;
        d[i] = k;

    }
    for(int i = 0; i <= t; i++){
        a[i + 1] = a[i] + d[i];
        if(i != t)
        b[a[i + 1]] = true;
    }
//  for(int i = 0; i <= t + 1; i++)
//      cout<<a[i]<<" ";
//  cout<<endl;
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for(int i = 0; i <= a[t + 1] + 11; i++){
        if(b[i]) f[i]++;
        for(int j = l; j <= r; j++)
            f[i + j] = min(f[i], f[i + j]);
    }
    int mn = 0x3f3f3f3f;
    for(int i = a[t + 1]; i <= a[t + 1] + 11; i++)
        mn = min(mn, f[i]);
    cout<<mn;
    return 0;
}


活动打卡代码 AcWing 247. 亚特兰蒂斯

艰难方显勇毅了属于😃

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 10010;
struct ss{
    double y1, y2, x;
    int d;
}node[N * 2];
struct k{
    int l, r, cnt;
    double len;
}tr[N * 8];
vector<double>y;
bool cmp(ss s1, ss s2){
    return s1.x < s2.x;
}
void build(int u, int l, int r){
    tr[u] = {l, r};
    if(l != r){
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    }
}
int find(double k){
    return lower_bound(y.begin(), y.end(), k) - y.begin();
}
void pushup(int u){
    if(tr[u].cnt){
        tr[u].len = y[tr[u].r + 1] - y[tr[u].l];
    }else if(tr[u].l != tr[u].r){
        tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
    }else{
        tr[u].len = 0;
    }
}
void modify(int u, int l, int r, int k){
    if(tr[u].l >= l && tr[u].r <= r){
        tr[u].cnt += k;
        pushup(u);
    }else{
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) modify(u << 1, l, r, k);
        if(r > mid) modify(u << 1 | 1, l, r, k);
        pushup(u);
    }
}
int main(){
    int n;
    int T = 0;
    while(scanf("%d", &n), n){
        y.clear();
        int j = 0;
        T++;
        double x1, y1, x2, y2;
        for(int i = 1; i <= n; i++){
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            y.push_back(y1), y.push_back(y2);
            node[j++] = {y1, y2, x1, 1};
            node[j++] = {y1, y2, x2, -1};
        }
        sort(node, node + j, cmp);
        sort(y.begin(), y.end());
        y.erase(unique(y.begin(), y.end()), y.end());
        int s = y.size();
        build(1, 0, s - 2);
        double res = 0;
        for(int i = 0; i < j; i++){
            if(i != 0) res += tr[1].len * (node[i].x - node[i - 1].x);
            modify(1, find(node[i].y1), find(node[i].y2) - 1, node[i].d);
        }
        printf("Test case #%d\n", T);
        printf("Total explored area: %.2f\n\n", res);
    }
    return 0;
}




冲冲冲

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 100010;
typedef long long LL;
struct node{
    int l, r;
    LL sum, add;
}tr[N * 4];
int a[N];
void build(int u, int l, int r){
    if(l == r){
        tr[u] = {l, r, a[l], 0};
        return;
    }else{
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        tr[u] = {l, r};
        tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    }
}
void pushup(node& root, node& left, node& right){
    root.sum = left.sum + right.sum;
}
void pushup(int u){
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void pushdown(int u){
    tr[u << 1].add += tr[u].add;
    tr[u << 1 | 1].add += tr[u].add;
    tr[u << 1].sum += (LL)(tr[u].add) * (tr[u << 1].r - tr[u << 1].l + 1);
    tr[u << 1 | 1].sum += (LL)(tr[u].add) * (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1);
    tr[u].add = 0;
}
LL query(int u, int l, int r){
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    int mid = tr[u].l + tr[u].r >> 1;
    LL k = 0;
    pushdown(u);
    if(l <= mid) k = query(u << 1, l, r);
    if(r > mid) k += query(u << 1 | 1, l, r);
    return k;
}
void modify(int u, int l, int r, LL k){
    if(tr[u].l >= l && tr[u].r <= r){
        tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * k;
        tr[u].add += k;
    }else{
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) modify(u << 1, l, r, k);
        if(r > mid) modify(u << 1 | 1, l, r, k);
        pushup(u);
    }
}
int main(){
    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    build(1, 1, n);
    int l, r, k;
    char op[2];
    while(m--){
        scanf("%s%d%d", op, &l, &r);
        if(*op == 'Q'){
            printf("%lld\n", query(1, l, r));
        }else{
            scanf("%d", &k);
            modify(1, l, r, k);
        }
    }
}



确实难啊2333🤣

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 500010;
typedef long long LL;
struct node{
    int l, r;
    LL sum, d;
}tr[N * 4];
LL a[N];
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 k = a[r] - a[r - 1];
        tr[u] = {l, r, k, k};
        return;
    }else{
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        tr[u].l = l, tr[u].r = r;
        pushup(u);
    }
}
void modify(int u, int x, LL k){
    if(tr[u].l == x && tr[u].r == x){
        tr[u].sum += k;
        tr[u].d += k;
    }else{
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) modify(u << 1, x, k);
        else modify(u << 1 | 1, x, k);
        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);
        if(l > mid) return query(u << 1 | 1, l, r);
        node temp1, temp2, temp3;
        temp1 = query(u << 1, l, r);
        temp2 = query(u << 1 | 1, l, r);
        pushup(temp3, temp1, temp2);
        return temp3;
    }
}
int main(){
    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    build(1, 1, n);
    char op[2];
    int l, r;
    LL k;
    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", &k);
            modify(1, l, k);
            if(r + 1 <= n) modify(1, r + 1, -k);
        }
    }
    return 0;
}



good😀

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 500010;
struct node{
    int l, r;
    int sum, lm, rm, tx;
}tr[N * 4];
int a[N];
void pushup(int u, int l, int r){
    tr[u].sum = tr[l].sum + tr[r].sum;
    tr[u].lm = max(tr[l].sum + tr[r].lm, tr[l].lm);
    tr[u].rm = max(tr[r].sum + tr[l].rm, tr[r].rm);
    tr[u].tx = max(max(tr[l].tx, tr[r].tx), tr[l].rm + tr[r].lm);

}
void pushup(int u){
    pushup(u, u << 1, u << 1 | 1);
}
void build(int u, int l, int r){
    tr[u] = {l, r, a[r], a[r], a[r], a[r]};
    if(l == r) return;
    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 k){
    if(tr[u].l == x && tr[u].r == x){
        tr[u] = {tr[u].l, tr[u].r, k, k, k, k};
        return;
    }else{
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) modify(u << 1, x, k);
        else modify(u << 1 | 1, x, k);
        pushup(u);
    }
}
node query(int u, int l, int r){
    if(tr[u].l >= l && tr[u].r <= r)
        return tr[u];
    int mid = tr[u].l + tr[u].r >> 1;
    node temp1, temp2;
    bool flag1 = false, flag2 = false;
    if(l <= mid){
        flag1= true;
        temp1 = query(u << 1, l, r);
    } 
    if(r > mid){
        flag2 = true;
        temp2 = query(u << 1 | 1, l, r);
    }
    node temp3;
    if(flag1 && flag2){
        temp3.l = temp1.l;
        temp3.r = temp2.r;
        temp3.sum = temp1.sum + temp2.sum;
        temp3.lm = max(temp1.sum + temp2.lm, temp1.lm);
        temp3.rm = max(temp2.sum + temp1.rm, temp2.rm);
        temp3.tx = max(max(temp1.tx, temp2.tx), temp1.rm + temp2.lm);
        return temp3;
    }
    if(flag1) return temp1;
    else return temp2;
}
int main(){
    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    build(1, 1, n);
    int u, x, y;
    while(m--){
        scanf("%d%d%d", &u, &x, &y);

        if(u == 2){
            modify(1, x, y);
        }else{
            if(x > y) swap(x, y);
            auto k = query(1, x, y);
            printf("%d\n", k.tx);
        }
    }
    return 0;
}