[Luogu]P5459 [BJOI2016]回转寿司
本文最后更新于 94 天前,其中的信息可能已经有所发展或是发生改变。

一道有趣的题目。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。
原文链接:https://www.codein.icu/lp5459/

题意

问有多少个连续子序列满足和不低于 $L$ 不大于 $R$,元素可能为负数。

解法

容易想到固定一端点,统计合法的另一端点。
列个式子:$L \le sum[r] – sum[l-1] \le R$
$\implies sum[l-1] + L \le sum[r]$
$\implies sum[l-1] + R \ge sum[r]$
$\implies sum[l-1] + L \le sum[r] \le sum[l-1] + R$
倒叙枚举左端点,询问合法右端点即可。

代码

离散化树状数组。其实还可以转偏序用分治做。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
using namespace std;
#define DEBUG
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 3e5 + 100;
int n, L, R, a[maxn], b[maxn], cnt;
long long sum[maxn], H[maxn];
inline int lowbit(int x){return x & -x;}
void add(int x,int k)
{
    for (; x <= cnt; x += lowbit(x)) b[x] += k;
}
int ask(int x)
{
    int res = 0;
    for (; x > 0; x -= lowbit(x)) res += b[x];
    return res;
}
int main()
{
    read(n), read(L), read(R);
    for (int i = 1; i <= n; ++i) read(a[i]), sum[i] = sum[i - 1] + a[i];
    for (int i = 1; i <= n; ++i) H[++cnt] = sum[i];
    for (int i = 1; i <= n; ++i) H[++cnt] = L + sum[i - 1] - 1, H[++cnt] = R + sum[i - 1];
    sort(H + 1, H + 1 + cnt), cnt = unique(H + 1, H + 1 + cnt) - H - 1;
    long long res = 0;
    for (int l = n; l; --l)
    {
        add(lower_bound(H + 1, H + 1 + cnt, sum[l]) - H, 1);
        res += ask(lower_bound(H + 1, H + 1 + cnt, sum[l - 1] + R) - H) - ask(lower_bound(H + 1, H + 1 + cnt, sum[l - 1] + L - 1) - H);
    }
    printf("%lld\n",res);
    return 0;
}
本文标题:[Luogu]P5459 [BJOI2016]回转寿司
本文作者:Clouder
本文链接: https://www.codein.icu/lp5459/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇