csoj_324

过年分块写挂了的

#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;

const int maxm=1e5+9;

template <class T> inline T read(const T sample) {
    T x=0; int f=1; char s;
    while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
    while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
    return x*f;
}
template <class T> inline void write(const T x) {
    if(x<0) return (void) (putchar('-'),write(-x));
    if(x>9) write(x/10);
    putchar(x%10^48);
}

struct tree{int v,l,r;}tr[maxm*400];
struct operat{int type,x,y;}q[maxm];
int n,m,a[maxm],b[maxm*2],rt[maxm],qs[maxm],tot,cn,tmp[2][23],cnt[2],len;
void change(int &now,int l,int r,int pos,int val){
    if(!now)now=++cn;
    tr[now].v+=val;
    if(l==r)return ;
    int mid=(l+r)>>1;
    if(pos<=mid)change(tr[now].l,l,mid,pos,val);
    else change(tr[now].r,mid+1,r,pos,val);
}

void pre_change(int x,int val){
    int k=std::lower_bound(b+1,b+1+tot,a[x])-b;
    for(int i=x;i<=n;i+=lowbit(i))change(rt[i],1,tot,k,val);
}

int query(int l,int r,int k){
    if(l==r){return b[l];}
    int mid=(l+r)>>1,sum=0;
    for(int i=1;i<=cnt[1];++i)sum+=tr[tr[tmp[1][i]].l].v;
    for(int i=1;i<=cnt[0];++i)sum-=tr[tr[tmp[0][i]].l].v;
     if (k<=sum)
    {
        for (int i=1;i<=cnt[1];i++) tmp[1][i]=tr[tmp[1][i]].l;
        for (int i=1;i<=cnt[0];i++) tmp[0][i]=tr[tmp[0][i]].l;
        return query(l,mid,k);
    }
    else
    {
        for (int i=1;i<=cnt[1];i++) tmp[1][i]=tr[tmp[1][i]].r;
        for (int i=1;i<=cnt[0];i++) tmp[0][i]=tr[tmp[0][i]].r;
        return query(mid+1,r,k-sum);
    }
}

int pre_query(int l,int r,int k){
    memset(tmp,0,sizeof(tmp));
    cnt[1]=cnt[0]=0;
    for(int i=r;i;i-=lowbit(i))tmp[1][++cnt[1]]=rt[i];
    for(int i=l-1;i;i-=lowbit(i))tmp[0][++cnt[0]]=rt[i];
    return query(1,tot,k);
}

int main()
{
    n=read(1),m=read(1);
    len=n;
    for(int i=1;i<=n;++i)qs[i]=b[i]=a[i]=read(1);
    for(int i=1,x,y,z;i<=m;++i){
        x=read(1),y=read(1),z=read(1);
        q[i]={x,y,z};
        if(x==1){
            qs[y]+=z;
            b[++len]=qs[y];
        }
    }
    sort(b+1,b+1+len);
    tot=unique(b+1,b+1+len)-b-1;
    for(int i=1;i<=n;++i)pre_change(i,1);
    for(int i=1;i<=m;++i){
        if(q[i].type==2){
            bool ok=0;
            ll k=q[i].y-q[i].x+1;
            if(k<3){
                write(0),putchar('\n');
                continue;
            }
            ll a=pre_query(q[i].x,q[i].y,k),b=pre_query(q[i].x,q[i].y,k-1),c=pre_query(q[i].x,q[i].y,k-2);
            k-=2;
            while(k){
                if(b+c>a){ok=1;break;}
                a=b,b=c,k-=1;
                if(k)c=pre_query(q[i].x,q[i].y,k);
            }
            write(ok?a+b+c:0),putchar('\n');
        }
        else{
            pre_change(q[i].x,-1);
            a[q[i].x]+=q[i].y;
            pre_change(q[i].x,1);
        }
    }
    return 0;
}