P10083 [GDKOI2024 提高组] 不休陀螺
2026-09-21
题解
考虑一个区间合法的条件。
- 这个区间每轮操作后的费用不降,也就是 ∑i=lr(bi−ai)≥0。
- 显然牌有两种,操作后加费用的和操作后扣费用的,最劣情况是把操作后扣费用的放在前面,后面跟一个 a 很大的加费用牌,令 E′=E−∑i=lrmax(ai−bi,0)。
在加费用时,对于所有满足 ai<bi 的牌,要让 E′≥max[ai<bi]ai。
在扣费用时,要保证每一张放最后面都能扣的起,也就是 E′≥max[ai>bi]bi。
两个合并一下,就是 E′≥maxi=lrmin(ai,bi)。
综上,合法条件为:
⎩⎨⎧i=l∑r(bi−ai)≥0E−i=l∑rmax(ai−bi,0)≥i=lmaxrmin(ai,bi)
观察一下,第一个条件较宽松,直接对 bi−ai 前缀和得到 c,然后判断 cr≥cl−1 即可。
第二个条件考虑枚举一个端点,这里选择 l,当 l 变大时,∑i=lrmax(ai−bi,0) 不增,左边整体不减;右边减少一组,maxi=lrmin(ai,bi) 不增。
整体来看,条件更加宽松,也就是说最大的 r 单调不减,直接进行双指针。
双指针过程中,考虑怎么对于最大的 r,找到 [l,r] 中所有满足第一个条件的位置,也就是查询所有满足 i≤r 且 ci≥cl−1。
可以在 c 上维护一个权值树状数组,每次查询 [cl−1,+∞],由于 c 很大,进行离散化即可,至于 [l,r] 中 min(ai,bi) 最大值,使用单调队列维护即可。
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
typedef long long LL;
#define LOCAL
namespace IO {
#ifndef LOCAL
#define SIZE (1<<20)
char in[SIZE] , *p1=in , *p2=in;
#define getchar() (p1==p2 && (p2=(p1=in)+fread(in,1,SIZE,stdin)) , p1==p2 ? EOF : *p1 ++)
#endif
inline int read() {
int x = 0 , f = 1;
int c = getchar();
while(c < '0' || '9' < c) {
if(c == '-') f = -1;
c = getchar();
}
while('0' <= c && c <= '9') {
x = (x<<3) + (x<<1) + c - '0';
c = getchar();
}
return x*f;
}
inline void write(LL x , bool f = true) {
if(x < 0) x = -x , putchar('-');
static short stk[30] , top; top = 0;
do {stk[++ top] = x%10 , x/=10; } while(x);
while(top) putchar(stk[top --] | '0');
if(f) putchar('\n');
else putchar(' ');
}
#ifndef LOCAL
#undef getchar
#undef SIZE
#endif
} using namespace IO;
const int N = 1e6+10;
inline LL max(LL x , LL y) {
if(x > y) return x;
return y;
}
inline LL min(LL x , LL y) {
if(x < y) return x;
return y;
}
int n , E;
int a[N] , b[N]; LL c[N];
int q[N];
vector<LL> nums;
namespace FW {
int c[N];
inline int lowbit(int x) {
return x & (-x);
}
inline void add(int x , int y) {
while(x <= (int) nums.size()) c[x] += y , x += lowbit(x);
}
inline int query(int x) {
int res = 0;
while(x) res += c[x] , x -= lowbit(x);
return res;
}
} using FW::add; using FW::query;
int main() {
n = read(); E = read();
for(int i = 1 ; i <= n ; i ++) a[i] = read();
for(int i = 1 ; i <= n ; i ++) {
b[i] = read(); c[i] = c[i-1]+b[i]-a[i];
nums.push_back(c[i]);
}
nums.push_back(0); //==
sort(nums.begin() , nums.end());
nums.erase(unique(nums.begin(),nums.end()) , nums.end());
for(int i = 0 ; i <= n ; i ++) {
c[i] = 1+lower_bound(nums.begin() , nums.end() , c[i])-nums.begin();
}
int hh = 0 , tt = -1;
LL sum = E , ans = 0;
for(int l = 1 , r = 0 ; l <= n ; l ++) {
if(r < l - 1) {
r = l - 1; sum = E; hh = 0; tt = -1;
}
if(hh <= tt && q[hh] < l) hh ++;
while(r < n && sum-max(a[r+1]-b[r+1],0)
>= max(hh <= tt ? min(a[q[hh]],b[q[hh]]) : 0 , min(a[r+1],b[r+1]))) {
r ++; sum -= max(a[r]-b[r],0);
add(c[r] , 1);
while(hh <= tt && min(a[q[tt]],b[q[tt]])
<= min(a[r],b[r])) tt --;
q[++ tt] = r;
}
if(l <= r) {
ans += query(nums.size())-query(c[l-1]-1);
add(c[l] , -1); sum += max(a[l]-b[l],0);
}
}
write(ans);
return 0;
}