AOJ 2674: Disordered Data Detection

実質Typhoon。
いつまでたっても同じようなやるだけ典型が出題され続けるの、問題作成陣の(解く方の)練習不足を感じる……

#include<stdio.h>
#include<algorithm>
using namespace std;
int c[110000];
int z[110000];
int ret[110000];
pair<int,pair<int,int> >ev[210000];
int bit[110000];
int sum(int a,int b){
	if(a)return sum(0,b)-sum(0,a-1);
	int ret=0;
	for(;b>=0;b=(b&(b+1))-1)ret+=bit[b];
	return ret;
}
void add(int a,int b){
	for(;a<110000;a|=a+1)bit[a]+=b;
}
int L[110000];
int R[110000];
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d",c+i);
		z[i]=c[i];
	}
	z[a]=-1000000000;
	z[a+1]=1000000000;
	std::sort(z,z+a+2);
	int b;scanf("%d",&b);
	for(int i=0;i<b;i++){
		int p,q,r;
		scanf("%d%d%d",&p,&q,&r);
		p--;q--;
		ev[i*2]=make_pair(p,make_pair(i,0));
		ev[i*2+1]=make_pair(q+1,make_pair(i,1));
		L[i]=min(c[p],c[q])-r;
		R[i]=max(c[p],c[q])+r;
	}
	std::sort(ev,ev+b*2);
	int now=0;
	for(int i=0;i<b*2;i++){
		int at=ev[i].first;
		int ind=ev[i].second.first;
		int type=ev[i].second.second;
		while(now<at){
			add(lower_bound(z,z+a+2,c[now])-z,1);
			now++;
		}
		if(type){
			ret[ind]+=sum(0,lower_bound(z,z+a+2,L[ind])-z-1);
			ret[ind]+=sum(upper_bound(z,z+a+2,R[ind])-z,a+1);
		}else{
			ret[ind]-=sum(0,lower_bound(z,z+a+2,L[ind])-z-1);
			ret[ind]-=sum(upper_bound(z,z+a+2,R[ind])-z,a+1);
		}
	}
	for(int i=0;i<b;i++)printf("%d\n",ret[i]);
}