AOJ 2563: The J-th Number

相当いろんな解法があるらしい。

考えられる一番直感的な方法で解いた。動的確保の二種の和のsegtreeにpairをぶちこんでソートして後半のクエリで二分探索。動的確保で何個ノードが必要になるのかがよくわからない。計算量(特にソート部分)もよくわからない。

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
struct wolf{
	vector<pair<int,int> >A;
	vector<pair<int,long long> >B;
	int left;
	int right;
	wolf(){
		left=right=-1;
	}
};
wolf pool[3500000];
int sz=0;
void add(int a,int b,int c,int d,int e,int f){
	if(d<a||b<c)return ;
	if(c<=a&&b<=d){
		pool[e].A.push_back(make_pair(f,1));
		return;
	}
	//printf("%d: %d %d\n",e,a,b);
	int num=min(b,d)-max(a,c)+1;
	pool[e].B.push_back(make_pair(f,num));
	int to;
	if(min((a+b)/2,d)>=max(a,c)){
		to=pool[e].left;
		if(!~to){
			to=pool[e].left=sz++;
		}
		add(a,(a+b)/2,c,d,to,f);
	}
	if(min(b,d)>=max((a+b)/2+1,c)){
		to=pool[e].right;
		if(!~to){
			to=pool[e].right=sz++;
		}
		add((a+b)/2+1,b,c,d,to,f);
	}
}
long long cnt(int a,int b,int c,int d,int e,int f){
//	printf("%d %d %d %d %d %d\n",a,b,c,d,e,f);
	if(d<a||b<c)return 0LL;
	if(c<=a&&b<=d){
		long long ret=(*(lower_bound(pool[e].B.begin(),pool[e].B.end(),make_pair(f+1,0LL))-1)).second;
		int num=b-a+1;
		ret+=(long long)((*(lower_bound(pool[e].A.begin(),pool[e].A.end(),make_pair(f+1,0))-1)).second)*num;
		return ret;
	}
	int num=min(b,d)-max(a,c)+1;
	long long ret=(long long)((*(lower_bound(pool[e].A.begin(),pool[e].A.end(),make_pair(f+1,0))-1)).second)*num;
	int to=pool[e].left;
	if(~to){
		ret+=cnt(a,(a+b)/2,c,d,to,f);
	}
	to=pool[e].right;
	if(~to){
		ret+=cnt((a+b)/2+1,b,c,d,to,f);
	}
	return ret;
}
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	sz++;
	for(int i=0;i<b;i++){
		int p,q,r;
		scanf("%d%d%d",&p,&q,&r);
		p--;q--;
		add(0,(1<<30)-1,p,q,0,r);
	}
	for(int i=0;i<sz;i++){
	//	printf("%d: %d %d\n",i,pool[i].A.size(),pool[i].B.size());
		pool[i].A.push_back(make_pair(0,0));
		pool[i].B.push_back(make_pair(0,0));
		
		std::sort(pool[i].A.begin(),pool[i].A.end());
		long long now=0;
		for(int j=0;j<pool[i].A.size();j++){
		//	if(j)printf("%d: %d %d\n",i,pool[i].A[j].first,pool[i].A[j].second);
			now+=pool[i].A[j].second;
			pool[i].A[j].second=now;
		}
		std::sort(pool[i].B.begin(),pool[i].B.end());
		now=0;
		for(int j=0;j<pool[i].B.size();j++){
	//		if(j)printf("%d: %d %d\n",i,pool[i].B[j].first,pool[i].B[j].second);
			now+=pool[i].B[j].second;
			pool[i].B[j].second=now;
		}
	}
	for(int i=0;i<c;i++){
		int p,q;
		long long r;
		scanf("%d%d%lld",&p,&q,&r);
		p--;q--;
		int left=0;
		int right=1000000007;
		while(left+1<right){
			int M=(left+right)/2;
			long long val=cnt(0,(1<<30)-1,p,q,0,M);
		//	printf("%lld\n",val);
			if(val>=r)right=M;
			else left=M;
		}
		printf("%d\n",right);
	}
}