题目链接

分析

这个就比较简单了，转换问题就是：
求一段最长的连续序列，使得这段序列的前缀(+s) >= 0;

前缀的话我们可以考虑用前缀和快速计算；
暴力的想我们去枚举每个字段，然后判断字段的所有前缀是否都>=0就行；
显然这样是O(n^3)的；

考虑优化：
首先发现固定左端点后，我们的右端点是有单调性的；
（因为对于r只要出现一个前缀<0，则r’(>r)的都不满足）
所以我们可以枚举左端点，然后二分右端点；

其次，要使得[l,r]的所有前缀都>=0，即前缀的最小值都要>=0；
所以我们可以维护前缀的最小值（线段树/树状数组/RMQ），每次快速查询；

这样时间复杂度是：O(n*log(n)*log(n))

注意二分的写法…

代码

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<map>
#include<algorithm>
#include<deque>
#include<stack>
#include<set>
// #include 
#include<math.h>
#include<string.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
 
#define pb push_back
#define coutl cout<<"------------"<<endl;
#define fi first
#define se second

#define ire(x) scanf("%d",&x)
#define iire(a,b) scanf("%d %d",&a,&b)
#define lre(x) scanf("%lld",&x)
#define llre(a,b) scanf("%lld %lld",&a,&b)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define endl "\n"
#define PI acos(-1.0)
//#define int long long
typedef long long ll;
typedef unsigned long long ull;
      
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<ll, ll> PLL;
typedef pair<double, double> PDD;
typedef pair<double, pair<int, double> > PDID;
typedef pair<char, char> PCC;
typedef pair<char, pair<int, int> > PCII;
typedef pair<int, pair<int, int> > PIII;
typedef pair<int, pair<int, pair<int, int> > > PIIII;
typedef pair<ll, pair<int, int> > PLII;

const int maxn = 2e5 + 7;
const int N = 2e6 + 7;
const int M = 4e6 + 7;
const int mod = 998244353;
const int inv = mod - mod/2;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-8;
  
ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
ll lcm(ll a,ll b) {return a*b / gcd(a,b);}
ll qmi(ll a,ll b,ll p) {ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans;}
int lowbit(int x) {return x & (-x);}

ll a[maxn];
ll sum[maxn];
ll n,s;

struct node
{
	int l,r;
	ll v;
}tr[maxn*4];

void pushup(int u)
{
//	tr[u].v = tr[u<<1].v + tr[u<<1|1].v;
	tr[u].v = min(tr[u<<1].v, tr[u<<1|1].v);
}

void build(int u,int l,int r)
{
	tr[u] = {l,r,INF};
	
	if(l == r) 
	{
		tr[u].v = sum[l];
		return;
	}
	
	int mid = l + r >> 1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	
	pushup(u);
}

ll query(int u,int l,int r)
{
	if(l <= tr[u].l && r >= tr[u].r) return tr[u].v;
	
	int mid = tr[u].l + tr[u].r >> 1;
	
	ll ans = INF;
	if(l <= mid) ans = min(ans,query(u<<1, l, r));
	if(r > mid) ans = min(ans,query(u<<1|1, l, r));
	
	return ans;
}

void solve()
{
	cin>>n>>s;
	for(int i=1;i<=n;i++) cin>>a[i], sum[i] = 0;
	for(int i=1;i<=n;i++) sum[i] = sum[i-1] + a[i];
	
	build(1,1,n);	//维护sum区间最小值
	
	ll ans_len = -1;
	ll ans_l,ans_r;
	
	for(int i=1;i<=n;i++)	//枚举左端点
	{
		//二分右端点
		int l = i;
		int r = n;
		while(l < r)
		{
			int mid = l + r + 1 >> 1;
			
			if(query(1,i,mid) + s >= sum[i-1]) l = mid;
			else r = mid - 1;
		}
		
// 		cout<
		
		if(query(1,i,l) + s >= sum[i-1] && l - i + 1 > ans_len)
		{
			ans_len = l-i+1;
			ans_l = i;
			ans_r = l;
		}
	}
	
	if(ans_len == -1) cout<<ans_len<<'\n';
	else cout<<ans_l<<' '<<ans_r<<'\n';
}

int main()
{
	IOS;
	
	int t;
// 	t = 1;
    cin>>t;
// 	ire(t);
	while(t--)
	{
		solve();
	}
	
    return 0;
}

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158