Rikka with sequence

Time Limit: 1 Sec Memory Limit: 256 MB

题目连接

http://acm.hdu.edu.cn/showproblem.php?pid=5204

Description

众所周知，萌萌哒六花不擅长数学，所以勇太给了她一些数学问题做练习，其中有一道是这样的：
现在有一个序列，因为这个序列很任性，开始时空的。接下来发生了n个事件，每一个事件是以下两种之一：
1.勇太利用黑炎龙的力量在序列的开头、结尾以及每相邻两个元素之间都插入一个权值为w的元素。若第一步执行事件一，执行后数列仅有一个数字w.
2.勇太想要六花告诉他第L个元素到第R个中权值第k小的权值是多少。
当然，这个问题对于萌萌哒六花来说实在是太难了，你可以帮帮她吗？

Input

第一行一个正整数n。接下来n行每一行描述了一种操作：
1.如果输入格式是1 w，表示第一种事件。
2.如果输入格式是2 L R k，表示第二种事件。
1≤n≤105，1≤L≤R≤1018，1≤w≤109，保证L，R，k合法, R不会超过当前序列长度。

Output

对于每一个第二类事件，输出一个数字表示答案。

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

HINT

题意

题解：

每一次加入数的时候，都会加入在奇数位置，我们每次/2之后，就相当于在回到了上一个状态

然后搞呀搞就好啦

正如题解所讲：大水题（雾

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 200001

#define mod 10007

#define eps 1e-9

//const int inf=0x7fffffff;   //无限大

const int inf=0x3f3f3f3f;

/*

int buf[10];

inline void write(int i) {

  int p = 0;if(i == 0) p++;

  else while(i) {buf[p++] = i % 10;i /= 10;}

  for(int j = p-1; j >=0; j--) putchar('0' + buf[j]);

  printf("\n");

}

*/

//**************************************************************************************

inline ll read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

struct node

{

    ll x,num;

};

bool cmp(node a,node b)

{

    return a.x<b.x;

}

ll a[maxn];

node b[maxn];

int main()

{

    int n=read(),tot=;

    for(int i=;i<n;i++)

    {

        int t=read();

        if(t==)

            a[++tot]=read();

        else

        {

            ll l,r,org;

            scanf("%lld%lld%lld",&l,&r,&org);

            int num=;

            for(int i=tot;i>=;i--)

            {

                b[++num].x=a[i];

                b[num].num=(r+)/-l/;

                r/=;

                l=(l+)/;

                if(r<l)

                    break;

            }

            sort(b+,b+num+,cmp);

            for(int i=;i<=num;i++)

            {

                org-=b[i].num;

                if(org<=)

                {

                    printf("%lld\n",b[i].x);

                    break;

                }

            }

        }

    }

}

秒客网

hdu 5204 Rikka with sequence 智商不够系列