skyaozoraの日記

AOJ2563 The J-th Number

22:28

問題概要

英語だけど短いし問題文を読んで

解法

「区間に対して処理を行う」「区間に関する何かに答える」って地点でもうどう見てもSegtree。適当にやったら状態量O(Nlog^2N)の計算量O(Nlog^3N)になったけど、450MBの7sくらいで何とか通った。

//JAG春コンテスト13I The J-th Number(AOJ2563)
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,lint> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define N 524288
map<int,lint> me[N*2+10];
vector<pint> d1[N*2+10];//n倍してないもの
vector<pint> d2[N*2+10];//下までの合計
int inf=1001001001;
//[a,b)にxを追加する
void add(int a,int b,int x,int k=0,int l=0,int r=N){
	if(r<=a || b<=l) return;
	if(a<=l && r<=b) me[k][x]++;
	else{
		add(a,b,x,k*2+1,l,(l+r)/2);
		add(a,b,x,k*2+2,(l+r)/2,r);
	}
}
vector<pint> merge(vector<pint> a,vector<pint> b){
	int i1=0,i2=0;
	vector<pint> ret;
	while(i1<a.size() || i2<b.size()){
		if(i1<a.size() && i2<b.size() && a[i1].fi==b[i2].fi){
			ret.pb(mp(a[i1].fi,a[i1].se+b[i2].se));i1++;i2++;
		}
		else if(i2>=b.size() || (i1<a.size() && a[i1].fi<b[i2].fi)){
			ret.pb(a[i1]);i1++;
		}
		else{
			ret.pb(b[i2]);i2++;
		}
	}
	return ret;
}
lint siz[N*2+10];
vector<int> v;
//[a,b)にx未満はいくつあるか
lint query(int a,int b,int x,int k=0,int l=0,int r=N){
	if(r<=a || b<=l) return 0;
	if(a<=l && r<=b){
		int id=lower_bound(All(d2[k]),mp(x,-1LL))-d2[k].begin()-1;
		return d2[k][id].se;
	}
	lint vl=query(a,b,x,k*2+1,l,(l+r)/2);
	lint vr=query(a,b,x,k*2+2,(l+r)/2,r);
	lint id=lower_bound(All(d1[k]),mp(x,-1LL))-d1[k].begin()-1;
	return d1[k][id].se*(v[min(b,r)]-v[max(a,l)])+vl+vr;
}
int a[252521],b[252521];lint x[252521];
int main()
{
	int n,m,q;
	cin>>n>>m>>q;
	rep(i,m+q){
		cin>>a[i]>>b[i]>>x[i];a[i]--;
		v.pb(a[i]);v.pb(b[i]);
	}
	sort(All(v));v.erase(unique(All(v)),v.end());
	n=v.size()-1;
	memset(siz,0,sizeof(siz));
	rep(i,n) siz[N-1+i]=v[i+1]-v[i];
	for(int i=N-2;i>=0;i--) siz[i]=siz[i*2+1]+siz[i*2+2];
	rep(i,m+q){
		a[i]=lower_bound(All(v),a[i])-v.begin();
		b[i]=lower_bound(All(v),b[i])-v.begin();
	}
	rep(i,m){
		add(a[i],b[i],(int)x[i]);
	}
	
	rep(i,N*2+5){
		d1[i].pb(mp(-1,0));
		map<int,lint>::iterator it=me[i].begin();
		while(it!=me[i].end()){
			d1[i].pb(mp((*it).fi,(*it).se));it++;
		}
		d1[i].pb(mp(inf,0));
	}
	for(int i=N*2-2;i>=0;i--){
		rep(j,d1[i].size()) d2[i].pb(mp(d1[i][j].fi,d1[i][j].se*siz[i]));
		if(i>N-2) continue;
		d2[i]=merge(d2[i],merge(d2[i*2+1],d2[i*2+2]));
	}
	rep(i,N*2+3){
		rep(j,(int)d1[i].size()-1) d1[i][j+1].se+=d1[i][j].se;
		rep(j,(int)d2[i].size()-1) d2[i][j+1].se+=d2[i][j].se;
	}
	REP(i,m,m+q){
		int lo=0,hi=inf;
		while(hi>lo){
			int mi=(hi+lo+1)/2;
			if(query(a[i],b[i],mi)<(lint)x[i]) lo=mi;else hi=mi-1;
		}
		cout<<lo<<endl;
	}
}

ところで「J-th Number」なのに何でI問題で出たんですかね･･･（このコンテストはちゃんとJ問題もあったし）