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/point_add_range_sum.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#include "head.hpp"
#include "data_structure/1D-fenwick.hpp"
#include "io/Scanner.hpp"
#include "io/Printer.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 op, l, r;
            scanner.scan(op, l, r);
            if(op == 0)
                    fenwick.add(++l, r);
            else
                    printer.print(fenwick.Rangesum(++l, r)), printer.putchar('\n');
    }
}
#line 1 "test/library_checker/point_add_range_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_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.hpp"

class Scanner
{
public:
	Scanner(std::FILE *f = stdin, std::size_t enough_buffer_size = 1 << 25)
		: f_(f), buffer_(new char[enough_buffer_size + 32]), buffer_head_(buffer_),
		  buffer_tail_(buffer_ + std::fread(buffer_, sizeof(char), enough_buffer_size + 32, f_)) {*buffer_tail_ = '\0';}
	~Scanner() {delete[] buffer_;}
	
	template<typename T>
	std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char> && std::is_signed_v<T>, bool>
	scan(T &x)
	{
		x = 0;
		while(*buffer_head_ != '-' && std::isspace(*buffer_head_))
			++buffer_head_;
		bool is_neg = *buffer_head_ == '-' && ++buffer_head_;
		char *old_buffer_head = buffer_head_;
		if(is_neg)
			while(std::isdigit(*buffer_head_)) x = x * 10 - (*buffer_head_++ - '0');
		else
			while(std::isdigit(*buffer_head_)) x = x * 10 + (*buffer_head_++ - '0');
		return buffer_head_ != old_buffer_head;
	}  

	template<typename... T>
	bool scan(T &...x)
	{
		return (... && scan(x));
	}

private:
	std::FILE *f_;
	char *buffer_, *buffer_head_, *buffer_tail_;
};
#line 2 "io/Printer.hpp"

class Printer
{
public:
	Printer(std::FILE *f = stdout, std::size_t buffer_size = 100000)
		: f_(f), buffer_(new char[buffer_size + 32]), buffer_head_(buffer_),
		  buffer_end_(buffer_ + buffer_size + 32), stk_(new char[32]), top_(stk_) {}
	~Printer()
	{
		flush();
		delete[] stk_;
		delete[] buffer_;
	}

	void flush()
	{
		std::fwrite(buffer_, buffer_head_ - buffer_, sizeof(char), f_);
		buffer_head_ = buffer_;
	}

	void putchar(char x)
	{
		if(buffer_end_ == buffer_head_)
			flush();
		*buffer_head_++ = x;
	}

	template<typename T>
	std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char> && std::is_signed_v<T>, void>
	print(T x)
	{
		if(x == 0)
			return this->putchar('0');
		if(x < 0)
		{
			putchar('-');
			do
			{
				T y = x / 10;
				*top_++ = y * 10 - x + '0';
				x = y;
			} while(x != 0);
		}
		else
		{
			do
			{
				T y = x / 10;
				*top_++ = x - y * 10 + '0';
				x = y;
			} while(x != 0);
		}
		if(buffer_end_ - buffer_head_ < top_ - stk_)
			flush();
		while(top_ != stk_) *buffer_head_++ = *--top_;
	}

	void print(char x) {return this->putchar(x);}

	template<typename T>
	std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char> && std::is_unsigned_v<T>, void>
	print(T x)
	{
		if(x == 0)
			return this->putchar('0');
		do
		{
			T y = x / 10;
			*top_++ = x - y * 10 + '0';
			x = y;
		} while(x != 0);
		if(buffer_end_ - buffer_head_ < top_ - stk_)
			flush();
		while(top_ != stk_) *buffer_head_++ = *--top_;
	}

	template<typename... T>
	void print(T... x)
	{
		return (..., print(x));
	}

	template<typename T>
	void println(T x)
	{
		return this->print(x), this->putchar('\n');
	}

private:
	std::FILE *f_;
	char *buffer_, *buffer_head_, *buffer_end_, *stk_, *top_;
};
#line 6 "test/library_checker/point_add_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 op, l, r;
            scanner.scan(op, l, r);
            if(op == 0)
                    fenwick.add(++l, r);
            else
                    printer.print(fenwick.Rangesum(++l, r)), printer.putchar('\n');
    }
}
Back to top page