cp-lib

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Dusker233/cp-lib

:heavy_check_mark: test/library_checker/static_range_sum.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"
#include "head.hpp"
#include "data_structure/1D-fenwick.hpp"
#include "io/Scanner_local.hpp"
#include "io/Printer_local.hpp"
#include "debug.hpp"

using i64 = long long;
constexpr int mmax = 5E5 + 10;

Scanner scanner;
Printer printer;
Fenwick<i64> fenwick(mmax);

int main()
{
    i64 n, q;
    scanner.scan(n, q);
    
    for(int i = 1;i <= n;i++)
    {
            i64 x;
            scanner.scan(x);
            fenwick.add(i, x);
    }
    for(int i = 1;i <= q;i++)
    {
            i64 l, r;
            scanner.scan(l, r);
            printer.println(fenwick.Rangesum(++l, r));
    }
    debug(fenwick.Rangesum(1, n));
}
#line 1 "test/library_checker/static_range_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"
#line 1 "head.hpp"
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define ioclear std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);
#define endl '\n'
#define CLOCK 1e3 * clock() / CLOCKS_PER_SEC


#line 2 "data_structure/1D-fenwick.hpp"

template<typename T>
struct Fenwick
{
	const int n;
	std::vector<T> a;

	Fenwick(int _n) : n(_n), a(_n) {}

	void add(int x, T v)
	{
		for(int i = x;i <= n;i += i & -i)
			a[i] += v;
		return;
	}

	T sum(int x)
	{
		T Ans = 0;
		for(int i = x;i;i -= i & -i)
			Ans += a[i];
		return Ans;
	}

	T Rangesum(int l, int r) {return sum(r) - sum(l - 1);} // [l, r]
};
#line 2 "io/Scanner_local.hpp"

struct Scanner
{
	template<typename T>
	void scan(T &x)
	{
		std::cin >> x;
	}

	template<typename... T>
	void scan(T& ...x)
	{
		((std::cin >> x), ...);
	}
};
#line 2 "io/Printer_local.hpp"

struct Printer
{
	template<typename T>
	void print(T x)
	{
		std::cout << x;
	}

	void putchar(char x)
	{
		putchar(x);
	}

	template<typename T>
	void println(T x)
	{
		std::cout << x << endl;
	}
};
#line 2 "debug.hpp"

#line 4 "debug.hpp"
#include <type_traits>
#line 8 "debug.hpp"

namespace dbg {
    // arithmetic
    template <class T, std::enable_if_t<std::is_arithmetic_v<T>, int> = 0>
    void print(const T &x) {std::cerr << std::boolalpha << x;}

    // string
    void print(const std::string &x) {std::cerr << '\"' << x << '\"';}

    // bitset
    template <std::size_t N> void print(const std::bitset<N> &Bs) {std::cerr << Bs;}

    // pair
    template <class T, class U> void print(const std::pair<T, U> &p) {
        std::cerr << "(";
        print(p.first);
        std::cerr << ", ";
        print(p.second);
        std::cerr << ")";
    }

    // tuple
    template <class... Args> void print(const std::tuple<Args...> &t) {
        std::cerr << "(";
        std::apply([](auto &&... args) {((print(args), std::cerr << ", "), ...);}, t);
        std::cerr << ")";
    }

    // Iterable
    template <typename T, typename = std::void_t<>>
    struct is_iterable : public std::false_type {};

    template <typename T>
    struct is_iterable<T, std::void_t<decltype(std::declval<T>().begin(),
            std::declval<T>().end())>>
            : public std::true_type {};

    template <typename T>
    using is_iterable_t = typename is_iterable<T>::type;

    template <typename T>
    inline constexpr bool is_iterable_v = is_iterable<T>::value;

    template <class T, std::enable_if_t<dbg::is_iterable_v<T>, int> = 0>
    void print(const T &v) {
        int f = 0;
        std::cerr << '{';
        for (const auto &i : v) std::cerr << (f++ ? ", " : ""), print(i);
        std::cerr << "}";
    }

// Debug Mode
    void debug_out() { std::cerr << endl; }
    template <typename Head, typename... Tail>
    void debug_out(Head H, Tail... T) {
        std::cerr << " ", print(H), debug_out(T...);
    }
#define debug(...)                                                             \
  std::cerr << __func__ << ":" << __LINE__ << " [" << #__VA_ARGS__             \
            << "] =",                                                          \
      debug_out(__VA_ARGS__)
};

using namespace dbg;
//
//} // namespace dbg

/**
 * Based on submission('https://codeforces.com/contest/1787/submission/191105890')
 * ANSI Escape Sequences: https://gist.github.com/fnky/458719343aabd01cfb17a3a4f7296797
 */
#line 7 "test/library_checker/static_range_sum.test.cpp"

using i64 = long long;
constexpr int mmax = 5E5 + 10;

Scanner scanner;
Printer printer;
Fenwick<i64> fenwick(mmax);

int main()
{
    i64 n, q;
    scanner.scan(n, q);
    
    for(int i = 1;i <= n;i++)
    {
            i64 x;
            scanner.scan(x);
            fenwick.add(i, x);
    }
    for(int i = 1;i <= q;i++)
    {
            i64 l, r;
            scanner.scan(l, r);
            printer.println(fenwick.Rangesum(++l, r));
    }
    debug(fenwick.Rangesum(1, n));
}
Back to top page