#775519 (C++17) No.924 紲星

提出ソース
結果

問題	No.924 紲星
コンテスト
ユーザー	f1b_maxbl00d
提出日時	2022-07-02 06:02:23
言語	C++17 (gcc 13.3.0 + boost 1.89.0)
結果	AC
実行時間	2,752 ms / 4,000 ms
コード長	15,306 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	3,024 ms
コンパイル使用メモリ	180,320 KB
最終ジャッジ日時	2025-01-30 03:47:04
ジャッジサーバーID （参考情報）	judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 16
権限があれば一括ダウンロードができます
ソースコード

raw source code
//#pragma warning(disable:4996)
//#include <Windows.h>
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>
#include <bitset>
//#include <stdio.h>

//< in.txt > out.txt
using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
//typedef boost::multiprecision::cpp_int bigint;
typedef pair<LL, LL> PLL;
typedef pair<int, int> PI;
typedef pair<LD, LL> pdl;
typedef pair<LD, LD> pdd;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef unsigned long long ULL;
template<class T>
using pqueue = priority_queue<T, vector<T>, function<bool(T, T)>>;
string alphabet = "abcdefghijklmnopqrstuvwxyz";

template<class T>
inline void chmin(T& a, T b) {
	a = min(a, b);
}

template<class T>
inline void chmax(T& a, T b) {
	a = max(a, b);
}

//y/xのfloorを求める
LL floor_(LL y, LL x) {
	if (x < 0) {
		x *= -1;
		y *= -1;
	}
	if (y >= 0) {
		return y / x;
	}
	else {
		if ((-y) % x == 0) {
			return y / x;
		}
		else {
			return -((-y) / x) - 1;
		}
	}
}

inline LL mod(LL a, LL m) {
	LL res = a % m;
	return res >= 0 ? res : res + m;
}

void input();
void solve();

void daminput();
void naive();

void outputinput();

int main() {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	cout << fixed << setprecision(12);
	input();
	//daminput();
	solve();
	//naive();
	//outputinput();
	return 0;
}

//////////////////////////////////////////////////
//////////////////////////////////////////////////

template<class T>
class CPSegmentTree {
public:
	CPSegmentTree() {}
	CPSegmentTree(int n, function<T(T, T)> tt, T t0) {
		build(n, tt, t0);
	}
	CPSegmentTree(vector<T>& ar0, function<T(T, T)> tt, T t0) {
		build(ar0, tt, t0);
	}
	void build(int n, function<T(T, T)> tt, T t0)
	{
		TT = tt;
		T0 = t0;
		height = 1;
		//2の累乗化
		int rn = 1;
		while (rn < n)
		{
			rn *= 2;
			height++;
		}
		N = rn;
		ar.resize(2 * N - 1, t0);
		cl.resize(2 * N - 1, -1);
		cr.resize(2 * N - 1, -1);
		time.resize(2 * N - 1, 0);
		for (int n = 0; n < N - 1; n++)
		{
			cl[n] = 2 * n + 1;
			cr[n] = 2 * n + 2;
		}
		roots.push_back(0);
	}
	void build(vector<T>& ar0, function<T(T, T)> tt, T t0)
	{
		TT = tt;
		T0 = t0;
		N = ar0.size();
		int rn = 1;
		while (rn < N)
		{
			rn *= 2;
			height++;
		}
		N = rn;
		cl.resize(2 * N - 1, -1);
		cr.resize(2 * N - 1, -1);
		time.resize(2 * N - 1, 0);
		for (int n = 0; n < N - 1; n++)
		{
			cl[n] = 2 * n + 1;
			cr[n] = 2 * n + 2;
		}
		ar.resize(2 * N - 1, t0);
		for (int n = 0; n < ar0.size(); n++)
		{
			ar[N - 1 + n] = ar0[n];
		}
		for (int n = N - 2; n >= 0; n--)
		{
			ar[n] = TT(ar[cl[n]], ar[cr[n]]);
		}
		roots.push_back(0);
	}
	//時間tの木のコピーを作る この木を表す時間を返す
	//(コピー元の木をこの後いじると壊れる)
	int copy(int t)
	{
		int oldr = roots[t];
		int newt = roots.size();
		roots.push_back(ar.size());
		ar.push_back(ar[oldr]);
		cl.push_back(cl[oldr]);
		cr.push_back(cr[oldr]);
		time.push_back(newt);
		return newt;
	}
	//時間tの頂点nをxに更新
	void set(int t, int n, T x)
	{
		set_node(t, roots[t], 0, N, n, x);
	}
	//時間tの頂点nにxを左からかける
	void addl(int t, int n, T x) {
		T old = get(t, n);
		set(t, n, TT(x, old));
	}
	//時間tの頂点nにxを右からかける
	void addr(int t, int n, T x) {
		T old = get(t, n);
		set(t, n, TT(old, x));
	}
	//時刻tにおける、[l,r)の範囲の積を返す
	T get(int t, int l, int r)
	{
		return get_node(l, r, roots[t], 0, N);
	}
	//時間tにおける、葉nの値
	T get(int t, int n)
	{
		return get(t, n, n + 1);
	}
private:
	template<class U>
	friend class StaticRectangleSum;
	//要素数(2の累乗化済み)
	int N;
	//要素
	vector<T> ar;
	//左右の子は何か
	VI cl, cr;
	//積
	function<T(T, T)> TT;
	//単位元
	T T0;
	//時刻tにおける根のid(はじめの時刻は0)
	VI roots;
	//この木の高さ
	int height;
	//各頂点の属する時間
	VI time;
	//時間tの頂点pに対する更新処理
	//範囲[l,r)を持つ
	//更新処理をした結果の自分の頂点番号を返す(新しく時間tに頂点を登録した場合)
	int set_node(int t, int p, int l, int r, int n, T x)
	{
		//頂点pが時間tの頂点でなければ、新しい頂点を作ったうえで変更
		if (time[p] != t)
		{
			int newp = ar.size();
			ar.push_back(ar[p]);
			cl.push_back(cl[p]);
			cr.push_back(cr[p]);
			time.push_back(t);
			p = newp;
		}
		//この頂点が頂点n自身の場合
		if (l == n && r == n + 1)
		{
			ar[p] = x;
			return p;
		}
		//左の子は[l,m)、右の子は[m,r)を持つ
		int m = (r - l) / 2 + l;
		//頂点nが左の子に含まれる場合
		if (n < m)
		{
			cl[p] = set_node(t, cl[p], l, m, n, x);
		}
		//頂点nが右の子に含まれる場合
		else
		{
			cr[p] = set_node(t, cr[p], m, r, n, x);
		}
		ar[p] = TT(ar[cl[p]], ar[cr[p]]);
		return p;
	}
	//再帰用 n:=見る頂点、頂点nの表す範囲は[s,e)
	T get_node(int l, int r, int n, int s, int e)
	{
		if (l <= s && e <= r)
		{
			return ar[n];
		}
		//左の子は[s,m)、右の子は[m,e)を持つ
		int m = (e - s) / 2 + s;
		T res = T0;
		//左の子が[l,r)とかぶる
		if (r > s && m > l)
		{
			res = get_node(l, r, cl[n], s, m);
		}
		//右の子が[l,r)とかぶる
		if (r > m && e > l)
		{
			res = TT(res, get_node(l, r, cr[n], m, e));
		}
		return res;
	}
	int size() {
		return N;
	}
};

//二次元領域[0,W)×[0,H)のアーベル群重み付き格子点の範囲和、x座標方向のupper/lower boundを求める
//need CPSegmentTree
template<class T>
class StaticRectangleSum {
private:
	int W, H;
	CPSegmentTree<T> seg;
	//Tの演算
	function<T(T, T)> tt;
	//逆元
	function<T(T)> neg;
	//単位元
	T t0;
public:
	StaticRectangleSum() :W(0), H(0) {}
	StaticRectangleSum(int w, int h, vector<tuple<int, int, T>> points, T t0_ = T(0), function<T(T, T)> tt_ = [](T a, T b) {return a + b; }, function<T(T)> neg_ = [](T a) {return -a; }) {
		build(w, h, points, t0_, tt_, neg_);
	}
	//points:(x座標,y座標,重み)の配列 0≦x座標<W、0≦y座標<Hである必要がある
	void build(int w, int h, vector<tuple<int, int, T>> points, T t0_ = T(0), function<T(T, T)> tt_ = [](T a, T b) {return a + b; }, function<T(T)> neg_ = [](T a) {return -a; }) {
		W = w;
		H = h;
		tt = tt_;
		neg = neg_;
		t0 = t0_;
		seg.build(W, tt, t0);
		//upper/lower boundのために、時間tをy座標H-yと同一視
		sort(points.begin(), points.end(), [](tuple<int, int, T>& p1, tuple<int, int, T>& p2) {
			return (std::get<1>(p1) > std::get<1>(p2));
		});
		//今見てる時間t(y=H-t)
		int curt = 0;
		for (tuple<int, int, T>& p : points) {
			int x, y;
			T w;
			tie(x, y, w) = p;
			while (H - curt != y) {
				seg.copy(curt++);
			}
			seg.addl(curt, x, w);
		}
		while (H - curt != 0) {
			seg.copy(curt++);
		}
	}
	//[x=l,r)×[y=b,u)の範囲の重み和を求める
	T get(int l, int r, int b, int u) {
		//y座標[b,u)を時間(u,b]に変換
		b = H - b;
		u = H - u;
		T sum = seg.get(b, l, r);
		sum = tt(sum, neg(seg.get(u, l, r)));
		return sum;
	}
	//[l,e-1)×[d,u)の和 < x <= [l,e)×[d,u)の和となるe(l<=e<=W+1)を求める(単調増加性を仮定)
	//less(a,b) := a<bならばtrue
	int lower_bound(int l, int d, int u, T x, function<bool(T, T)> less = [](T a, T b) {return a < b; }) {
		//y座標を[d,u)から時間(u,d]に変換
		d = H - d;
		u = H - u;
		struct nodebfs {
			//時間u,dにおける見てる頂点
			int nu, nd;
			//頂点nは[a,b)を表す
			int a, b;
		};
		//[l,W)を覆うようなノードの集合
		vector<nodebfs> nodes;
		queue<nodebfs> nodebfsq;
		int RN = seg.size();
		nodebfsq.push({ seg.roots[u],seg.roots[d],0,RN });
		while (!nodebfsq.empty()) {
			int nu = nodebfsq.front().nu;
			int nd = nodebfsq.front().nd;
			int a = nodebfsq.front().a;
			int b = nodebfsq.front().b;
			nodebfsq.pop();
			if (W <= a || b <= l) {
				continue;
			}
			if (l <= a && b <= W) {
				nodes.push_back({ nu,nd,a,b });
			}
			else {
				nodebfsq.push({ seg.cl[nu],seg.cl[nd],a,(a + b) / 2 });
				nodebfsq.push({ seg.cr[nu],seg.cr[nd],(a + b) / 2,b });
			}
		}
		//nodes[0,nn]の和 < x <= nodes[0,nn + 1]の和
		int nn = -1;
		//nodes[0,nn]の和
		T sum = t0;
		while (nn + 1 < nodes.size()) {
			T next = tt(seg.ar[nodes[nn + 1].nd], neg(seg.ar[nodes[nn + 1].nu]));
			next = tt(sum, next);
			//nodes[0,nn+1]の和 >= xのとき
			if (!less(next, x)) {
				break;
			}
			else {
				nn++;
				sum = next;
			}
		}
		//全部とっても<x
		if (nn == nodes.size() - 1 && less(sum, x)) {
			return W;
		}
		nn++;
		//nodes[nn]をバラす
		//[l,r) < x
		int r = l;
		if (nn - 1 >= 0) {
			r = nodes[nn - 1].b;
		}
		nodebfs cur = nodes[nn];
		int a = nodes[nn].a;
		int b = nodes[nn].b;
		while (b - a > 1) {
			//左の子の和
			int chl_d = seg.cl[cur.nd];
			int chl_u = seg.cl[cur.nu];
			T suml = tt(seg.ar[chl_d], neg(seg.ar[chl_u]));
			if (!less(tt(sum, suml), x)) {
				b = (a + b) / 2;
				cur = { chl_u,chl_d,a,b };
			}
			else {
				sum = tt(sum, suml);
				int chr_d = seg.cr[cur.nd];
				int chr_u = seg.cr[cur.nu];
				r = (a + b) / 2;
				a = (a + b) / 2;
				cur = { chr_u,chr_d,a,b };
			}
		}
		return r + 1;
	}
	//[l,e-1)×[d,u)の和 <= x < [l,e)×[d,u)の和となるe(l<=e<=W+1)を求める(単調増加性を仮定)
	//less(a,b) := a<bならばtrue
	int upper_bound(int l, int d, int u, T x, function<bool(T, T)> less = [](T a, T b) {return a < b; }) {
		//y座標を[d,u)から時間(u,d]に変換
		d = H - d;
		u = H - u;
		struct nodebfs {
			//時間u,dにおける見てる頂点
			int nu, nd;
			//頂点nは[a,b)を表す
			int a, b;
		};
		//[l,W)を覆うようなノードの集合
		vector<nodebfs> nodes;
		queue<nodebfs> nodebfsq;
		int RN = seg.size();
		nodebfsq.push({ seg.roots[u],seg.roots[d],0,RN });
		while (!nodebfsq.empty()) {
			int nu = nodebfsq.front().nu;
			int nd = nodebfsq.front().nd;
			int a = nodebfsq.front().a;
			int b = nodebfsq.front().b;
			nodebfsq.pop();
			if (W <= a || b <= l) {
				continue;
			}
			if (l <= a && b <= W) {
				nodes.push_back({ nu,nd,a,b });
			}
			else {
				nodebfsq.push({ seg.cl[nu],seg.cl[nd],a,(a + b) / 2 });
				nodebfsq.push({ seg.cr[nu],seg.cr[nd],(a + b) / 2,b });
			}
		}
		//nodes[0,nn]の和 <= x < nodes[0,nn + 1]の和
		int nn = -1;
		//nodes[0,nn]の和
		T sum = t0;
		while (nn + 1 < nodes.size()) {
			T next = tt(seg.ar[nodes[nn + 1].nd], neg(seg.ar[nodes[nn + 1].nu]));
			next = tt(sum, next);
			//nodes[0,nn+1]の和 > xのとき
			if (less(x, next)) {
				break;
			}
			else {
				nn++;
				sum = next;
			}
		}
		//全部とっても<=x
		if (nn == nodes.size() - 1 && !less(x, sum)) {
			return W;
		}
		nn++;
		//nodes[nn]をバラす
		//[l,r) <= x
		int r = l;
		if (nn - 1 >= 0) {
			r = nodes[nn - 1].b;
		}
		nodebfs cur = nodes[nn];
		int a = nodes[nn].a;
		int b = nodes[nn].b;
		while (b - a > 1) {
			//左の子の和
			int chl_d = seg.cl[cur.nd];
			int chl_u = seg.cl[cur.nu];
			T suml = tt(seg.ar[chl_d], neg(seg.ar[chl_u]));
			if (less(x, tt(sum, suml))) {
				b = (a + b) / 2;
				cur = { chl_u,chl_d,a,b };
			}
			else {
				sum = tt(sum, suml);
				int chr_d = seg.cr[cur.nd];
				int chr_u = seg.cr[cur.nu];
				r = (a + b) / 2;
				a = (a + b) / 2;
				cur = { chr_u,chr_d,a,b };
			}
		}
		return r + 1;
	}
};

//各項が0以上M未満の静的整数列のRange Kth SmallestやRange Countを求める
//(x座標が要素、y座標は添え字)
class CPSegSequence {
private:
	StaticRectangleSum<LL> rec;
	int N;
	int M;
public:
	CPSegSequence() {};
	CPSegSequence(int m, VLL& seq) {
		build(m, seq);
	}
	void build(int m, VLL& seq) {
		M = m;
		N = seq.size();
		vector<tuple<int, int, LL>> points;
		points.reserve(N);
		for (int n = 0; n < N; n++) {
			points.emplace_back(seq[n], n, 1);
		}
		rec.build(M, N, points);
	}
	//A[l]からA[r-1]のうち、s以上e未満の要素の数を求める
	int get(int l, int r, int s, int e) {
		return rec.get(max(s, 0), min(e, M), l, r);
	}
	//A[l]からA[r-1]のうち、[d,u-1)の要素の数 < x <= [d,u)の要素の数なるuを求める
	int lower_bound(int l, int r, int d, int x) {
		return rec.lower_bound(d, l, r, x);
	}
	//A[l]からA[r-1]のうち、[d,u-1)の要素の数 <= x < [d,u)の要素の数なるuを求める
	int upper_bound(int l, int r, int d, int x) {
		return rec.upper_bound(d, l, r, x);
	}
	//A[l]からA[r-1]のうち、k番目(1-indexed)に小さい数を求める
	int kthnumber(int l, int r, int k) {
		return rec.lower_bound(0, l, r, k) - 1;
	}
};

//座圧
class CoordComp
{
public:
	int N;
	VI new2old;
	map<LL, int> old2new;
	CoordComp() :N(0) {};
	CoordComp(VLL& v) {
		build(v);
	}
	//vに含まれる数に昇順で添え字(0-index)を設定する(vは変更しない)
	void build(VLL& v)
	{
		set<LL> all;
		for (LL t : v)
		{
			all.insert(t);
		}
		N = all.size();
		new2old.reserve(N);
		int i = 0;
		for (LL t : all)
		{
			old2new.insert(pair<LL, int>(t, i++));
			new2old.push_back(t);
		}
	}
	//tを圧縮した座標を返す
	LL conv(int t)
	{
		return old2new[t];
	}
	//[l,r)が含む登録点の集合を変換後の座標の区間[s,e)で返す(登録点が存在しなければ[-1,-1)を返す)
	PI conv(LL l, LL r)
	{
		int s = lower_bound(l);
		int e = lower_bound(r);
		return PI(s, e);
	}
	//revconv(e-1) <= x < revconv(e)なるeを返す
	int upper_bound(LL x) {
		int s = -1, e = N;
		while (e - s > 1) {
			int m = (e + s) / 2;
			if (new2old[m] <= x) {
				s = m;
			}
			else {
				e = m;
			}
		}
		return e;
	}
	//revconv(e-1) < x <= revconv(e)なるeを返す
	int lower_bound(LL x) {
		int s = -1, e = N;
		while (e - s > 1) {
			int m = (e + s) / 2;
			if (new2old[m] < x) {
				s = m;
			}
			else {
				e = m;
			}
		}
		return e;
	}
	//圧縮済みの座標から、元の数を返す
	LL revconv(int i)
	{
		return new2old[i];
	}
	//登録点の個数
	int size()
	{
		return N;
	}
};

int N, Q;
VLL A;

void input() {
	cin >> N >> Q;
	A.resize(N);
	for (int n = 0; n < N; n++) {
		cin >> A[n];
	}
}

void daminput() {
}

void solve() {
	CoordComp coord(A);
	VLL ord(N);
	for (int n = 0; n < N; n++) {
		ord[n] = coord.conv(A[n]);
	}
	CPSegSequence seq(coord.size(),ord);
	vector<tuple<int, int, LL>> points;
	points.reserve(N);
	for (int n = 0; n < N; n++) {
		points.emplace_back(ord[n], n, A[n]);
	}
	StaticRectangleSum<LL> recsum(coord.size(), N, points);
	for (int q = 0; q < Q; q++) {
		int l, r;
		cin >> l >> r;
		l--; r--;
		int d = (r - l) / 2 + 1;
		LL x = seq.kthnumber(l, r + 1, d);
		int c = seq.get(l, r + 1, 0, x + 1);
		LL sum = coord.revconv(x) * c - recsum.get(0, x + 1, l, r + 1);
		sum += recsum.get(x + 1, coord.size(), l, r + 1) - coord.revconv(x) * (r - l + 1 - c);
		cout << sum << "\n";
	}
}

void naive() {
}

void outputinput() {
}
yukicoder

結果

ソースコード
