hdu 5204 Rika with sequence y問題

リンク:http://acm.hdu.edu.cn/showproblem.php?pid=5204
Rikca with sequence
Time Limit：2000/1000 MS（Java/Others）    メモリLimit：65536/65536 K（Java/Others）Total Submission（s）：757    Acceepted Submission(s)：136
Problem Description
As we know，Rika is poor at math.Yuta is worying about this situation，so he gives Rikca some math task to practice.The is one of them:
Yuta have a sequence.Because the sequence is very self-willed，at first the sequence is emppty.And the n Yuta don operation on on this sequence，each operation is is eigh of these types:
1.Add a number w into each gap of the sequence.For example if w=3 and the sequence before is「2 4」、it will be changed to「3 3 4」.
**after the first operation of the first type、there is only one number in the sequence*
2.Query the kth small number in the subsequence[L，R].For example if k=2，L=2，R=4 and the sequence is“3 3 3 4 2”，the answer will be 3.
Yuta wants Rikca to tell him the answer of each query.
It is too difficult for Rikca.Can you help her？
 
Input
The first line contains one number 
n(n≦100000).Each of the follwing 
n line s describes an operation：if it is“1 w”it will be the first type.Otherwise if it is“2 L R k”，it will be the second type. 
（1≦w≦109、L≦R≦1018）
R will not be larger than the length of the sequence
 
Output
For each query operation，output one number–the answer.
 
Sample Input

   
   
   
   

    
    
    
    6
1 3
1 1
2 2 3 2
1 2
2 3 5 2
2 1 4 4
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    3
2
3
   
   
   
   
   
   
   
   


   
   
   
   

件名:
n個の操作
最初の空のシーケンス
op==1  一つの数をあげます。シーケンスが空なら、この数を追加します。シーケンスが空ではない場合は、セットの一番前にこの数を追加し、その後のすべての数字の後にこの数字を追加します。
op==2  問い合わせ区間はk番目に大きいです。
作り方:
法則があります 1からLまでの区間について。前の1操作で発生した数が現れます。 （L＋1）／2回、その後、前の（L−（L＋1）／2＋1）／2次類推が現れる。
毎回半分になるので、最大60個の数が出ます。
まず1から（L-1）の区間に出る数-1を、 その後、1からRまでの区間に出現する数を +1、この60個の数を並べ替えて、k番目まで数えたらいいです。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <malloc.h>
#include <ctype.h>
#include <math.h>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#include <stack>
#include <queue>
#include <vector>
#include <deque>
#include <set>
#include <map> 


typedef __int64 ll; 

 
ll op[100100];
ll num[100100];

ll bit[70];

void deal(ll wei,ll x)
{
	ll ji=1;//   
	while(wei)
	{
		bit[ji]+=x*(wei+1)/2; 
		wei-=(wei+1)/2;
		ji++;
	}
}

struct point 
{
	ll num,bit;
};
point tnum[70];

ll cmp(point a,point b)
{
	return a.num<b.num;
}

int main()
{
	ll n;
	scanf("%I64d",&n);
	ll len=1;
	for(ll i=1;i<=n;i++)
	{
		scanf("%I64d",&op[i]);

		if(op[i]&1)
		{
			scanf("%I64d",&num[len++]);
		}
		else
		{
			ll l,r,kk;

			scanf("%I64d%I64d%I64d",&l,&r,&kk);


			memset(bit,0,sizeof bit);
			deal(r,1);
			deal(l-1,-1);

			for(ll i=1;i<=65;i++)//      sum[len-i];
			{
				tnum[i].bit=bit[i];
				tnum[i].num=num[len-i];
			}

			sort(tnum+1,tnum+1+65,cmp);

			for(ll i=1;i<=65;i++)
			{
				kk-=tnum[i].bit;
				if(kk<=0)
				{
					printf("%I64d
",tnum[i].num);
					break;
				}
			}
		}

	}
	return 0;
}