$FarmerJohnSolves3SUM$

题目描述

$FarmerJohn$ 相信他在算法设计上实现了一个重大突破：他声称他发现了一个 $3SUM$ 问题的近似线性时间算法，这是一个有名的算法问题，尚未发现比运行速度比平方时间明显更优的解法。$3SUM$ 问题的一个形式是：给定一个整数数组 $s_1,\dots ,s_m$，计算不同索引组成的无序三元对 $i,j,k$ 的数量，使得 $s_i+s_j+s_k=0$

为了测试 $FarmerJohn$ 的断言，$Bessie$ 提供了一个 $N$ 个整数组成的数组 $A$（$1\le N\le 5000$）。$Bessie$ 还会进行 $Q$ 次询问（$1\le Q\le 10^5$），每个询问由两个索引 $1\le a_i\le b_i\le N$ 组成。对于每个询问，$FarmerJohn$ 必须在子数组 $A[a_i\dots b_i]$ 上求解 $3SUM$ 问题。

不幸的是，$FarmerJohn$ 刚刚发现了他的算法中的一个错误。他很自信他能修复这个算法，但同时，他请你帮他先通过 $Bessie$ 的测试！

输入格式

输入的第一行包含两个空格分隔的整数 $N$ 和 $Q$。

第二行包含空格分隔的数组 $A$ 的元素 $A_1,\dots ,A_N$ 。

以下 $Q$ 行每行包含两个空格分隔的整数 $a_i$ 和 $b_i$ ，表示一个询问。

保证对于每个数组元素 $A_i$ 有 $-10^6\le A_i\le 10^6$ 。

输出格式

输出包含 $Q$ 行，第 $i$ 行包含一个整数，为第 $i$ 个询问的结果。注意你需要使用 $64$ 位整数型来避免溢出。

输入输出样例

输入 #1

7 3
2 0 -1 1 -2 3 3
1 5
2 4
1 7

输出 #1

2
1
4

说明/提示

样例解释

对于第一个询问，所有的三元对为 $(A_1,A_2,A_5)$ 和 $(A_2,A_3,A_4)$ 。

题目大意

有一个长度为 $N$ 的序列 $a_1,a_2,\dots ,a_n$ 。

$Q$ 次询问，每次给定 $l$ 和 $r$ ，问有多少三元组 $(i,j,k)$ 满足 $l\le i<j<k\le r$ 且 $a_i+a_j+a_k=0$ 。

数据范围 ： $1\le N\le 5000,-10^6\le a_i\le 10^6,1\le Q\le 10^5$ 。

解题思路

首先对于所有可能的 $i,k$ ($1\le i<k\le N$) ， 计算有多少 $j$ 满足 $i<j<k$ 且 $a_j=-a_i-a_k$，记作 $f_{i,k}$ 。

查找的过程可以用桶来实现，但要记得每次找完一个区间 $[i,k]$ 内的 $j$ 时，记得把桶清空。

需要注意的是 $a_i$ 可能为负数，所以对每一个要在桶操作的数，都得加上一个足够大的数，保证数组的下标不能是负数。

对于一组询问 $l,r$ ，答案即为 $\sum _{i=l}^r\sum _{k=i}^r{f}_{i,k}$ ， 可用二维前缀、后缀和计算。

时间复杂度：

• 预处理 ： $O(N^2)$
• 查询 ： $O(1)$

$ACcode$

阅读时请省略快读 —— QAQ

#include <bits/stdc++.h>
#define int long long
#define _ 1000000
using namespace std;

/* --------------- fast io --------------- */ // begin
namespace Fread
{
    const int SIZE = 1 << 21;
    char buf[SIZE], *S, *T;
    inline char getchar()
    {
        if (S == T)
        {
            T = (S = buf) + fread(buf, 1, SIZE, stdin);
            if (S == T)
                return 'n';
        }
        return *S++;
    }
} // namespace Fread
namespace Fwrite
{
    const int SIZE = 1 << 21;
    char buf[SIZE], *S = buf, *T = buf + SIZE;
    inline void flush()
    {
        fwrite(buf, 1, S - buf, stdout);
        S = buf;
    }
    inline void putchar(char c)
    {
        *S++ = c;
        if (S == T)
            flush();
    }
    struct NTR
    {
        ~NTR() { flush(); }
    } ztr;
} // namespace Fwrite
#ifdef ONLINE_JUDGE
#define getchar Fread ::getchar
#define putchar Fwrite ::putchar
#endif
namespace Fastio
{

    struct Reader
    {
        template <typename T>
        Reader &operator>>(T &x)
        {
            char c = getchar();
            T f = 1;
            while (c < '0' || c > '9')
            {
                if (c == '-')
                    f = -1;
                c = getchar();
            }
            x = 0;
            while (c >= '0' && c <= '9')
            {
                x = x * 10 + (c - '0');
                c = getchar();
            }
            x *= f;
            return *this;
        }

        Reader &operator>>(char &c)
        {
            c = getchar();
            while (c == ' ' || c == 'n')
            {
                c = getchar();
            }
            return *this;
        }
        Reader &operator>>(char *str)
        {
            int len = 0;
            char c = getchar();
            while (c == ' ' || c == 'n')
            {
                c = getchar();
            }
            while (c != ' ' && c != 'n' && c != 'r')
            { // rn in windows
                str[len++] = c;
                c = getchar();
            }
            str[len] = '';
            return *this;
        }
        Reader() {}
    } cin;
    const char endl = 'n';
    struct Writer
    {

        template <typename T>
        Writer &operator<<(T x)
        {
            if (x == 0)
            {
                putchar('0');
                return *this;
            }
            if (x < 0)
            {
                putchar('-');
                x = -x;
            }
            static int sta[45];
            int top = 0;
            while (x)
            {
                sta[++top] = x % 10;
                x /= 10;
            }
            while (top)
            {
                putchar(sta[top] + '0');
                --top;
            }
            return *this;
        }
        Writer &operator<<(char c)
        {
            putchar(c);
            return *this;
        }
        Writer &operator<<(char *str)
        {
            int cur = 0;
            while (str[cur])
                putchar(str[cur++]);
            return *this;
        }
        Writer &operator<<(const char *str)
        {
            int cur = 0;
            while (str[cur])
                putchar(str[cur++]);
            return *this;
        }
        Writer() {}
    } cout;
} // namespace Fastio
#define cin Fastio ::cin
#define cout Fastio ::cout
#define endl Fastio ::endl

/* --------------- fast io --------------- */ // end

int n, q;
int a, b;

int c[5005];
int f[5005][5005];
int d[4000005];

int col(int x)
{
    return x + (_ << 1);
}

signed main()
{
    cin >> n >> q;

    for (register int i = 1; i <= n; ++i)
    {
        cin >> c[i];
    }

    for (register int i = 1; i <= n; ++i)
    {
        for (register int j = i + 1; j <= n; ++j)
        {
            f[i][j] = d[col(-c[i] - c[j])];
            d[col(c[j])]++;
        }
        for (register int j = i + 1; j <= n; ++j)
        {
            d[col(c[j])] = 0;
        }
    }

    for (register int len = 3; len <= n; ++len)
    {
        for (register int i = 1; i + len - 1 <= n; ++i)
        {
            int j = i + len - 1;
            f[i][j] += f[i + 1][j] + f[i][j - 1] - f[i + 1][j - 1];
        }
    }

    while (q--)
    {
        cin >> a >> b;
        cout << f[a][b] << endl;
    }

    return 0;
}

最后

以上就是平淡鸡为你收集整理的Farmer John Solves 3SUM F a r m e r   J 的全部内容，希望文章能够帮你解决Farmer John Solves 3SUM F a r m e r   J 所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。