2 Dオフセット入門

1次元sort;
多次元cdq学はできない.
では、二次元を勉強しましょう.
2 Dバイアス:2 Dバイアスは、座標軸の点(x,y)と見なすことができます.これは、xが何個あるかを検索し、yがその点より小さいことです.
通常は1 Dをソートし、別の1 Dツリー配列を更新してメンテナンスします.
例題1:http://poj.org/problem?id=2352
POJ 2352
Stars
标题:N個の座標をあげて、それぞれの座標の等級(等級の意味はXで、Yはすべて現在の(X,Y)の座標の個数より小さい);
問題解:入力されたサンプルは、デフォルトがXでインクリメントされてからYでインクリメントされたもの、すなわちデフォルトがYで優先されてソートされているので、Yより小さい座標の集合の中でXより小さいものがすべて見つかっていると見なすことができます.列挙Y(実際にはなく、相当)、ツリー配列メンテナンスX、挿入X、クエリー接頭辞和.

#include
#include
#include
#include
#include
#include
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1000000;
struct node{
	int x,y;
}s[maxn];
int c[maxn],n;
int lowbit(int x){
  return x&-x; }
void add(int id,int p){
	while(id<=32005){
		c[id]+=p;
		id+=lowbit(id);
	}
}
int sum(int id){
	int ans=0;
	while(id>=1){
		ans+=c[id];
		id-=lowbit(id);
	}
	return ans;
}
int ans[maxn];
int main(){
	//cin>>n; 
	while(~scanf("%d",&n)){
	for(int i=1;i<=n;i++){
	//	cin>>s[i].x>>s[i].y;
    	scanf("%d%d",&s[i].x,&s[i].y);
		c[i]=0;
		ans[i]=0;
	}
    for(int i=1;i<=n;i++){
    	int x=s[i].x;
    	x++;//          0，              1  
    	ans[sum(x)]++;
    	add(x,1);
	}
	for(int i=0;i

例題2:https://ac.nowcoder.com/acm/contest/16/A Laptop
题意:N対数、対数ごとにすべてコンピュータのメモリの価格とハードディスクのスピードを代表して、あなたにいくつのコンピュータのこのデータがすべていくつかのコンピュータより小さいことを闻きます
题解:この属性は座標と見なして、あなたに何個の座標のXを要して、Yはすべていくつかの座標のXより小さくて、Y;
           次に、Xソート、ツリー配列メンテナンスY、XバックメンテナンスY、クエリー接尾辞和、つまり最大のXから順に対応するYを挿入することで、現在のIのXより大きいこれらの座標のうちどれだけのYが現在のIのYより小さいかを知ることができ、現在のIより大きいすべてのXの座標でクエリーの数を減算します!=0は、確かに座標のあるX,Yはいずれも現在のIのX,Yより大きいことを示す.

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1e5+5;
struct node{
	int x,y;
}s[maxn];
int c[maxn],n;
int lowbit(int x){
  return x&-x; 
}
void add(int id,int p){
	while(id<=n){
		c[id]+=p;
		id+=lowbit(id);
	}
}
int sum(int id){
	int ans=0;
	while(id>=1){
		ans+=c[id];
		id-=lowbit(id);
	}
	return ans;
}
bool cmp(node a,node b){
	return a.xv;
int getid(int x){
	return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
int main(){
    scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&s[i].x,&s[i].y);
		v.push_back(s[i].y);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	sort(s+1,s+1+n,cmp);
	int ans=0;
	for(int i=n;i>=1;i--){
		int k=getid(s[i].y);
		cout<