Submission #979083

---

Source Code Expand

#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<vector>
#include<array>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<cassert>
#include<functional>
#include<random>
#include<complex>
#include<bitset>
#include<chrono>
//#include<boost/multiprecision/cpp_int.hpp>
#define int int64_t
#define uint uint64_t
#define REP(i, a, b) for (int64_t i = (int64_t)(a); i < (int64_t)(b); i++)
#define rep(i, a) REP(i, 0, a)
#define EACH(i, a) for (auto i: a)
#define ITR(x, a) for (auto x = a.begin(); x != a.end(); x++)
#define ALL(a) (a.begin()), (a.end())
#define HAS(a, x) (a.find(x) != a.end())
#define Min(x) *min_element(ALL(x))
#define Max(x) *max_element(ALL(x))
#define Unique(L) (L.erase(unique(ALL(L)), L.end()))
#define veccat(v1, v2) std::copy((v2).begin(),(v2).end(),std::back_inserter(v1)/*v1の後ろにv2を入れる*/)
#define intmax (std::numeric_limits<int64_t>::max() / 4)
using namespace std;
//typedef boost::multiprecision::cpp_int bigint;
const double EPS = 1e-9;
const double PI = acos(-1.0);

class segtree_add_sum_lazy {
private:
	typedef int T;
public:
	segtree_add_sum_lazy(const int N) {
		SIZE = roundup_pow2(N);
		all.clear();
		all.resize(SIZE * 2, 0);
		part.clear();
		part.resize(SIZE * 2, 0);
	}

	//配列要素の[index]にnumberを加算する。
	void update(const int index, const T number) {
		update(index, index + 1, number);
	}

	//配列要素の[L,R)全てにnumberを加算する。
	void update(const int L, const int R, const T number) {
		update_inner(L, R, 1, 0, SIZE, number);
	}

	//[L,R)の総和を返す。
	T getsum(const int L, const int R) {
		return getsum_inner(L, R, 1, 0, SIZE);
	}
private:
	void update_inner(const int queryL, const int queryR, const int index, const int segL, const int segR, const T number) {
		if (queryL <= segL && segR <= queryR)all[index] += number;
		else if (queryL < segR && segL < queryR) {
			part[index] += number * (min(queryR, segR) - max(queryL, segL));
			update_inner(queryL, queryR, index * 2, segL, (segL + segR) / 2, number);
			update_inner(queryL, queryR, index * 2 + 1, (segL + segR) / 2, segR, number);
		}
	}

	T getsum_inner(const int queryL, const int queryR, const int index, const int segL, const int segR) {
		if (queryR <= segL || segR <= queryL)return 0;
		if (queryL <= segL && segR <= queryR)return all[index] * (segR - segL) + part[index];
		T result = all[index] * (min(queryR, segR) - max(queryL, segL));
		result += getsum_inner(queryL, queryR, index * 2, segL, (segL + segR) / 2);
		result += getsum_inner(queryL, queryR, index * 2 + 1, (segL + segR) / 2, segR);
		return result;
	}

	//x以上であるような2のべき乗数のうち最小のものを返す。
	int roundup_pow2(int x) {
		x--;
		rep(i, 6)x |= x >> (1LL << i);
		return x + 1;
	}

	int SIZE;
	vector<T>all;
	vector<T>part;
};

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	vector<int>P(N);

	rep(i, N)cin >> P[i];

	segtree_add_sum_lazy A(N), B(N);

	rep(i, N)A.update(i, i + 1);
	rep(i, N)B.update(i, N - i);

	rep(i, N) {
		int index = P[i] - 1;
		A.update(index, N, i + 1);
		B.update(0, index + 1, i + 1);
	}

	rep(i, N) {
		if (i)cout << " ";
		cout << A.getsum(i, i + 1);
	}
	cout << endl;
	rep(i, N) {
		if (i)cout << " ";
		cout << B.getsum(i, i + 1);
	}
	cout << endl;
	return 0;
}

Submission Info

Judge Result