#1065498 (C++23) No.3094 Stapler

提出ソース
結果

問題	No.3094 Stapler
ユーザー	Today03
提出日時	2025-04-07 02:32:00
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	105 ms / 2,000 ms
コード長	8,467 bytes
コンパイル時間	3,741 ms
コンパイル使用メモリ	285,136 KB
実行使用メモリ	35,312 KB
最終ジャッジ日時	2025-06-20 02:33:28
合計ジャッジ時間	10,422 ms
ジャッジサーバーID （参考情報）	judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 72
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include<bits/stdc++.h>
#define ALL(x) (x).begin(),(x).end()
#define LB(v,x) (int)(lower_bound(ALL(v),x)-(v).begin())
#define UQ(v) sort(ALL(v)),(v).erase(unique(ALL(v)),(v).end())
#define IO ios::sync_with_stdio(false),cin.tie(nullptr);
#define chmax(a,b)(a)=(a)<(b)?(b):(a)
#define chmin(a,b)(a)=(a)<(b)?(a):(b)
using namespace std;
using ll=long long;
const int INF=1e9+10;
const ll INFL=4e18;



/// @brief 遅延評価セグメント木
/// @tparam Monoid モノイド
/// @tparam Operator 作用素
/// @tparam mapping （モノイドの元，作用素の元）→モノイドの元を返す関数
template<typename Monoid,typename Operator,auto mapping>
struct SegTreeLazy{
	using MonoidType=typename Monoid::Type;
	using OperatorType=typename Operator::Type;
	SegTreeLazy()=default;

	/// @brief 要素数 n の遅延セグ木を構築する
	SegTreeLazy(int n){
		this->n=n;
		dat.assign(n<<1,Monoid::id());
		lazy.assign(n<<1,Operator::id());
	}

	/// @brief 配列 v から遅延セグ木を構築する
	SegTreeLazy(const vector<MonoidType>&v){
		this->n=v.size();
		dat.assign(n<<1,Monoid::id());
		lazy.assign(n<<1,Operator::id());
		for(int i=0;i<n;i++)dat[i+n]=v[i];
		for(int i=n-1;i>0;i--)dat[i]=Monoid::op(dat[i<<1],dat[i<<1|1]);
	}

	/// @brief i 番目の要素を x に更新する
	void set(int i,MonoidType x){
		generate_indices(i,i+1);
		pushdown();
		i+=n;
		dat[i]=x;
		while(i>>=1)dat[i]=Monoid::op(dat[i<<1],dat[i<<1|1]);
	}

	/// @brief 区間 [l, r) に x を作用させる
	void apply(int l,int r,OperatorType x){
		if(l==r)return;
		generate_indices(l,r);
		pushdown();
		l+=n,r+=n;
		while(l<r){
			if(l&1){
				lazy[l]=Operator::op(lazy[l],x);
				dat[l]=mapping(dat[l],x);
				l++;
			}
			if(r&1){
				r--;
				lazy[r]=Operator::op(lazy[r],x);
				dat[r]=mapping(dat[r],x);
			}
			l>>=1,r>>=1;
		}
		pushup();
	}

	/// @brief 区間 [l, r) のモノイド積を返す
	MonoidType fold(int l,int r){
		if(l==r)return Monoid::id();
		generate_indices(l,r);
		pushdown();
		MonoidType retl=Monoid::id(),retr=Monoid::id();
		l+=n,r+=n;
		while(l<r){
			if(l&1)retl=Monoid::op(retl,dat[l++]);
			if(r&1)retr=Monoid::op(dat[--r],retr);
			l>>=1,r>>=1;
		}
		return Monoid::op(retl,retr);
	}

	template<typename F>
	int find_right(int l,F f){
		assert(f(Monoid::id()));
		if(l==n)return n;
		generate_indices(l,n);
		pushdown();
		l+=n;
		int r=n+n;
		vector<int> cand_l,cand_r;
		while(l<r){
			if(l&1)cand_l.push_back(l++);
			if(r&1)cand_r.push_back(--r);
			l>>=1,r>>=1;
		}
		vector<int>cand=cand_l;
		reverse(cand_r.begin(),cand_r.end());
		cand.insert(cand.end(),cand_r.begin(),cand_r.end());
		MonoidType val=Monoid::id();
		for(int i:cand){
			if(f(Monoid::op(val,dat[i]))){
				val=Monoid::op(val,dat[i]);
			}else{
				while(i<n){
					propagate(i);
					i<<=1;
					if(f(Monoid::op(val,dat[i]))){
						val=Monoid::op(val,dat[i]);
						i|=1;
					}
				}
				return i-n;
			}
		}
		return n;
	}
	template<typename F>
	int find_left(int r,F f){
		assert(f(Monoid::id()));
		if(r==0)return 0;
		generate_indices(0,r);
		pushdown();
		r+=n;
		int l=n;
		vector<int> cand_l,cand_r;
		while(l<r){
			if(l&1)cand_l.push_back(l++);
			if(r&1)cand_r.push_back(--r);
			l>>=1,r>>=1;
		}
		vector<int>cand=cand_r;
		reverse(cand_l.begin(),cand_l.end());
		cand.insert(cand.end(),cand_l.begin(),cand_l.end());
		MonoidType val=Monoid::id();
		for(int i:cand){
			if(f(Monoid::op(dat[i],val))){
				val=Monoid::op(dat[i],val);
			}else{
				while(i<n){
					propagate(i);
					i=(i<<1)|1;
					if(f(Monoid::op(dat[i],val))){
						val=Monoid::op(dat[i],val);
						i^=1;
					}
				}
				return i-n+1;
			}
		}
		return 0;
	}

	int size(){return n;}
	MonoidType operator[](int i){return fold(i,i+1);}

private:
	int n;
	vector<MonoidType>dat;
	vector<OperatorType>lazy;
	vector<int>indices;
	void generate_indices(int l,int r){
		indices.clear();
		l+=n,r+=n;
		int lm=(l/(l&-l))>>1,rm=(r/(r&-r))>>1;
		while(l<r){
			if(l<=lm)indices.push_back(l);
			if(r<=rm)indices.push_back(r);
			l>>=1,r>>=1;
		}
		while(l){
			indices.push_back(l);
			l>>=1;
		}
	}
	void propagate(int i){
		if(i<n){
			lazy[i<<1]=Operator::op(lazy[i<<1],lazy[i]);
			lazy[i<<1|1]=Operator::op(lazy[i<<1|1],lazy[i]);
			dat[i<<1]=mapping(dat[i<<1],lazy[i]);
			dat[i<<1|1]=mapping(dat[i<<1|1],lazy[i]);
		}
		lazy[i]=Operator::id();
	}
	void pushdown(){
		for(int j=(int)indices.size()-1;j>=0;j--){
			int i=indices[j];
			propagate(i);
		}
	}
	void pushup(){
		for(int j=0;j<(int)indices.size();j++){
			int i=indices[j];
			dat[i]=Monoid::op(dat[i<<1],dat[i<<1|1]);
		}
	}
};


/// @file monoid.hpp
/// @brief モノイド
namespace Monoid{
	/// @brief Min モノイド
	/// @tparam max_value 単位元
	template<typename T,T max_value=INF>
	struct Min{
		using Type=T;
		static Type id(){return max_value;}
		static Type op(const Type&a,const Type&b){return min(a,b);}
	};

	/// @brief Max モノイド
	/// @tparam min_value 単位元
	template<typename T,T min_value=-INF>
	struct Max{
		using Type=T;
		static Type id(){return min_value;}
		static Type op(const Type&a,const Type&b){return max(a,b);}
	};

	/// @brief 和
	template<typename T>
	struct Sum{
		using Type=T;
		static Type id(){return 0;}
		static Type op(const Type&a,const Type&b){return a+b;}
	};

	/// @brief （和，区間の長さ）
	template<typename T>
	struct SumPair{
		using Type=pair<T,int>;
		static Type id(){return make_pair(T(0),0);}
		static Type op(const Type&a,const Type&b){return{a.first+b.first,a.second+b.second};}
	};
}


namespace Operator{
	template<typename T,T not_exist>
	struct Update{
		using Type=T;
		static Type id(){return not_exist;}
		static Type op(const Type&a,const Type&b){return b==id()?a:b;}
	};

	template<typename T>
	struct Add{
		using Type=T;
		static Type id(){return 0;}
		static Type op(const Type&a,const Type&b){return a+b;}
	};

	template<typename T>
	struct UpdateTimeStamp{
		using Type=pair<T,int>;
		static Type id(){return {0,-1};}
		static Type op(const Type&a,const Type&b){return b.second>a.second?b:a;}
	};
}


namespace RangeQuery{
	template<typename T,T max_value,T not_exist>
	struct Update_GetMin{
		static T mapping(const T&a,const T&b){return b==not_exist?a:b;}
		using Type=struct SegTreeLazy<Monoid::Min<T,max_value>,Operator::Update<T,not_exist>,mapping>;
	};

	template<typename T,T min_value,T not_exist>
	struct Update_GetMax{
		static T mapping(const T&a,const T&b){return b==not_exist?a:b;}
		using Type=struct SegTreeLazy<Monoid::Max<T,min_value>,Operator::Update<T,not_exist>,mapping>;
	};

	template<typename T,T not_exist>
	struct Update_GetSum{
		using S=typename Monoid::SumPair<T>::Type;
		static S mapping(const S&a,const T&b){return b==not_exist?a:S{b*a.second,a.second};}
		using Type=struct SegTreeLazy<Monoid::SumPair<T>,Operator::Update<T,not_exist>,mapping>;
	};

	template<typename T,T max_value>
	struct Add_GetMin{
		static T mapping(const T&a,const T&b){return a+b;}
		using Type=struct SegTreeLazy<Monoid::Min<T,max_value>,Operator::Add<T>,mapping>;
	};

	template<typename T,T min_value>
	struct Add_GetMax{
		static T mapping(const T&a,const T&b){return a+b;}
		using Type=struct SegTreeLazy<Monoid::Max<T,min_value>,Operator::Add<T>,mapping>;
	};

	template<typename T>
	struct Add_GetSum{
		using S=typename Monoid::SumPair<T>::Type;
		static S mapping(const S&a,const T&b){return{a.first+b*a.second,a.second};}
		using Type=struct SegTreeLazy<Monoid::SumPair<T>,Operator::Add<T>,mapping>;
	};
}


struct Info{
	int minval,mincnt;
	Info(int x=0,int y=1){minval=x,mincnt=y;}
};

struct Mono{
	using Type=Info;
	static Type op(Type l,Type r){
		if(l.minval==r.minval){
			return Info(l.minval,l.mincnt+r.mincnt);
		}else if(l.minval<r.minval){
			return l;
		}else{
			return r;
		}
	}
	static Type id(){
		return {INF,0};
	}
};

struct Ope{
	using Type=int;
	static Type op(int l,int r){
		return l+r;
	}
	static Type id(){
		return 0;
	}
};

Info mapping(Info x,int f){
	x.minval+=f;
	return x;
}

int main(){
	IO;
	int N;cin>>N;
	vector<Info>init(N,Info());
	SegTreeLazy<Mono,Ope,mapping>seg(init);


	int Q;cin>>Q;
	vector<pair<int,int>>query(Q);

	for(int q=0;q<Q;q++){
		int t;cin>>t;

		if(t==1){
			int l,r;cin>>l>>r;
			l--,r--;

			query[q]={l,r};
			seg.apply(l,r,1);
		}

		else if(t==2){
			int p;cin>>p,p--;

			auto[l,r]=query[p];
			seg.apply(l,r,-1);
		}

		else{
			Info res=seg.fold(0,N);

			int ans=res.mincnt;
			if(res.minval!=0)ans=0;

			cout<<ans<<'\n';
		}
	}
}
yukicoder

結果

ソースコード
