[hdu5204]水题
2024-10-09 02:30:08
思路：插入的数按指数级增长，所以范围内最多存在logR个数。并且最近i次插入的数，首位置为2^(i-1)，且每隔2^i出现一次，于是暴力之。。可以用插入排序维护，也可查询时再排下序。
一：
#pragma comment(linker, "/STACK:10240000,10240000") #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <map>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <ctime>
#include <cctype>
#include <set>
#include <bitset>
#include <functional>
#include <numeric>
#include <stdexcept>
#include <utility> using namespace std; #define mem0(a) memset(a, 0, sizeof(a))
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define define_m int m = (l + r) >> 1
#define rep0(a, b) for (int a = 0; a < (b); a++)
#define rep1(a, b) for (int a = 1; a <= (b); a++)
#define all(a) (a).begin(), (a).end()
#define lowbit(x) ((x) & (-(x)))
#define constructInt4(name, a, b, c, d) name(int a = 0, int b = 0, int c = 0, int d = 0): a(a), b(b), c(c), d(d) {}
#define constructInt3(name, a, b, c) name(int a = 0, int b = 0, int c = 0): a(a), b(b), c(c) {}
#define constructInt2(name, a, b) name(int a = 0, int b = 0): a(a), b(b) {}
#define pchr(a) putchar(a)
#define pstr(a) printf("%s", a)
#define sint(a) ReadInt(a)
#define sint2(a, b) ReadInt(a);ReadInt(b)
#define sint3(a, b, c) ReadInt(a);ReadInt(b);ReadInt(c)
#define pint(a) WriteInt(a) typedef double db;
typedef long long LL;
typedef pair<int, int> pii;
typedef multiset<int> msi;
typedef set<int> si;
typedef vector<int> vi;
typedef map<int, int> mii; const int dx[] = {, , , -, , , -, -};
const int dy[] = {, , -, , -, , , -};
const int maxn = 1e3 + ;
const int maxm = 1e5 + ;
const int maxv = 1e7 + ;
const int max_val = 1e6 + ;
const int MD = 1e9 +;
const int INF = 1e9 + ;
const double PI = acos(-1.0);
const double eps = 1e-; template<class T>T gcd(T a, T b){return b==?a:gcd(b,a%b);}
template<class T>void ReadInt(T &x){char c=getchar();while(!isdigit(c))c=getchar();x=;while(isdigit(c)){x=x*+c-'';c=getchar();}}
template<class T>void WriteInt(T i) {int p=;static int b[];if(i == ) b[p++] = ;else while(i){b[p++]=i%;i/=;}for(int j=p-;j>=;j--)pchr(''+b[j]);} struct abc {
pii a[];
int l, r;
void Init() { l = r = ; }
void push_back(int x) {
a[r++] = make_pair(x, );
for(int i = l; i < r - ; i++) a[i].second++;
if (r - l >= ) {
int pos;
for (int i = l; i < r; i++) {
if (a[i].second == ) {
pos = i;
break;
}
}
for (int i = pos; i > l; i--) a[i] = a[i - ];
l++;
}
int p = r - ;
while (p > l && a[p].first < a[p - ].first) {
swap(a[p], a[p - ]);
p--;
}
}
pii &operator [] (int i) {
return a[l + i];
}
int size() {
return r - l;
}
}; abc g; LL calc(LL x, LL pos) {
if (x < pos) return ;
return (x - pos) / pos / + ;
}
int main() {
//freopen("in.txt", "r", stdin);
int n;
while (cin >> n) {
g.Init();
rep0(i, n) {
int id, w;
sint(id);
if (id == ) {
sint(w);
g.push_back(w);
}
else {
LL L, R, k;
sint3(L, R, k);
int sz = g.size();
rep0(i, sz) {
LL pos = 1LL << g[i].second, c = calc(R, pos) - calc(L - , pos);
if (k <= c) {
pint(g[i].first);
pchr('\n');
break;
}
k -= c;
}
}
}
}
return ;
}
二：
#pragma comment(linker, "/STACK:10240000,10240000") #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <map>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <ctime>
#include <cctype>
#include <set> using namespace std; #define mem0(a) memset(a, 0, sizeof(a))
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define define_m int m = (l + r) >> 1
#define rep0(a, b) for (int a = 0; a < (b); a++)
#define rep1(a, b) for (int a = 1; a <= (b); a++)
#define all(a) (a).begin(), (a).end()
#define lowbit(x) ((x) & (-(x)))
#define constructInt4(name, a, b, c, d) name(int a = 0, int b = 0, int c = 0, int d = 0): a(a), b(b), c(c), d(d) {}
#define constructInt3(name, a, b, c) name(int a = 0, int b = 0, int c = 0): a(a), b(b), c(c) {}
#define constructInt2(name, a, b) name(int a = 0, int b = 0): a(a), b(b) {}
#define pchr(a) putchar(a)
#define pstr(a) printf("%s", a)
#define sint(a) ReadInt(a)
#define sint2(a, b) ReadInt(a);ReadInt(b)
#define sint3(a, b, c) ReadInt(a);ReadInt(b);ReadInt(c)
#define pint(a) WriteInt(a) typedef double db;
typedef long long LL;
typedef pair<int, int> pii;
typedef multiset<int> msi;
typedef set<int> si;
typedef vector<int> vi;
typedef map<int, int> mii; const int dx[] = {, , , -, , , -, -};
const int dy[] = {, , -, , -, , , -};
const int maxn = 1e3 + ;
const int maxm = 1e5 + ;
const int maxv = 1e7 + ;
const int max_val = 1e6 + ;
const int MD = 1e9 +;
const int INF = 1e9 + ;
const double PI = acos(-1.0);
const double eps = 1e-; template<class T>T gcd(T a, T b){return b==?a:gcd(b,a%b);}
template<class T>void ReadInt(T &x){char c=getchar();while(!isdigit(c))c=getchar();x=;while(isdigit(c)){x=x*+c-'';c=getchar();}}
template<class T>void WriteInt(T i) {int p=;static int b[];if(i == ) b[p++] = ;else while(i){b[p++]=i%;i/=;}for(int j=p-;j>=;j--)pchr(''+b[j]);} struct abc {
int a[];
int l, r;
void Init() { l = r = ; }
void push_back(int x) {
a[r++] = x;
if (r - l >= ) {
l++;
}
}
int &operator [] (int i) {
return a[l + i];
}
int size() {
return r - l;
}
}; abc g; pair<int, LL> a[]; LL calc(LL x, int id) {
LL start = 1LL << (g.size() - id - ), t = 1LL << (g.size() - id);
if (x < start) return ;
return (x - start) / t + ;
} int main() {
//freopen("in.txt", "r", stdin);
int n;
while (cin >> n) {
g.Init();
rep0(i, n) {
int id, w;
sint(id);
if (id == ) {
sint(w);
g.push_back(w);
}
else {
LL L, R, k;
sint3(L, R, k);
int total = , sz = g.size();
rep0(i, sz) {
LL c = calc(R, i) - calc(L - , i);
if (c > ) a[total++] = make_pair(g[i], c);
}
sort(a, a + total);
int now = ;
while () {
if (k <= a[now].second) {
break;
}
k -= a[now++].second;
}
pint(a[now].first);
pchr('\n');
}
}
}
return ;
}
最新文章
- 异常处理_Maven之web项目java.lang.LinkageError
- ios10 xcode8 适配的那些事
- handshake_failure
- mm/mmap.c
- js 用延时函数来实现像鼠标移入qq头像然后会出现新的模块
- latextools \cite 自动补全
- 开发环境安装 Java Mysql MyEclipse Android Adt
- CentOS 6.5 伪分布式 安装 hadoop 2.6.0
- JavaScript中的闭包理解
- css中z-index属性（标签层叠次序）
- Java中的注释
- Struts 2 标签库
- TCP/IP及内核参数优化调优
- 启动和停止SQL Server服务三种形式
- BZOJ2662[BeiJing wc2012]冻结——分层图最短路
- java基础学习之final关键字
- oracle-db安装
- bzoj3029 守卫者的挑战 （多维dp）
- 确保安全的HTTPS（使用混合加密的HTTPS，前端面试常问）第二篇
- OpenCL 事件的使用，以及回调函数