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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
| #include <bits/stdc++.h>
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;
}
|