好印象深刻的题，前天选拔赛给跪了。怪我这种关键题没敲出来。
题意很简单，给你一串无规则的数列，再给个m值，求出满足 数列和>=m的长度最小的连续子串。。。确实一开始卡住了，因为看数据肯定是nlogn的算法才能过，我和聪哥坐在外面的楼梯上，想了各种方法，我就一直在想前缀和以及 先求出最长连续和 再两边删减等等，刚提出来 就马上否定了。。后来还是聪哥想出个比较靠谱的方案，即二分结果，然后对二分出来的结果 先枚举右端点，再通过二分的结果得到左端点，找到左端点和右端点中间最小的前缀和，用左端点的前缀和 减去 最小的前缀和，如果结果>=m,意味着该二分结果可行，可以继续缩小下去，否则说明不行。
然后我就敲了，结果一直WA，后来知道自己哪里傻逼了，我对二分出来的len，在枚举右端点的时候，直接就是从len到n，0-(len-1)这里就没有枚举右端点，事实是，可能恰好结果就在0-(len-1），真是傻逼
不过这个算法确实是正确的，但还是有时限问题 因为多了个二分，其时间复杂度就变成了 n*logn*logn,所以只好聪哥改了我上面的漏洞之后，果然A了，不过用了1.7s，而且，之后我再提及他的同样的代码，就TLE了，估计是UVA的机器突然又跑慢了。所以这个算法还是有问题的。
后来跟聪哥讨论后觉得二分可能可以去掉不要，确实可以去掉。。。我又傻逼了，这么简单问题没想到，预处理完suffix前缀和之后，题目不就是要求suffix[右端点]-suffix[i]>=m，满足这个条件的 离右端点的最近的点，也就是说 我令 val=suffix[i]<=suffix[右端点]-m，即求离右端点最近的满足>=val的suffix所在的点，如果我线段树里面维护的是suffix的最小值，那么我为了求离右端点最近的，我肯定是对 线段树这样query：假如当前右子树满足 >=val,则优先走右子树，否则如何左子树>=val,则走左子树，如果左右都走不了 就是-1了
这样得到的值必定是离右端点最近的啊啊啊啊。
我真是傻逼
这是之前的思路 算法正确 但是会TLE
#include <iostream>
#include <cstdio>
#define N 500010
#define LL long long
#define lson rt<<1,l,mid
#define rson (rt<<1|1),mid+1,r
using namespace std;
LL suffix[N];
int n,m;
LL tree[N*];
void build(int rt,int l,int r)
{
if (l>=r){
tree[rt]=suffix[l];
return;
}
int mid=(l+r)>>;
build(lson);
build(rson);
if (tree[rt<<]>tree[rt<<|])
tree[rt]=tree[rt<<|];
else
tree[rt]=tree[rt<<];
}
LL query(int L,int R,int rt,int l,int r)
{
if (L<=l && r<=R){
return tree[rt];
}
int mid=(l+r)>>;
if (R<=mid){
return query(L,R,lson);
}
if (L>mid){
return query(L,R,rson);
}
return min(query(L,R,lson),query(L,R,rson));
}
int ok(int x)
{
for (int i=;i<=n;i++){ //这里应该从前面开始枚举，比赛的时候就是直接从len开始枚举，导致一直WA。。。虽然改了也不一定会避免时限超时，但总归这样是我敲错了，那样是我们思路错了，性质不一样。
int j=i-x;
if (j<) j=;
LL mini;
if (i==) mini=;
else
mini=query(j,i-,,,n);
if (suffix[i]-mini>=m) return ;
}
return ;
} int main()
{
int t;
scanf("%d",&t);
while (t--){
suffix[]=;
scanf("%d%d",&n,&m);
bool isok=;
for (int i=;i<=n;i++){
scanf("%lld",&num[i]);
suffix[i]=suffix[i-]+num[i];
if (num[i]>=m) isok=;
}
if (isok){
puts("");
continue;
}
if (m<=){
puts("-1");
continue;
}
build(,,n);
int L=,R=n+,mid;
bool flag=;
int ans=-;
while (L<R)
{
mid=(L+R)>>;
if (ok(mid)){
flag=;
ans=mid;
R=mid;
}
else
L=mid+;
}
if (!flag){
puts("-1");
}
else
printf("%d\n",ans);
}
return ;
}
/*
7 7
3 -2 1 6 1 -2 3
*/
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
#define N 500010
#define LL long long
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
LL suffix[N];
int n,m;
LL tree[N*];
void build(int rt,int l,int r)
{
if (l>=r){
tree[rt]=suffix[l];
return;
}
int mid=(l+r)>>;
build(lson);
build(rson);
if (tree[rt<<]>tree[rt<<|])
tree[rt]=tree[rt<<|];
else
tree[rt]=tree[rt<<];
}
int query(LL val,int L,int R,int rt,int l,int r)
{
if (l>=r)
return l;
int mid=(l+r)>>;
int ret1=-,ret2=-;
if (mid<R) //因为是从顶点开始搜索起的，所以用L和R来控制区间
if(val>=tree[rt<<|]){ //优先找右子树，就能得到最近的点
ret1=query(val,L,R,rson);
}
if (L<=mid)
if (val>=tree[rt<<]){
ret2=query(val,L,R,lson);
}
int ret=max(ret1,ret2);
return ret;
}
int main()
{
int t;
scanf("%d",&t);
while (t--){
suffix[]=;
scanf("%d%d",&n,&m);
bool isok=;
for (int i=;i<=n;i++){
scanf("%lld",&suffix[i]);
if (suffix[i]>=m) isok=;
suffix[i]+=suffix[i-];
}
if (isok){
puts("");
continue;
}
if (m<=){
puts("-1");
continue;
}
build(,,n);
int ans=N;
for (int i=;i<=n;i++){
LL v=suffix[i]-m;
int res=query(v,,i-,,,n); //对每个v 在 0到 i-1的区间里，从线段树的顶点开始搜索起，得到离右端点最近的点。
if (res!=-) ans=min(ans,i-res);
// cout<<i<<" "<<res<<endl;
}
if (ans==N) ans=-;
printf("%d\n",ans);
}
return ;
}