前缀和有很好的性质

但是…

long long! long long! long long!

天呐…我好像写了整整10天…其实主要是被期中考试×了

然后我期中考试还是炸了 数学73你敢信?

懵逼的 题目

LL

扯淡的 题解

day1的题感觉大部分的参赛选手都能想到算法啊..根本没有什么技术含量啊

——某联赛的毒瘤出题人

不过这题的思维难度确实没有NOIpD1T1大www

真 没什么用的思路

Part1
Part2
Part3
Part4
Part5

到底 为什么$fr[]$没有可减性

qwq

就上面这幅图说一下…

如果我要添加浅蓝色的这一小段

于是我加上了lefr[ri], 减去了lefr[le - 1]

然后我发现, 在$[le, ri]$之间, 最小值a[wz]所占的横杆(橘色)超过了le, 一直到了leqwq[wz] + 1才结束, 以$1$为左端点的子集们的最小值才不是a[wz](黑色的横杆)

这样一来, 其实我们减去的lefr[le - 1](粉色), 和我们应该减去的a[wz] * (le - 1 - leqwq[wz]) + lefr[leqwq[wz]], 就不一样了…所以是错的

假 没什么用的实现方法

  • 我需要一个数组lefr[MAXN]: lefr[i]存储的是$1 \to i$中所有以$i$为右端点的子集的最小值的和
    • 我需要一个数组leqwq[MAXN]: leqwq[i]存储了: 在$i$的左边, 比a[i]小的数中最靠右的(也就是最接近$i$的), 数的位置(注意: a[leqwq[x]] < a[x], 注意区间元素个数, 且如果没有找到比当前数小的数, leqwq[i] = 0)
      • 我需要一个单调栈(要手写, 在init()函数中修改, 查询):
        • 开两个栈first[], second[]: first代表数值, second代表位置
        • 从头到尾加数, 传入两个参数(大小, 位置), 并进行如下操作:
          • 查询: 二分一个比当前数小的数, 并返回这个数的位置即可
          • 修改: 如果新进的数比栈顶小(或等于), 弹栈(两个栈一同弹出); 直到新进的数比栈顶大为止(也就是这个栈是从下至上单调递增的)
    • 这样就可以预处理lefr[]了(这个预处理和莫队的add()基本上是一模一样的):
      • lefr[i] = a[i] * (i - leqwq[i]) + lefr[leqwq[i]]
  • 我需要一个数组rifr[MAXN]: rifr[i]存储的是$i \to n$中所有以$i$为左端点的子集的最小值的和
    • 我需要一个数组riqwq[MAXN]: riqwq[i]存储了: 在$i$的右边, 比a[i]小的数中最靠右的(也就是最接近$i$的), 数的位置(注意: 如果没有找到比当前数小的数, riqwq[i] = n + 1)
      • 单调栈同上即可(写一个结构体就行), 但加数要反着来
    • 这样我们就可以预处理rifr[]了:
      • rifr[i] = a[i] * (riqwq[i] - i) + rifr[riqwq[i]]
  • 我需要一个solve()函数来进行莫队操作(注意: 不可以再使用诸如add(ri++)等写法了…因为在add(int)中, 全局变量ri已经改变了)
  • 我需要一个函数cx(int le, int ri)返回$[le, ri]$中的最小值的位置
    • ST表乱搞就好啦
    • 我需要一个函数LL lecal(): 他能够计算在前缀和运算中在左边应该减去多少
    • wz为当前区间内的最小值的位置, xleqwq[wz]
      • return a[wz] * (le - 1 - x) + lefr[x];
  • 我需要一个函数LL rical(): 他能够计算在前缀和运算中在右边应该减去多少
    • wz为当前区间内的最小值的位置, xriqwq[wz]
      • return a[wz] * (x - ri - 1) + rifr[x];
  • 我需要一个函数leadd(int x): 向当前的区间内加入一个数a[x](--le)
    • 如果riqwq[x] > ri也就是因当前添加的数而增加的所有子集的最小值都为a[x]: 那么直接ans += a[x] * (ri - le + 1)即可
    • 否则, 有一部分的区间的最小值并非a[x]:
      • ans += rifr[ri];
      • ans -= rical();
  • 我需要一个函数riadd(int x): 向当前的区间内的右边加入一个数a[x](++ri)
    • 如果leqwq[x] < le也就是因当前添加的数而增加的所有子集的最小值都为a[x]: 那么直接ans += a[x] * (ri - le + 1)即可
    • 否则, 有一部分的区间的最小值并非a[x]:
      • ans += lefr[x];
      • ans -= lecal();
  • 我需要一个函数ledel(int x): 从当前的区间内的左边删除一个数a[x](le++)
    • 删除嘛…就是增加的反操作啊…
    • 如果riqwq[x] > ri: ans -= (ri - le + 1) * a[x]
    • 否则:
      • ans -= riqwq[x];
      • ans += rical();
  • 我需要一个函数ridel(int x): 从当前的区间内的右边删除一个数a[x](ri--)
    • 如果leqwq[x] < le: ans -= (ri - le + 1) * a[x]
    • 否则:
      • ans -= leqwq[x];
      • ans += lecal();

Maya…我怎么感觉…这个题比tree难搞多~~~了…

真 简单明了的 代码

跳过的 坑

  • ST表: le + (t << 1) - 1 <= n 以及 le + (1 << t) <= n…直接给我$RE$成零分了…
  • 没有把a[]开成LL, 这样在预处理进行乘法的时候就已经炸了…
/**************************************************************
    Problem: 4540
    User: Cansult
    Language: C++
    Result: Accepted
    Time:9876 ms
    Memory:18424 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <cmath>
#define MAXN (100000 + 5)
#define INF (0x7fffffff)
#define MAXL (20 + 5)
#define pii pair<int, int>
#define LL long long
using namespace std;
struct question
{
    int le, ri, bh;
}que[MAXN];
struct dds
{
    int first[MAXN], second[MAXN], re0;
    dds(int x): re0(x) { first[0] = second[0] = 1, first[1] = -INF, second[1] = x; }
    int cx(int dqfr, int dqsec)
    {
        if (!first[0])
        {
            first[++first[0]] = dqfr, second[++second[0]] = dqsec;
            return re0;
        }
        int re = upper_bound(first + 1, first + first[0] + 1, dqfr) - first - 1;
        if (!re)    re = re0;
        else    re = second[re];
        while (first[0] && first[first[0]] >= dqfr)
            --first[0], --second[0];
        first[++first[0]] = dqfr, second[++second[0]] = dqsec;
        return re;
    }
};
struct ST
{
    int f[MAXN][MAXL], n, lgn;
    LL a[MAXN];
    int lg(int x)
    {
        int re = 0;
        while ((1 << re) < x)
            ++re;
        return re;
    }
    void init(int xn, LL *xa)
    {
        memset(a, 0x8f, sizeof(a));
        n = xn, lgn = lg(n);
        for (int i = 1; i <= n; i++)
            f[i][0] = i, a[i] = xa[i];
        for (int t = 1; t <= lgn; t++)
            for (int i = 1; i <= n; i++)
                if (i + (1 << t) - 1 <= n)
                {
                    if (a[f[i][t - 1]] < a[f[i + (1 << (t - 1))][t - 1]])
                        f[i][t] = f[i][t - 1];
                    else
                        f[i][t] = f[i + (1 << (t - 1))][t - 1];
                }
    }
    int cx(int le, int ri)
    {
        int lglr = lg(ri - le + 1), lex = f[le][lglr - 1], rix = f[ri - (1 << (lglr - 1)) + 1][lglr - 1];
        if (a[lex] < a[rix])
            return lex;
        else
            return rix;
    }
};
ST QAQ;
int n, q, leqwq[MAXN], riqwq[MAXN], le, ri, block;
LL lefr[MAXN], rifr[MAXN], ans, outans[MAXN], a[MAXN];
void init()
{
    dds led(0), rid(n + 1);
    QAQ.init(n, a);
// leqwq && riqwq:
    for (int i = 1; i <= n; i++)
        leqwq[i] = led.cx(a[i], i);
    for (int i = n; i >= 1; i--)
        riqwq[i] = rid.cx(a[i], i);
// lefr && rifr:
    for (int i = 1; i <= n; i++)
        lefr[i] = a[i] * (i - leqwq[i]) + lefr[leqwq[i]];
    for (int i = n; i >= 1; i--)
        rifr[i] = a[i] * (riqwq[i] - i) + rifr[riqwq[i]];
}
/*inline LL lecal(int x)
{
    LL re = a[x] * (x - leqwq[x] - 1) + lefr[leqwq[x]];
    return re;
}
inline LL rical(int x)
{
    LL re = a[x] * (riqwq[x] - x - 1) + rifr[riqwq[x]];
    return re;
}*/
inline LL lecal()
{
    int wz = QAQ.cx(le, ri), x = leqwq[wz];
    LL re = a[wz] * (le - 1 - x) + lefr[x];
    return re;
}
inline LL rical()
{
    int wz = QAQ.cx(le, ri), x = riqwq[wz];
    LL re = a[wz] * (x - ri - 1) + rifr[x];
    return re;
}
void leadd(int x)
{
    if (riqwq[x] > ri)
        ans += a[x] * (ri - le + 1);
    else
    {
        ans += rifr[x];
        ans -= rical();
    }
}
void riadd(int x)
{
    if (leqwq[x] < le)
        ans += a[x] * (ri - le + 1);
    else
    {
        ans += lefr[x];
        ans -= lecal();
    }
}
void ledel(int x)
{
    if (riqwq[x] > ri)
        ans -= a[x] * (ri - le + 1);
    else
    {
        ans -= rifr[x];
        ans += rical();
    }
}
void ridel(int x)
{
    if (leqwq[x] < le)
        ans -= a[x] * (ri - le + 1);
    else
    {
        ans -= lefr[x];
        ans += lecal();
    }
}
bool cmp(const question x, const question y)
{
    if (x.le / block == y.le / block)
        return x.ri < y.ri;
    else
        return x.le < y.le;
}
void solve()
{
    sort(que + 1, que + q + 1, cmp);
    ri = le = que[1].le;
    for (int i = le; i <= que[1].ri; i++)
        riadd(ri), ++ri;
    --ri;
    outans[que[1].bh] = ans;
    for (int i = 2; i <= q; i++)
    {
        while (le < que[i].le)
            ledel(le), ++le;
        while (le > que[i].le)
            leadd(--le);
        if (le > ri)
            ri = le - 1, ans = 0;
        while (ri < que[i].ri)
            riadd(++ri);
        while (ri > que[i].ri)
            ridel(ri), --ri;
        outans[que[i].bh] = ans;
    }
}
int main()
{
    scanf("%d%d", &n, &q);
    block = sqrt(n) + 1;
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for (int i = 1; i <= q; i++)
        scanf("%d%d", &que[i].le, &que[i].ri), que[i].bh = i;
    init();
    /*for (int i = 1; i <= n; i++)
        printf("%d ", leqwq[i]);
    puts("");
    for (int i = 1; i <= n; i++)
        printf("%d ", riqwq[i]);
    puts("\n---------------");
    for (int i = 1; i <= n; i++)
        printf("%d ", lefr[i]);
    puts("");
    for (int i = 1; i <= n; i++)
        printf("%d ", rifr[i]);
    puts("");*/
    solve();
    for (int i = 1; i <= q; i++)
        printf("%lld\n", outans[i]);
    return 0;
}

/*
5 5
5 2 4 1 3
1 5
1 3
2 4
3 5
2 5
*/

听说还有线段树做法?

被吓尿了 改天去参拜一下

By … Cansult