题目
传送门 to luogu
思路
这思路真是绝了……我不知道该怎么说。
注意到左端点需要最小，所以我们一来先猜
l
=
1
l=1
l=1 。假如我们求出一个最小的
r
r
r 使得
[
l
,
r
]
[l,r]
[l,r] 中所有数的和超过
k
k
k ，那么这个和 最多是
k
+
1
k+1
k+1 。
同时，如果说
[
l
,
r
]
[l,r]
[l,r] 中所有数的和为
k
+
1
k+1
k+1 ，那么
[
l
,
r
−
1
]
[l,r-1]
[l,r−1] 的和一定是
k
−
1
k-1
k−1 。故
a
r
=
2
a_r=2
ar=2 。此时我们考虑将
l
l
l 增大一。如果
a
l
=
1
a_l=1
al=1 那么
[
l
+
1
,
r
]
[l+1,r]
[l+1,r] 已经是答案了。否则
[
l
+
1
,
r
+
1
]
[l+1,r+1]
[l+1,r+1] 的和是不小于
k
k
k 的。什么情况下这个和是
k
+
1
k+1
k+1 呢？就是
a
r
+
1
=
2
a_{r+1}=2
ar+1=2 的时候。
可以看到，一个区间
[
l
,
r
]
[l,r]
[l,r] 在满足
a
r
=
2
a_r=2
ar=2 且
k
−
1
=
∑
i
=
l
r
−
1
a
i
k-1=\sum_{i=l}^{r-1}a_i
k−1=∑i=lr−1ai 时，可以分成三种情况：
a
l
=
1
a_l=1
al=1 。此时
[
l
+
1
,
r
]
[l+1,r]
[l+1,r] 即为答案。
a
l
=
2
a_l=2
al=2 且
a
r
+
1
=
1
a_{r+1}=1
ar+1=1 。此时
[
l
+
1
,
r
+
1
]
[l+1,r+1]
[l+1,r+1] 即为答案。
a
l
=
a
r
+
1
=
2
a_l=a_{r+1}=2
al=ar+1=2 。此时令
l
′
=
l
+
1
,
r
′
=
r
+
1
l'=l+1,\;r'=r+1
l′=l+1,r′=r+1 ，对
[
l
′
,
r
′
]
[l',r']
[l′,r′] 递归执行分类。
显然只有一种情况要递归，我们只要能将其加速就好了。这种情况我们只需要问，
l
/
r
l/r
l/r 开始的连续的
2
2
2 有多少个？可以树状数组（或者线段树）上二分。求出第一个
r
r
r 同样方法。复杂度
O
[
(
n
+
m
)
log
n
]
\mathcal O[(n+m)\log n]
O[(n+m)logn] 。
代码
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std
;
typedef long long int_
;
inline int readint(){
int a
= 0; char c
= getchar(), f
= 1;
for(; c
<'0'||c
>'9'; c
=getchar())
if(c
== '-') f
= -f
;
for(; '0'<=c
&&c
<='9'; c
=getchar())
a
= (a
<<3)+(a
<<1)+(c
^48);
return a
*f
;
}
inline int qkpow(int_ b
,int_ q
,int Mod
){
int ans
= 1;
for(; q
; q
>>=1,b
=b
*b
%Mod
)
if(q
&1) ans
= ans
*b
%Mod
;
return ans
;
}
const int MaxN
= 21;
int bit
[1<<MaxN
], n
, m
, a
[1<<MaxN
];
void modify(int id
,int x
){
for(int i
=id
; i
<=n
; i
+=(i
&-i
))
bit
[i
] += x
;
}
int query(int id
){
int res
= 0;
for(int i
=id
; i
; i
-=(i
&-i
))
res
+= bit
[i
];
return res
;
}
int findS(int s
){
int x
= 0, now
= 0;
for(int j
=MaxN
-1; j
>=0; --j
)
if((1<<j
)+x
<= n
&& bit
[x
+(1<<j
)]+now
< s
)
now
+= bit
[x
+= (1<<j
)];
return x
+1;
}
int countTwo(int id
){
int x
= 0, now
= -query(id
-1);
for(int j
=MaxN
-1; j
>=0; --j
)
if((1<<j
)+x
<= n
)
if((1<<j
)+x
< id
|| bit
[x
+(1<<j
)]+now
== 2*((1<<j
)+x
-id
+1))
now
+= bit
[x
+= (1<<j
)];
return x
;
}
char zhihucuan
[1<<10];
int main(){
n
= readint(), m
= readint();
for(int i
=1; i
<=n
; ++i
)
modify(i
,a
[i
] = readint());
while(m
--){
scanf("%s",zhihucuan
);
char opt
= *zhihucuan
;
if(opt
== 'C'){
int t
= readint();
modify(t
,-a
[t
]);
modify(t
,a
[t
] = readint());
}
if(opt
== 'A'){
int s
= readint();
int r
= findS(s
);
if(r
== n
+1 || !s
){
puts("none");
continue;
}
if(query(r
) == s
){
printf("1 %d\n",r
);
continue;
}
if(a
[1] == 1){
printf("2 %d\n",r
);
continue;
}
int cnt1
= countTwo(1);
int cnt2
= countTwo(r
);
if(cnt1
< cnt2
-r
+1)
printf("%d %d\n",cnt1
+2,r
+cnt1
);
else{
if(cnt2
== n
) puts("none");
else printf("%d %d\n",cnt2
-r
+2,cnt2
+1);
}
}
}
return 0;
}
