D - Data Mining - Gym 100496 D - 오프라인 처리 + 트 리 배열 + 이산 화

http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=193991

//     +      
//    【 1,N】   a        ,           ，     b      

//Gym 100496D         [a,b] ，b                            ，    。
//  【           】                    ,                a，   a     1   ，     a        ，          a  

 ， [a,b]     ，          ！               ，                       ，         ，    ，  ，               

，              ，，                ，              ，    （         ）。。      ...      ，               

  ，         。
   vis             (     10^9,       )       [N]，   【a,b】， b-for  a           ，      【     】       ；        

 ，      ，    【     】	for  ，  [a,b] 【b                 】 b        【     】(   )， 【           】
  get_sum(【b                 】)


#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;
#define inf 0x7f7f7f7f;
const int maxn=100000*2+5;
int n,m;
struct node
{
	int x,num;		//                
} A[maxn];
struct edge
{
	int x,y,num;
} tm[maxn];

int cmp(node a,node b)
{
	return a.x<b.x;			//         ，
}
int posi[maxn];
int vis[maxn];

int max(int a,int b )
{
	if (a<b)return b;return a;
}
int tree[maxn];
inline  int lowbit(int x)
{
	return x&-x;
}
void add(int x,int value)
{
	for (int i=x;i<=n;i=i+lowbit(i))
	{
		tree[i]+=value;
	}
}
int get(int x)
{
	int sum=0;
	for (int i=x;i;i-=lowbit(i))
	{
		sum+=tree[i];
	}
	return sum;
}
int cmp2(edge a,edge b)
{
	if (a.x!=b.x)
		return a.x>b.x;
	else
		return a.y<b.y;
	
}
int ans[maxn];
int main()
{
	freopen( "data.in","r",stdin );  //scanf  1.txt  
	   freopen( "data.out","w",stdout );  //printf   1.tx
	int i,a,b,j;
	
	cin>>n;
	
	for (i=1;i<=n;i++)
	{
		scanf("%d",&A[i].x);
		A[i].num=i; 
	}
	sort(A+1,A+1+n,cmp);				//          
	
	int ok=0;
	for (i=1;i<=n;i++)		//        ，   
	{
		ok++;
		if (A[i].x==A[i-1].x)		//     ，           
		{
			ok--;
			posi[A[i].num]=ok;
		}
		else
			posi[A[i].num]=ok;
	}
	
	
	cin>>m;
	int maxx=0;			 
	for (i=1;i<=m;i++)
	{
		scanf("%d%d",&tm[i].x,&tm[i].y);
		tm[i].y+=tm[i].x-1;		//   【a          b   】   【       a+b-1   】
		tm[i].num=i;			//      
		maxx=max(maxx,tm[i].y);		//       
	}
	sort(tm+1,tm+1+m,cmp2);			//     ，                【1，3】 【2，4】     【2，4】，     【1，3】     ，     ；
	int mark_l=maxx;
	vis[ posi[mark_l]  ]=mark_l;		//         。	
	add(mark_l,1);				
	for (i=1;i<=m;i++)
	{
		a=tm[i].x;
		b=tm[i].y; 
		if (a<mark_l)			//  a>=mark_l                   ，        。
		{
			for (j=mark_l-1;j>=a;j--)		//  【    mark_l a】
			{
				if (vis[ posi[j]  ]==0)		//       
				{
					vis[ posi[j]  ]=j;
					add(j,1);
				}
				else
				{
					int t=vis[ posi[j]  ];
					add(t,-1);
					vis[ posi[j] ]=j;
					add(j,1);
				}
			}
		}
//	cout<<get(vis[posi[b]])<<endl;
		ans[tm[i].num]=get( vis[posi[b]]);
		mark_l=a;  
	}
	
 
		for (i=1;i<=m;i++)
	{
			printf("%d
",ans[i]);
		}

	
	
	
	
	return 0;
	
}