在我心里，ACM的意义之于程序员，就像剑道之于剑客一样，
都是一种境界上的追求，一种对自我要求的恪守。
每一次AC都是一次感动
没有人告诉你要走什么路线，什么时候前进，什么时候停止，
一切都取决于你自己，志向决定高度。
但也正是这么多的未知和可能性，产生了这么多的乐趣。
年轻人要少水群，多做题，才能进 WF——kuangbin
在我心里，ACM 的意义之于程序员，就像剑道之于剑客一样，
都是一种境界上的追求，一种对自我要求的恪守。
算法一定要自己实现，否则永远无法真正掌握
代码能力的提高没有捷径，只能踏踏实实一个一个敲，
类比数学的学习，搞懂一个题之后一定要亲自做一遍，否则以后遇到还是不会做
人一我百！人十我万！永不放弃~~~怀着自信的心，去追逐梦想。
尽管现在这份模板内容比较少，以后我会让它有血有肉起来~
-
关于STL
$STL$ （Standard Template Library,标准模版库）是 C++ 语言标准中的重要组成部分。$STL$以模板类和模版函数的形式为程序员提供了各种数据结构和算法的实现，程序员通过充分的利用$STL$，可以在代码空间、执行时间和编码效率上获得极大的好处。$STL$ 大致可以分为三大类：算法（$algorithm$）、容器（$container$）、迭代器（$iterator$）。$STL$ 容器是一些模版类，提供了多种组织数据的常用方法，例如：$vector$（向量，类似于数组）、$list$（列表，类似于链表）、$deque$（双向队列）、$set$（集合）、$map$（映像）、$stack$（栈）、$queue$（队列）、$priority_queue$（优先队列）等，通过模版的参数我们可以指定容器中的元素类型。$STL$ 算法是一些模版函数，提供了相当多的有用的算法和操作，从简单的$for_ each$ （遍历）到复杂的$stable_sort$（稳定排序）。$STL$ 迭代器将对 C 指针一般化，用来将算法和容器联系起来。几乎所有的$STL$算法都是通过迭代器来存取元素序列进行工作的，而$STL$中的每一个容器也都定义了其本身所专有的迭代器，用以存取容器中的元素。有趣的是，普通的指针也可以像迭代器一般的工作。熟悉了$STL$后，你会发现，很多功能只需要用短短的几行就可以实现了。通过$STL$，我们可以构造出优雅而且高效的代码，甚至比你自己手工实现的代码效率还要高很多。
$STL$ 的另外一个特点是，它是以源码方式免费提供的，程序员不仅可以自由地使用这些代码，也可以学习其源码，甚至可以按照自己的需要去修改它，这一点十分得人性化。 -
使用STL
在C＋＋标准中，$STL$被组织为以下的一组头文件（注意，是没有.h后缀的！）:
algorithm/deque/functional/iterator/list/map memory/numeric/queue/set/stack/utility/vector
但是需要强调的是，在实际的开发中，不建议直接导入std 命名空间，而在 ACM/ICPC 等算法竞赛中，直接导入会提高编码效率,所以我们要分清楚是竞赛还是实际的开发。
$STL$ 是C++语言机制运用的一个典范，通过学习$STL$可以更深刻的理解C++语言的思想和方法。建议在有了一些$STL$的使用经验后，认真阅读一下《C++ STL》这本书。
-
简介
$STL$ 的 头文件中描述了一个看上去非常简单的模板类$pair$ ，用来表示一个二元组或元素对，并提供了按照字典序(默认先比较$first$ ，若$first$ 相等，再比较$second$ )对元素进行大小比较运算符模板函数. -
用法
-
$pair$ 模板类对象有两个成员：$first$ 和$second$ ，分别表示首元素、尾元素. - 在中已定义六个⽐比较运算符：$<、>、<=、>=、==、!=$.
-
$make_pair$ 需要两个参数，分别为元素对的⾸首元素和尾元素.
-
-
示例
pair<int, string> p1; //default constructor pair<string, double> p2("zhouyu", 100); // overroad constructor pair<string, double> p3 = (p2); p2.first = "nobody"; p2.second = 20; pair<string, double> p1 = make_pair("tianyu", 100); pair<string, double> p2; p2 = p1; //overoad "=" cout << p2.first << " " << p2.second << endl;
-
简介
$set$ 是关联容器，用来存储同一种数据类型的数据结构，基本功能与数组相似。不同的是，在$set$ 中每个元素的值都是唯一的，而且系统能够根据元素的值自动进行排序。但是$set$ 中数元素的值并不能直接被改变.在头⽂文件中，还定义了另一非常实用的模版类 multiset（多重集合).
多重集合与集合的区别在于集合中能否存在相同元素.
两者基本操作相似，需要注意的是，集合的 count() 能返回 1、0 / 有、无，而多重集合是有多少返回多少.
-
用法
set<type> s // 创建一个type类集合 s.begin() // 返回指向第⼀一个元素的迭代器器 s.clear() // 清除所有元素 s.count() // 返回某个值元素的个数 s.empty() // 如果集合为空，返回true(真） s.end() // 返回指向后⼀一个元素之后的迭代器器，不不是后⼀一个元素 s.equal_range() // 返回集合中与给定值相等的上下限的两个迭代器器 s.erase() // 删除集合中的元素 s.find() // 返回⼀一个指向被查找到元素的迭代器器 s.get_allocator() // 返回集合的分配器器 s.insert() // 在集合中插⼊入元素 s.lower_bound() // 返回指向⼤大于（或等于）某值的第⼀一个元素的迭代器器 s.key_comp() // 返回⼀一个⽤用于元素间值⽐比较的函数 s.max_size() // 返回集合能容纳的元素的⼤大限值 s.rbegin() // 返回指向集合中后⼀一个元素的反向迭代器器 s.rend() // 返回指向集合中第⼀一个元素的反向迭代器器 s.size() // 集合中元素的数⽬目 s.swap() // 交换两个集合变量量 s.upper_bound() // 返回⼤大于某个值元素的迭代器器 s.value_comp() // 返回⼀一个⽤用于⽐比较元素间的值的函数
-
示例
-
简介
头文件中定义了$vector$ (向量容器模版类)，$vector$ 容器以连续数组的方式存储元素序列，可将$vector$ 看作是以顺序结构实现的线性表.
-
用法
vector<int> s; // 定义一个空的vector对象，存储的是int类型的元素 vector<int> s(n); // 定义一个含有n个int元素的vector对象 vector<int> s(first, last); // 定义一个vector对象，并从由迭代器first和last定义的序 列[first, last)中复制初值 s[i] // 直接以下标⽅方式访问容器中的元素 s.front() // 返回首元素 s.back() // 返回尾元素 （模拟栈操作） s.push_back(x) // 向表尾插入元素x s.size() // 返回表⻓ s.empty() // 表为空时，返回真，否则返回假 s.pop_back() // 删除表尾元素 s.begin() // 返回指向⾸首元素的随机存取迭代器 s.end() // 返回指向尾元素的下一个位置的随机存取迭代器 s.insert(it, val) // 向迭代器it指向的元素前插入新元素val s.insert(it, n, val) // 向迭代器it指向的元素前插入n个新元素val s.insert(it, first, last) // 将由迭代器first和last所指定的序列[first, last)插入到 迭代器it指向的元素前⾯面 s.erase(it) // 删除由迭代器it所指向的元素 s.erase(first, last) // 删除由迭代器first和last所指定的序列[first, last) s.reserve(n) // 预分配缓冲空间，使存储空间⾄至少可容纳n个元素 s.resize(n) // 改变序列⻓长度，超出的元素将会全部被删除，如果序列需要 扩展（原空间小于n），元素默认值将填满扩展出的空间 s.resize(n, val) // 改变序列⻓长度，超出的元素将会全部被删除，如果序列需要 扩展（原空间小于n），val将填满扩展出的空间 s.clear() // 删除容器中的所有元素 s.swap(v) // 将s与另一个vector对象进行交换 s.assign(first, last) // 将序列替换成由迭代器first和last所指定的序列[first, last)，[first, last)不能是原序列中的一部分 // 将序列替换成由迭代器first和last所指定的序列[first, last)，[first, last)不能是原序列中的一部分 // 要注意的是，resize和clear操作都是对表的有效元素进行的操作，但并不一定会改变缓冲空间的大小 // vector上还定义了序列之间的比较操作运算符（>、<、>=、<=、==、!=），可以按照字典序比较两个序列 // vector还有其他的一些操作，如反转、取反等
-
示例
vector<int> s; // 定义一个空的vector对象，存储的是int类型的元素 vector<int> s(n); // 定义一个含有n个int元素的vector对象 vector<int> s(first, last); // 定义一个vector对象，并从由迭代器first和last定义的 序列[first, last)中复制初值
-
简介
字符串是程序中经常要表达和处理的数据，我们通常采用字符数组或字符指针表示字符串。string 类的定义在头文件中，可以看作是一个字符的 vector，vector上的各种操作都可以适用于 string，另外，string 类还支持字符串的拼合、转换操作。
-
用法
-
示例
bool ok(int a, int b) { char buf[100]; string s1, s2; sprintf(buf, "%d", a); s1 = string(buf); sprintf(buf, "%d", b); s2 = string(buf); rep(i, 0, sz(s1)) { if(s2.find(s1.substr(i, 1)) != string::npos) return true; // npos is a static member constant value with the greatest possible value for an element of type size_t. // As a return value, it is usually used to indicate no matches. } return false; }
- 简介
- 用法
- 示例
- 简介
- 用法
- 示例
- 简介
- 用法
- 示例
-
简介
在STL的头文件中中定义了模版类bitset，用来方便地管理一系列的bit位类。bitset除了可以访问指定下标的bit位以外，还可以把它们作为一个整数来进行某些统计。
-
用法
-
示例
- 简介
- 用法
- 示例
- 简介
- 用法
- 示例
有一堆石子共有
n % (k + 1) == 0 // A必胜有
编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数
const int N = 1e3 + 5;
int T, cas = 0;
int n, m;
int dp[N][N];
char s[N], t[N];
int main(){
while(~scanf("%s%s", s, t)){
int n = (int)strlen(s), m = (int)strlen(t);
for(int i = 0; i <= n; i++) dp[i][0] = i;
for(int i = 0; i <= m; i++) dp[0][i] = i;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (s[i - 1] != t[j - 1]));
}
}
printf("%d\n", dp[n][m]);
}
return 0;
}- KMP_Pre
/*
* next[]的含义，x[i - next[i]...i - 1] = x[0...next[i] - 1]
* next[i]为满足x[i - z...i - 1] = x[0...z - 1]的最大z值（就是x的自身匹配）
*/
void KMP_Pre(char x[], int m, int next[]){
int i = 0;
int j = next[0] = -1;
while(i < m){
while(-1 != j && x[i] != x[j])
j = next[j];
next[++i] = ++j;
}
}- preKMP
/*
* kmpNext[]的意思：next'[i] = next[next[...[next[i]]]]
* （直到next'[i] < 0或者x[next'[i]] != x[i]）
* 这样的预处理可以快一些
*/
void preKMP(char x[], int m, int kmpNext[]){
int i = 0;
int j = kmpNext[0] = -1;
while(i < m){
while(-1 != j && x[i] != x[j])
j = kmpNext[j];
if (x[++i] == x[++j]) kmpNext[i] = kmpNext[j];
else kmpNext[i] = j;
}
}- KMP_Count
/*
* 此函数与上述两个函数中的任意一个搭配使用（即调用上述两个函数中的任意一个）
* 返回x在y中出现的次数，可以重叠
*/
int next[10010];
int KMP_Count(char x[], int m, char y[], int n){
// x是模式串，y是主串
int i = 0,j = 0;
int ans = 0;
// preKMP(x, m, next);
KMP_Pre(x, m, next);
while(i < n){
while(-1 != j && y[i] != x[j])
j = next[j];
i++, j++;
if (j >= m){
ans++;
j = next[j];
}
}
return ans;
}/*
* 扩展KMP
* next[i]:x[i...m-1]的最长公共前缀
* extend[i]:y[i...n-1]与x[0...m-1]的最长公共前缀
*/
void preEKMP(char x[], int m, int next[]){
next[0] = m;
int j = 0;
while(j + 1 < m && x[j] == x[j + 1]) j++;
next[1] = j;
int k = 1;
for(int i = 2; i < m; i++){
int p = next[k] + k - 1;
int L = next[i - k];
if (i + L < p + 1) next[i] = L;
else{
j = std::max(0, p - i + 1);
while(i + j < m && x[i + j] == x[j]) j++;
next[i] = j;
k = i;
}
}
}
void EKMP(char x[], int m, char y[], int n, int next[], int extend[]){
preEKMP(x, m, next);
int j = 0;
while(j < n && j < m && x[j] == y[j]) j++;
extend[0] = j;
int k = 0;
for(int i = 1; i < n; i++){
int p = extend[k] + k - 1;
int L = next[i - k];
if (i + L < p + 1) extend[i] = L;
else{
j = std::max(0, p - i + 1);
while(i + j < n && j < m && y[i + j] == x[j]) j++;
extend[i] = j;
k = i;
}
}
}const int MAXN = 110010;
char A[MAXN * 2];
int B[MAXN * 2];
void Manacher(char s[], int len){
int l = 0;
A[l++] = '$'; //0下标存储为其他字符
A[l++] = '#';
for(int i = 0; i < len; i++){
A[l++] = s[i];
A[l++] = '#';
}
A[l] = 0; //空字符
int mx = 0, id = 0;
for(int i = 0; i < l; i++){
B[i] = mx > i ? std::min(B[2 * id - i], mx - i) : 1;
while(A[i + B[i]] == A[i - B[i]]) B[i]++;
if(i + B[i] > mx){
mx = i + B[i];
id = i;
}
}
}
/*
* abaaba
* i: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
* A: $ # a # b # a # a # b # a # '\0'
* B: 1 1 2 1 4 1 2 7 2 1 4 1 2 1 //以第i个为中心的回文半径（包括第i个）
*/
char s[MAXN];
int main(){
while(std::cin >> s){
int len = (int)strlen(s);
Manacher(s, len);
int ans = 0;
for(int i = 0; i < 2 * len + 2; i++) //两倍长度并且首位插有字符，所以i < 2 * len + 2
ans = std::max(ans, B[i] - 1);
std::cout << ans << std::endl;
}
return 0;
}/*
* 注意：mod选择足够大的质数（至少大于字符串个数）
*/
unsigned int hashA(char *url, int mod){
unsigned int n = 0;
char *b = (char *)&n;
for (int i = 0; url[i]; i++) b[i % 4] ^= url[i];
return n % mod;
}
unsigned int hashB(char *url, int mod){
unsigned int h = 0,g;
while (*url){
h = (h << 4) + *url++;
g = h & 0xF0000000;
if (g) h ^= (g >> 24);
h &= ~g;
}
return h % mod;
}
unsigned int hashC(char *p, int prime = 25013){
unsigned int h = 0,g;
for (; *p; p++){
h = (h << 4) + *p;
g = h & 0xF0000000;
if (g){
h ^= (g >> 24);
h ^= g;
}
}
return h % prime;
}/*
* 划分树，类似线段树
* 主要求解某个区间第 k 大元素
* 时间复杂度 log(n)
*/
const int MAXN = 100010;
int tree[20][MAXN]; // 表示每层每个位置的值
int sorted[MAXN]; // 已经排序好的数
int toleft[20][MAXN]; // toleft[p][i]表示第i层从1到i有数分入左边
void build(int l, int r, int dep){
if(l == r) return;
int mid = (l + r) >> 1;
int same = mid - l + 1; // 表示等于中间值而且被分入左边的个数
for(int i = l; i <= r; i++) // 注意是l,不是1
if(tree[dep][i] < sorted[mid])
same--;
int lpos = l, rpos = mid + 1;
for(int i = l; i <= r; i++){
if(tree[dep][i] < sorted[mid])
tree[dep + 1][lpos++] = tree[dep][i];
else if(tree[dep][i] == sorted[mid] && same > 0){
tree[dep + 1][lpos++] = tree[dep][i];
same--;
}
else tree[dep + 1][rpos++] = tree[dep][i];
toleft[dep][i] = toleft[dep][l - 1] + lpos - l;
}
build(l, mid, dep + 1);
build(mid + 1, r, dep + 1);
}
// 查询区间第k大的数,[L,R]是大区间,[l,r]是要查询的小区间
int query(int L, int R, int l, int r, int dep, int k){
if(l == r) return tree[dep][l];
int mid = (L + R) >> 1;
int cnt = toleft[dep][r] - toleft[dep][l - 1];
if(cnt >= k){
int newl = L + toleft[dep][l - 1] - toleft[dep][L - 1];
int newr = newl + cnt - 1;
return query(L, mid, newl, newr, dep + 1, k);
}
else{
int newr = r + toleft[dep][R] - toleft[dep][r];
int newl = newr - (r - l - cnt);
return query(mid + 1, R, newl, newr, dep + 1, k - cnt);
}
}
int main(){
int n, m;
while(scanf("%d%d", &n, &m) == 2){
memset(tree, 0, sizeof(tree));
for(int i = 1; i <= n; i++){
scanf("%d", &tree[0][i]);
sorted[i] = tree[0][i];
}
sort(sorted + 1, sorted + n + 1);
build(1, n, 0);
int s, t, k;
while(m--){
scanf("%d%d%d", &s, &t, &k);
printf("%d\n", query(1, n, s, t, 0, k));
}
}
return 0;
}/*
* 合并复杂度 O(log N)
* INIT: init() 读入数据并进行初始化;
* CALL: merge() 合并两棵左偏树;
* ins() 插入一个新节点;
* top() 取得最小结点;
* pop() 取得并删除最小结点;
* del() 删除某结点;
* add() 增/减一个结点的键值;
* iroot() 获取结点i的根;
*/
#define typec int // type of key val
const int na = -1;
const int N = 1010;
struct node{
typec key;
int l, r, f, dist;
} tr[N];
int iroot(int i){
// find i's root
if(i == na) return i;
while (tr[i].f != na)
i = tr[i].f;
return i;
}
int merge(int rx, int ry){
// two root: rx, ry
if(rx == na) return ry;
if(ry == na) return rx;
if(tr[rx].key > tr[ry].key) swap(rx, ry);
int r = merge(tr[rx].r, ry);
tr[rx].r = r; tr[r].f = rx;
if(tr[r].dist > tr[tr[rx].l].dist) swap(tr[rx].l, tr[rx].r);
if(tr[rx].r == na) tr[rx].dist = 0;
else tr[rx].dist = tr[tr[rx].r].dist + 1;
return rx; // return new root
}
int ins(int i, typec key, int root){
// add a new node(i, key)
tr[i].key = key;
tr[i].l = tr[i].r = tr[i].f = na;
tr[i].dist = 0;
return root = merge(root, i); // return new root
}
int del(int i){
// delete node i
if(i == na) return i;
int x, y, l, r;
l = tr[i].l; r = tr[i].r; y = tr[i].f;
tr[i].l = tr[i].r = tr[i].f = na;
tr[x = merge(l, r)].f = y;
if(y != na && tr[y].l == i) tr[y].l = x;
if(y != na && tr[y].r == i) tr[y].r = x;
for(; y != na; x = y, y = tr[y].f){
if (tr[tr[y].l].dist < tr[tr[y].r].dist) swap(tr[y].l, tr[y].r);
if (tr[tr[y].r].dist + 1 == tr[y].dist) break;
tr[y].dist = tr[tr[y].r].dist + 1;
}
// return new root
return x != na ? iroot(x) : iroot(y);
}
node top(int root){
return tr[root];
}
node pop(int &root){
node out = tr[root];
int l = tr[root].l, r = tr[root].r;
tr[root].l = tr[root].r = tr[root].f = na;
tr[l].f = tr[r].f = na;
root = merge(l, r);
return out;
}
int add(int i, typec val){// tr[i].key += val
if(i == na) return i;
if(tr[i].l == na && tr[i].r == na && tr[i].f == na){
tr[i].key += val;
return i;
}
typec key = tr[i].key + val;
int rt = del(i);
return ins(i, key, rt);
}
void init(int n){
for(int i = 1; i <= n; i++){
scanf("%d", &tr[i].key); // %d: type of key
tr[i].l = tr[i].r = tr[i].f = na;
tr[i].dist = 0;
}
}k 叉
/*
* INIT: init();
* 注: tree[i][tk]>0时表示单词存在, 当然也可赋予它更多含义;
*/
const int tk = 26, tb = 'a'; // tk叉; 起始字母为tb;
const int N = 1010; // N: 最大结点个数
int top, tree[N][tk+1];
void init() {
top = 1;
memset(tree[0], 0, sizeof(tree[0]));
}
int sear(char *s) { // 失败返0
for(int rt = 0; rt == tree[rt][*s-tb];)
if(*(++s) == 0)
return tree[rt][tk];
return 0;
}
void insert(char *s, int rank = 1) {
int rt, nxt;
for(rt = 0; *s; rt = nxt, ++s) {
nxt = tree[rt][*s-tb];
if(0 == nxt) {
tree[rt][*s-tb] = nxt = top;
memset(tree[top], 0, sizeof(tree[top]));
top++;
}
}
tree[rt][tk] = rank; // 1表示存在0表示不存在,也可以赋予其其他含义
}
void delt(char *s) { // 只做标记, 假定s一定存在
int rt = 0;
for(; *s; ++s) rt = tree[rt][*s-tb];
tree[rt][tk] = 0;
}
int prefix(char *s) { // 最长前缀
int rt = 0, lv;
for(lv = 0; *s; ++s, ++lv) {
rt = tree[rt][*s-tb];
if (rt == 0) break;
}
return lv;
}左儿子右兄弟
const int N = 1010;
int top;一维
/*
* 求最大值，数组下标从1开始
* 求最小值，或者最大的最小值下标，数组从0开始修改一下即可
*/
const int N = 50010;
int dp[N][20];
int mm[N];
// 初始化RMQ。b数组是区间元素序列，下标从1开始
void initRMQ(int n, int b[]) {
mm[0] = -1;
for (int i = 1; i <= n; ++i) {
mm[i] = ((i&(i-1)) == 0) ? mm[i-1] + 1 : mm[i-1];
dp[i][0] = b[i];
}
for (int j = 1; j < mm[n]; ++j)
for (int i = 1; i + (1 << j) - 1 <= n; ++i)
dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
}
// 查询最大值
int rmq(int x, int y) {
int k = mm[y-x+1];
return max(dp[x][k], dp[y-(1<<k)+1][k]);
}二维
/*
* 预处理复杂度 nmlog(n)log(m)
* 数组下标从1开始
*/
int val[310][310];
int dp[310][310][9][9]; // 最大值
int mm[310]; // 二进制位数减一，使用前初始化
void initRMQ(int n, int m) {
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
dp[i][j][0][0] = val[i][j];
for(int ii = 0; ii < mm[n]; ++ii)
for(int jj = 0; jj < mm[m]; ++jj) if(ii+jj) {
for(int i = 1; i + (1 << ii) - 1 <= n; ++i)
for(int j = 1; j + (1 << jj) - 1 <= m; ++j) {
if(ii) dp[i][j][ii][jj] = max(dp[i][j][ii-1][jj],
dp[i+(1<<(ii-1))][j][ii-1][jj]);
else dp[i][j][ii][jj] = max(dp[i][j][ii][jj-1],
dp[i][j+(1<<(jj-1))][ii][jj-1]);
}
}
}
// 查询矩形内的最大值 (x1<=x2, y1<=y2)
int rmq(int x1, int y1, int x2, int y2) {
int k1 = mm[x2-x1+1];
int k2 = mm[y2-y1+1];
x2 = x2 - (1<<k1) + 1;
y2 = y2 - (1<<k2) + 1;
return max(max(dp[x1][y1][k1][k2], dp[x1][y2][k1][k2]),
max(dp[x2][y1][k1][k2], dp[x2][y2][k1][k2]));
}
int main() {
// 在外面对mm数组进行初始化
mm[0] = -1;
for(int i = 1; i <= 305; i++)
mm[i] = ((i&(i-1)) == 0) ? mm[i-1]+1 : mm[i-1];
int n, m, Q;
int r1, c1, r2, c2;
while(scanf("%d%d", &n, &m) == 2) {
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
scanf("%d", &val[i][j]);
initRMQ(n, m);
scanf("%d", &Q);
while(Q--) {
scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
if(r1 > r2) swap(r1, r2);
if(c1 > c2) swap(c1, c2);
int tmp = rmq(r1, c1, r2, c2);
printf("%d ", tmp);
if(tmp == val[r1][c1] || tmp == val[r1][c2]
|| tmp == val[r2][c1] || tmp == val[r2][c2])
puts("yes");
else puts("no");
}
}
return 0;
}/*
* 在[l, h)范围内查找值v,返回下标
* 假设a数组已经按从小到大排序
* 失败返回-1
*/
int bs(int a[], int l, int h, int v){
while(l < h){
int m = (l + h) >> 1;
if(a[m] == v) return m;
if(a[m] < v) l = m + 1;
else h = m;
}
return -1;
}/*
* 在[l, h)范围内查找值v,返回下标
* 假设a数组已经按从小到大排序
* 失败返回-1
*/
/*
* 传入参数必须在a[l]与a[h]之间
* 假设a数组已经按从小到大排序
* 返回值l总是合理的
*/
int bs(int a[], int l, int h, int v){
while(l < h){
int m = (l + h) >> 1;
if(a[m] < v) l = m + 1;
else h = m;
}
return l;
}/*
* 在下标[l, r]范围内查找,返回下标
* 假设a数组已经按从小到大排序
* 失败返回-1
*/
int bs(int a[], int l, int r, int v){
while(l < r){
int m = (l + r + 1) >> 1;
if(a[m] > v) r = m - 1;
else l = m;
}
if(a[l] > v) return -1;
return l;
}/*
* 二分套二分
* 数组A同数组B组合乘积，二分查找第K大
*/
typedef long long ll;
const int MAXN = 5e4 + 10;
ll N, K, A[MAXN], B[MAXN];
// 查找小于x的元素个数
ll check(ll x){
ll j = N, ans = 0;
for(int i = 1; i <= N; i++){
while(j > 0){
if (A[i] * B[j] > x) j--;
else break;
}
ans += j;
}
return ans;
}
int main(int argc, const char * argv[]){
cin >> N >> K;
for(int i = 1; i <= N; i++)
scanf("%lld %lld", A + i, B + i);
sort(A + 1, A + N + 1);
sort(B + 1, B + N + 1);
ll ans = 0;
ll key = N * N - K + 1;
ll low = A[1] * B[1]; // 初始最小值
ll high = A[N] * B[N]; // 初始最大值
while(high - low > 1){
ll mid = (low + high) >> 1;
if(check(mid) >= key){
ans = mid;
high = mid;
}
else low = mid;
}
cout << ans << '\n';
return 0;
}/*
* INIT: makeset(n);
* CALL: find(x);
* unin(x, y);
*/
const int N = 1010;
struct ufset{
int p[N], rank[N], sz;
void link(int x, int y){
if(x == y) return ;
if(rank[x] > rank[y]) p[y] = x;
else p[x] = y;
if(rank[x] == rank[y]) rank[y]++;
}
void makeset(int n){
sz = n;
for(int i = 0; i < sz; i++){
p[i] = i;
rank[i] = 0;
}
}
int find(int x){
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
void unin(int x, int y){
link(find(x), find(y));
}
void compress(){
for(int i = 0; i < sz; i++)
find(i);
}
};void ksort(int l, int h, int a[]){
if (h < l + 2) return ;
int e = h, p = l;
while(l < h){
while(++l < e && a[l] <= a[p]);
while(--h > p && a[h] >= a[p]);
if(l < h) swap(a[l], a[h]);
}
swap(a[h], a[p]);
ksort(p, h, a);
ksort(l, e, a);
}const int MAXSIZE = 200;
void Add(char *str1, char *str2, char *str3);
void Minus(char *str1, char *str2, char *str3);
void Mul(char *str1, char *str2, char *str3);
void Div(char *str1, char *str2, char *str3);
int main(){
char str1[MAXSIZE], str2[MAXSIZE], str3[MAXSIZE];
while(scanf("%s %s", str1, str2) == 2){
if(strcmp(str1, "0")){
memset(str3, '0', sizeof(str3));
Add(str1, str2, str3);
printf("%s\n", str3);
memset(str3, '0', sizeof(str3));
Minus(str1, str2, str3);
printf("%s\n", str3);
memset(str3, '0', sizeof(str3));
Mul(str1, str2, str3);
printf("%s\n", str3);
memset(str3, '0', sizeof(str3));
Div(str1, str2, str3);
printf("%s\n", str3);
}
else{
if(strcmp(str2, "0")) printf("%s\n-%s\n0\n0\n", str2, str2);
else printf("0\n0\n0\n0\n");
}
}
return 0;
}
void Add(char *str1, char *str2, char *str3){
// str3 = str1 + str2;
int i, j, i1, i2, tmp, carry;
int len1 = (int)strlen(str1), len2 = (int)strlen(str2);
char ch;
i1 = len1 - 1;
i2 = len2 - 1;
j = carry = 0;
for(; i1 >= 0 && i2 >= 0; ++j, --i1, --i2){
tmp = str1[i1] - '0' + str2[i2] - '0' + carry;
carry = tmp / 10;
str3[j] = tmp % 10 + '0';
}
while(i1 >= 0){
tmp = str1[i1--] - '0' + carry;
carry = tmp / 10;
str3[j++] = tmp % 10 + '0';
}
while(i2 >= 0){
tmp = str2[i2--] - '0' + carry;
carry = tmp / 10;
str3[j++] = tmp % 10 + '0';
}
if(carry)
str3[j++] = carry + '0';
str3[j] = '\0';
for(i = 0, --j; i < j; ++i, --j){
ch = str3[i];
str3[i] = str3[j];
str3[j] = ch;
}
return ;
}
void Minus(char *str1, char *str2, char *str3){
// str3 = str1-str2 (str1 > str2)
int i, j, i1, i2, tmp, carry;
int len1 = (int)strlen(str1), len2 = (int)strlen(str2);
char ch;
i1 = len1 - 1;
i2 = len2 - 1;
j = carry = 0;
while(i2 >= 0){
tmp = str1[i1] - str2[i2] - carry;
if(tmp < 0){
str3[j] = tmp + 10 + '0';
carry = 1;
}
else{
str3[j] = tmp + '0';
carry = 0;
}
i1--;
i2--;
j++;
}
while(i1 >= 0){
tmp = str1[i1] - '0' - carry;
if(tmp < 0){
str3[j] = tmp + 10 + '0';
carry = 1;
}
else{
str3[j] = tmp + '0';
carry = 0;
}
--i1;
++j;
}
--j;
while(str3[j] == '0' && j > 0) --j;
str3[++j] = '\0';
for(i = 0, --j; i < j; ++i, --j){
ch = str3[i];
str3[i] = str3[j];
str3[j] = ch;
}
return ;
}
void Mul(char *str1, char *str2, char *str3){
int i, j = 0, i1, i2, tmp, carry, jj;
int len1 = (int)strlen(str1), len2 = (int)strlen(str2);
char ch;
jj = carry = 0;
for(i1 = len1 - 1; i1 >= 0; --i1){
j = jj;
for(i2 = len2 - 1; i2 >= 0; --i2, ++j){
tmp = (str3[j] - '0') + (str1[i1] - '0') * (str2[i2] - '0') + carry;
if(tmp > 9){
carry = tmp / 10;
str3[j] = tmp % 10 + '0';
}
else{
str3[j] = tmp + '0';
carry = 0;
}
}
if(carry){
str3[j] = carry + '0';
carry = 0;
j++;
}
jj++;
}
j--;
while(str3[j] == '0' && j > 0) j--;
str3[++j] = '\0';
for(i = 0, --j; i < j; ++i, --j){
ch = str3[i];
str3[i] = str3[j];
str3[j] = ch;
}
return ;
}
void Div(char *str1, char *str2, char *str3){
int i1, i2, i, j, jj = 0, tag, carry, cf, c[MAXSIZE];
int len1 = (int)strlen(str1), len2 = (int)strlen(str2), lend;
char d[MAXSIZE];
memset(c, 0, sizeof(c));
memcpy(d, str1, len2);
lend = len2;
j = 0;
for(i1 = len2 - 1; i1 < len1; ++i1){
if(lend < len2){
d[lend] = str1[i1+1];
c[j] = 0;
++j;
++lend;
}
else if(lend == len2){
jj = 1;
for(i = 0; i < lend; ++i){
if(d[i] > str2[i]) break;
else if(d[i] < str2[i]){
jj = 0;
break;
}
}
if(jj == 0){
d[lend] = str1[i1+1];
c[j] = 0;
++j;
++lend;
continue;
}
}
if(jj == 1 || lend > len2){
cf = jj = 0;
while(d[jj] <= '0' && jj < lend) ++jj;
if (lend - jj > len2) cf = 1;
else if(lend - jj < len2) cf = 0;
else{
i2 = 0;
cf = 1;
for(i = jj; i < lend; ++i){
if(d[i] < str2[i2]){
cf = 0;
break;
}
else if(d[i] > str2[i2]) break;
++i2;
}
}
while(cf){
i2 = len2 - 1;
cf = 0;
for(i = lend - 1; i >= lend - len2; --i){
d[i] = d[i] - str2[i2] + '0';
if(d[i] < '0'){
d[i] = d[i] + 10;
carry = 1;
--d[i - 1];
}
else carry = 0;
--i2;
}
++c[j];
jj = 0;
while(d[jj] <= '0' && jj < lend) ++jj;
if (lend - jj > len2) cf = 1;
else if(lend - jj < len2) cf = 0;
else{
i2 = 0;
cf = 1;
for(i = jj; i < lend; ++i){
if(d[i] < str2[i2]){
cf = 0;
break;
}
else if(d[i] > str2[i2]) break;
++i2;
}
}
}
jj = 0;
while(d[jj] <= '0' && jj < lend) ++jj;
for(i = 0; i < lend - jj; ++i) d[i] = d[i + jj];
d[i] = str1[i1 + 1];
lend = i + 1;
j++;
}
}
i = tag = 0;
while(c[i] == 0) ++i;
for(; i < j; ++i, ++tag)
str3[tag] = c[i]+'0';
str3[tag] = '\0';
return ;
}/*
* < , <= , + , - , * , / , %(修改/的最后一行可得)
*/
const int base = 10000; // (base^2) fit into int
const int width = 4; // width = log_10(base)
const int MAXN = 100000; // MAXN * width: 可表示的最大位数
const int MAXC = 1e5 + 10;
struct bint{
int ln, v[MAXN];
bint(int r = 0){
// r应该是字符串!
for (ln = 0; r > 0; r /= base)
v[ln++] = r % base;
}
bint &operator = (const bint &r){
memcpy(this, &r, (r.ln + 1) * sizeof(int));
return *this;
}
};
bool operator < (const bint &a, const bint &b){
int i;
if (a.ln != b.ln) return a.ln < b.ln;
for (i = a.ln - 1; i >= 0 && a.v[i] == b.v[i]; i--) ;
return i < 0 ? 0 : a.v[i] < b.v[i];
}
bool operator <= (const bint &a, const bint &b){
return !(b < a);
}
bint operator + (const bint &a, const bint &b){
bint res;
int i, cy = 0;
for(i = 0; i < a.ln || i < b.ln || cy > 0; i++){
if(i < a.ln) cy += a.v[i];
if(i < b.ln) cy += b.v[i];
res.v[i] = cy % base;
cy /= base;
}
res.ln = i;
return res;
}
bint operator - (const bint &a, const bint &b){
bint res;
int i, cy = 0;
for(res.ln = a.ln, i = 0; i < res.ln; i++){
res.v[i] = a.v[i] - cy;
if(i < b.ln)
res.v[i] -= b.v[i];
if(res.v[i] < 0)
cy = 1, res.v[i] += base;
else cy = 0;
}
while(res.ln > 0 && res.v[res.ln - 1] == 0) res.ln--;
return res;
}
bint operator * (const bint &a, const bint &b){
bint res;
res.ln = 0;
if(0 == b.ln){
res.v[0] = 0;
return res;
}
int i, j, cy;
for(i = 0; i < a.ln; i++){
for(j = cy = 0; j < b.ln || cy > 0; j++, cy /= base){
if(j < b.ln)
cy += a.v[i] * b.v[j];
if(i + j < res.ln)
cy += res.v[i + j];
if(i + j >= res.ln)
res.v[res.ln++] = cy % base;
else
res.v[i + j] = cy % base;
}
}
return res;
}
bint operator / (const bint &a, const bint &b){
// !b != 0
bint tmp, mod, res;
int i, lf, rg, mid;
mod.v[0] = mod.ln = 0;
for(i = a.ln - 1; i >= 0; i--){
mod = mod * base + a.v[i];
for(lf = 0, rg = base -1; lf < rg;){
mid = (lf + rg + 1) / 2;
if(b * mid <= mod) lf = mid;
else rg = mid - 1;
}
res.v[i] = lf;
mod = mod - b * lf;
}
res.ln = a.ln;
while(res.ln > 0 && res.v[res.ln - 1] == 0)
res.ln--;
return res; // return mod; 就是%运算
}
int digits(bint& a){// 返回位数
if(a.ln == 0) return 0;
int l = (a.ln - 1) * 4;
for(int t = a.v[a.ln - 1]; t; ++l, t /= 10);
return l;
}
bool read(bint &b, char buf[]){
if(1 != scanf("%s", buf)) return 0; // 读取失败返回0
int w, u, ln = (int)strlen(buf);
memset(&b, 0, sizeof(bint));
if('0' == buf[0] && 0 == buf[1]) return 1;
for(w = 1, u = 0; ln; ){
u += (buf[--ln] - '0') * w;
if(w * 10 == base){
b.v[b.ln++] = u;
w = 1;
u = 0;
}
else w *= 10;
}
if(w != 1) b.v[b.ln++] = u;
return 1;
}
void write(const bint &v){
int i;
printf("%d", v.ln == 0 ? 0 : v.v[v.ln - 1]);
for(i = v.ln - 2; i >= 0; i--)
printf("%04d", v.v[i]); // !!! 4 == width
printf("\n");
return ;
}
char buf[MAXC];
int main(){
bint A, B, C, D;
read(A, buf);
read(B, buf);
C = A / B; // floor(A/B)
write(C);
D = B * C;
D = A - D; // A%B
write(D);
return 0;
}typedef long long ll;
class BigInteger{
private:
const static int MOD = (119 << 23) + 1;
const static int root = 3;
const static int invroot = 332748118;
int *a;
int length, sig;
void apply(int length){
if(!length) return ;
a = new int [length]();
this->length = length;
}
void destroy(){
if(!length) return ;
delete[] a;
a = NULL;
}
void resize(int length){
if(length == this->length) return ;
if(!length) return destroy();
int *aux = a;
a = new int [length]();
memcpy(a, aux, sizeof(int) * min(length, this->length));
if(this->length) delete [] aux;
this->length = length;
}
BigInteger(int length) : length(length), sig(0){
apply(length);
}
BigInteger(const BigInteger &p, int length) : length(length), sig(p.sig){
apply(length);
memcpy(a, p.a, sizeof(int) * min(p.length, length));
}
bool absgreaterequal(const BigInteger &q) const{
if(length != q.length) return length > q.length;
for(int i = length - 1; ~i; -- i){
if(a[i] > q.a[i]) return true;
if(a[i] < q.a[i]) return false;
}
return true;
}
BigInteger operator << (const int &dis) const{
if(!sig) return *this;
BigInteger ret(length + dis);
memcpy(ret.a + dis, a, sizeof(int) * length);
ret.sig = sig;
return ret;
}
BigInteger operator >> (const int &dis) const{
if(dis >= length) return BigInteger();
BigInteger ret(length - dis);
memcpy(ret.a, a + dis, sizeof(int) * ret.length);
ret.sig = sig;
return ret;
}
int powermod(int a, int exp) const{
int ret = 1;
for(; exp; exp >>= 1){
if(exp & 1) ret = (ll) ret * a % MOD;
a = (ll) a * a % MOD;
}
return ret;
}
void NTT(int *a, int length, int type) const{
int len = -1;
for(int x = length; x; ++len, x >>= 1) ;
for(int i = 1, j = 0; i < length - 1; ++i){
for(int s = length; j ^= s >>= 1, ~j & s; ) ;
if(i < j) swap(a[i], a[j]);
}
for(int i = 1; i <= len; ++ i){
for(int j = 0, unit = powermod(type == 1 ? root : invroot,
(MOD - 1) >> i), szk = 1 << (i - 1); j < length; j += 1 << i){
for(int k = j, w = 1; k < j + szk; ++ k){
int s = a[k], t = (ll) w * a[k + szk] % MOD;
a[k] = s + t >= MOD ? s + t - MOD : s + t;
a[k + szk] = s - t < 0 ? s - t + MOD : s - t;
w = (ll) w * unit % MOD;
}
}
}
if(type == 1) return ;
int inv = powermod(length, MOD - 2);
for(int i = 0; i < length; ++i)
a[i] = (ll) a[i] * inv % MOD;
}
int divide(BigInteger &p, const int &q) const{
if(!q) assert(-1);
if(!p.sig) return 0;
ll remain = 0, x = abs(q);
for(int i = length - 1; ~i; -- i){
remain = remain * 10 + p.a[i];
p.a[i] = (int)(remain / x);
remain %= x;
}
for(; p.length && !p.a[p.length - 1]; -- p.length) ;
remain *= p.sig;
p.sig *= q < 0 ? -1 : 1;
if(!p.length) p.sig = 0;
return (int)remain;
}
public:
BigInteger() : length(0), sig(0) { a = NULL; }
BigInteger(const BigInteger &p) : length(p.length), sig(p.sig){
apply(length), memcpy(a, p.a, sizeof(int) * length);
}
~BigInteger() { destroy(); }
int getlength() { return length; }
bool positive() { return sig > 0; }
bool iszero() { return !sig; }
bool negative() { return sig < 0; }
bool even() { return !sig || !(a[0] & 1); }
BigInteger &operator = (const BigInteger &p){
destroy();
apply(p.length);
length = p.length;
sig = p.sig;
memcpy(a, p.a, sizeof(int) * length);
return *this;
}
template <typename T>
BigInteger &operator = (const T &p){
destroy();
sig = p ? p > 0 ? 1 : -1 : 0;
apply(40);
int cnt = 0;
for(T x = abs(p); x; x /= 10) a[cnt++] = x % 10;
resize(cnt);
return *this;
}
void read(){
destroy();
sig = 1;
char ch = getchar();
for( ; ch < '0' || ch > '9'; ch = getchar())
if (ch == '-')
sig = -1;
resize(1);
int nowlength = 0;
for(; ch >= '0' && ch <= '9'; ch = getchar()){
a[nowlength++] = ch - '0';
if(nowlength == length){
resize(length << 1);
}
}
reverse(a, a + nowlength);
for(; nowlength && !a[nowlength - 1]; --nowlength) ;
resize(nowlength);
sig = length ? sig : 0;
}
void write(){
if(!sig) return (void)putchar('0');
if(sig < 0) putchar('-');
for(int i = length - 1; ~i; i--)
putchar(a[i] + '0');
}
template <typename T>
T tointeger(){
T ret = 0;
for(int i = length - 1; i >= 0; ++ i)
ret = ret * 10 + a[i];
return ret * sig;
}
bool operator == (const BigInteger &p) const{
if(sig != p.sig || length != p.length)
return false;
for(int i = 0; i < length; ++i)
if (a[i] != p.a[i])
return false;
return true;
}
bool operator > (const BigInteger &p) const{
if(sig != p.sig) return sig > p.sig;
if(length != p.length)
return length > p.length ^ sig == -1;
for(int i = length - 1; i >= 0; --i){
if(a[i] > p.a[i])
return sig > 0;
if(a[i] < p.a[i])
return sig < 0;
}
return false;
}
BigInteger &operator ++ (){
resize(length + 1);
sig >= 0 ? ++a[0] : --a[0];
for(int i = 0; i < length - 1; ++i){
if(a[i] < 10 && a[i] >= 0) break;
a[i] >= 10 ? (a[i] -= 10, ++a[i + 1]) : (a[i] += 10, --a[i + 1]);
}
for(; length && !a[length - 1]; --length) ;
resize(length);
sig = length ? sig >= 0 ? 1 : -1 : 0;
return *this;
}
BigInteger &operator -- (){
sig = -sig;
++*this;
sig = -sig;
return *this;
}
BigInteger operator ++ (int){
BigInteger aux(*this);
++*this;
return aux;
}
BigInteger operator -- (int){
BigInteger aux(*this);
--*this;
return aux;
}
BigInteger operator + (const BigInteger &p) const{
if(!p.sig) return *this;
if(!sig) return p;
bool type = true, flag = sig > 0;
const BigInteger *aux = this, *aux1 = &p;
if(sig != p.sig){
type = false;
if (!absgreaterequal(p)){
flag = !flag;
swap(aux, aux1);
}
}
BigInteger ret(*aux, max(length, p.length) + 1);
for(int i = 0; i < ret.length - 1; ++i){
ret.a[i] += i < aux1->length ? type ? aux1->a[i] : -aux1->a[i] : 0;
ret.a[i] >= 10 ? (ret.a[i] -= 10, ++ret.a[i + 1]) :
ret.a[i] < 0 ? (ret.a[i] += 10, --ret.a[i + 1]) : 0;
}
for(; ret.length && !ret.a[ret.length - 1]; --ret.length) ;
ret.resize(ret.length);
ret.sig = ret.length ? flag ? 1 : -1 : 0;
return ret;
}
BigInteger operator - () const{
BigInteger ret(*this);
ret.sig = -ret.sig;
return ret;
}
BigInteger operator - (const BigInteger &p) const { return *this + (-p); }
BigInteger operator * (const BigInteger &p) const{
if(!sig || !p.sig) return BigInteger();
int n = length + p.length;
int lengthret = 1;
for(; lengthret < n; lengthret <<= 1) ;
BigInteger ret(*this, lengthret);
int *aux = new int [lengthret]();
memcpy(aux, p.a, sizeof(int) * p.length);
NTT(ret.a, lengthret, 1);
NTT(aux, lengthret, 1);
for(int i = 0; i < lengthret; ++i)
ret.a[i] = (ll) ret.a[i] * aux[i] % MOD;
NTT(ret.a, lengthret, -1);
for(int i = 0; i < n - 1; i++){
ret.a[i + 1] += ret.a[i] / 10;
ret.a[i] %= 10;
}
for(; n && !ret.a[n - 1]; --n) ;
ret.resize(n);
ret.sig = sig * p.sig;
return ret;
}
BigInteger operator * (const int &p) const{
if(!p || !sig) return BigInteger();
BigInteger ret(*this, length + 10);
ll x = abs(p), remain = 0;
for(int i = 0; i < length; ++ i){
remain += ret.a[i] * x;
ret.a[i] = remain % 10;
remain /= 10;
}
int nowlength = length;
for(ret.a[nowlength] = (int)remain; ret.a[nowlength]; ++nowlength){
ret.a[nowlength + 1] = ret.a[nowlength] / 10;
ret.a[nowlength] %= 10;
}
for(; nowlength && !ret.a[nowlength - 1]; --nowlength) ;
ret.resize(nowlength);
ret.sig = sig * (p < 0 ? -1 : 1);
return ret;
}
BigInteger operator / (const BigInteger &p) const{
if(!p.sig) assert(-1);
if(!sig || length < p.length)
return BigInteger();
int num = 0;
for(int i = p.length - 1; i >= p.length - 3; --i)
(num *= 10) += i >= 0 ? p.a[i] : 0;
num = 100000 / num;
int nowprecision = 1;
BigInteger ret;
ret = num;
for(; nowprecision <= length - p.length; nowprecision <<= 1){
BigInteger aux((nowprecision << 1) + 3);
aux.sig = 1;
for(int i = p.length - aux.length; i < p.length; ++i)
aux.a[i - p.length + aux.length] = i >= 0 ? p.a[i] : 0;
aux = (aux * ret >> (nowprecision + 2)) * ret >> (nowprecision + 2);
ret = (ret * 2 << nowprecision) - aux;
}
ret = ret * *this >> (p.length + nowprecision + 1);
ret.sig = abs(ret.sig);
BigInteger aux(p);
aux.sig = abs(aux.sig);
if(!absgreaterequal(ret * aux)) --ret;
else if(!absgreaterequal(++ret * aux)) --ret;
ret.sig *= sig * p.sig;
return ret;
}
BigInteger operator / (const int &p) const{
BigInteger ret(*this);
divide(ret, p);
ret.resize(ret.length);
return ret;
}
BigInteger sqrt() const{
if(sig < 0) assert(-1);
if(!sig) return *this;
int num = 0;
for(int i = length - 1; i >= length - 8; --i)
(num *= 10) += i >= 0 ? a[i] : 0;
ll x = length & 1 ? 10000000000000ll : 100000000000000ll;
num = std::sqrt(1.0 * x / num); // 命名空间不能省
int nowprecision = 2;
BigInteger ret;
ret = num;
for(; nowprecision <= (length >> 1) + 1; nowprecision = (nowprecision << 1) - 1){
BigInteger aux((nowprecision << 1) + 1 + (length & 1));
aux.sig = 1;
for(int i = length - aux.length; i < length; ++i)
aux.a[i - length + aux.length] = i >= 0 ? a[i] : 0;
aux = ((aux * ret >> (nowprecision + 1)) * ret >> (nowprecision + 1)) / 2;
BigInteger aux1((nowprecision + 1) << 1);
aux1.sig = 1;
aux1.a[aux1.length - 1] = 1, aux1.a[aux1.length - 2] = 5;
ret = ret * (aux1 - aux) >> (nowprecision + 2);
}
ret = ret * *this >> ((length >> 1) + nowprecision + 1);
if(!absgreaterequal(ret * ret)) --ret;
else{
++ret;
if(!absgreaterequal(ret * ret)) --ret;
}
return ret;
}
BigInteger operator % (const BigInteger &p) const{
if(!p.sig) assert(-1);
return *this - *this / p * p;
}
int operator % (const int &p) const{
if(!p) assert(-1);
BigInteger aux(*this);
return divide(aux, p);
}
friend BigInteger operator * (const int &q, const BigInteger &p) { return p * q; }
BigInteger &operator += (const BigInteger &p) { *this = *this + p; return *this; }
BigInteger &operator -= (const BigInteger &p) { *this = *this - p; return *this; }
BigInteger &operator *= (const BigInteger &p) { *this = *this * p; return *this; }
BigInteger &operator *= (const int &p) { *this = *this * p; return *this; }
BigInteger &operator /= (const BigInteger &p) { *this = *this / p; return *this; }
BigInteger &operator /= (const int &p) { *this = *this / p; return *this; }
BigInteger &operator %= (const BigInteger &p) { *this = *this % p; return *this; }
BigInteger &operator %= (const int &p) { *this = *this % p; return *this; }
template <typename T>
BigInteger power(T exp) const{
BigInteger ret = 1, aux(*this);
for(; exp; exp >>= 1){
if(exp & 1) ret *= aux;
aux *= aux;
}
return ret;
}
};
BigInteger a;
int main() {
a.read();
a.sqrt().write();
putchar(10);
return 0;
}/*
* 取第k个元素
* k = 0 ... n - 1,平均复杂度O(n) 注意a[]中的顺序被改变
*/
#define _cp(a,b) ((a) < (b))
typedef int elem_t;
elem_t kth_element(int n, elem_t *a, int k) {
// a[0 ... n-1]
elem_t t, key;
int l = 0, r = n - 1, i, j;
while(l < r) {
for(key = a[((i = l - 1) + (j = r + 1)) >> 1]; i < j;) {
for(j--; _cp(key, a[j]); j--);
for(i++; _cp(a[i], key); i++);
if(i < j) t = a[i], a[i] = a[j], a[j] = t;
}
if(k > j) l = j + 1;
else r = j;
}
return a[k];
}