d**********x 发帖数: 4083 | 1 那题目貌似就没卡复杂度。。。枉我昨天下班后还捏着鼻子写了个treap。。。结果证
明是输出格式错了,只过了两三个case的可以考虑检查一下输出格式
思路大致就是用order statistics tree。每次查询都是O(logn)。手写最大问题在于没
法定制容器的行为。。。
好吧,然后想了一下,如果用两个heap加一个map的话也是可以的,因为只是查询
median,没有要求随机查询kth元素,所以还是写复杂了
附上代码,treap是个随机平衡树,可以拿去用。
#include
#include
#include
#include
using namespace std;
template
class Treap {
public:
class Node {
public:
Node(const T& value)
: value_(value),
left_(NULL),
right_(NULL),
parent_(NULL),
count_(1)
{
rank_ = rand();
}
int getCount() {return count_;}
T getValue() {return value_;}
void updateCount() {
int leftCount = left_?left_->count_:0;
int rightCount = right_?right_->count_:0;
count_ = leftCount + rightCount + 1;
}
friend class Treap;
private:
Node* parent_;
Node* left_;
Node* right_;
int count_;
int rank_;
T value_;
};
void rightRotate(Node* node) {
Node* grand = node->parent_->parent_;
Node* right = node->right_;
Node* left = node->left_;
Node* parent = node->parent_;
node->right_ = parent;
node->parent_ = grand;
parent->left_ = right;
parent->parent_ = node;
if (grand) {
if (grand->left_ == parent) {
grand->left_ = node;
} else {
grand->right_ = node;
}
} else {
root_ = node;
}
if (right) {
right->parent_ = parent;
}
parent->updateCount();
node->updateCount();
}
void leftRotate(Node* node) {
Node* grand = node->parent_->parent_;
Node* right = node->right_;
Node* left = node->left_;
Node* parent = node->parent_;
node->left_ = parent;
node->parent_ = grand;
parent->right_ = left;
parent->parent_ = node;
if (grand) {
if (grand->left_ == parent) {
grand->left_ = node;
} else {
grand->right_ = node;
}
} else {
root_ = node;
}
if (left) {
left->parent_ = parent;
}
parent->updateCount();
node->updateCount();
}
Treap() {root_ = NULL;}
void insert(const T& value) {
Node* node = new Node(value);
Node* root = root_;
if (root == NULL) {
root_ = node;
return;
}
while(true) {
if (value < root->value_) {
root->count_++;
if (root->left_ == NULL) {
root->left_ = node;
node->parent_ = root;
break;
}
root = root->left_;
} else {
root->count_++;
if (root->right_ == NULL) {
root->right_ = node;
node->parent_ = root;
break;
}
root = root->right_;
}
}
while(node->parent_ != NULL && node->rank_ > node->parent_->rank_) {
if (node == node->parent_->left_) {
rightRotate(node);
} else {
leftRotate(node);
}
}
}
bool remove(const T& value) {
Node* node = find(value);
if (!node) {
return false;
}
while(node->left_ || node->right_) {
int rightRank = node->right_?node->right_->rank_:-1;
int leftRank = node->left_?node->left_->rank_:-1;
if (leftRank > rightRank) {
rightRotate(node->left_);
} else {
leftRotate(node->right_);
}
}
Node* parent = node->parent_;
if (!parent) {
root_ = NULL;
} else if (node == parent->left_) {
parent->left_ = NULL;
} else {
parent->right_ = NULL;
}
while(parent != NULL) {
parent->count_--;
parent = parent->parent_;
}
delete node;
return true;
}
Node* find(const T& value) {
Node* root = root_;
while(root != NULL) {
if (value == root->value_) {
return root;
} else if (value < root->value_) {
root = root->left_;
} else {
root = root->right_;
}
}
return root;
}
double findMedian() {
if (!root_) {
return -1;
}
int count = root_->count_;
if (count % 2) {
return findKth(count/2 + 1);
} else {
return ((double)findKth(count/2) + (double)findKth(count/2+1))/2;
}
}
T findKth(int k) {
Node* root = root_;
int leftCount = root->left_?root->left_->count_:0;
while(k != leftCount + 1) {
if (k > leftCount + 1) {
k = k - leftCount - 1;
root = root->right_;
} else {
root = root->left_;
}
leftCount = root->left_?root->left_->count_:0;
}
return root->value_;
}
void dump() {
cout << "-----------" << endl;
queue Q;
Q.push(root_);
Node* last = root_;
Node* newLast;
while(!Q.empty()) {
Node* cur = Q.front();
Q.pop();
if (cur->left_ != NULL) {
newLast = cur->left_;
Q.push(cur->left_);
}
if (cur->right_ != NULL) {
newLast = cur->right_;
Q.push(cur->right_);
}
cout << cur->value_ << "(" << cur->rank_ <<")" << (cur->parent_?
" ":"! ");
if (cur == last) {
last = newLast;
cout << endl;
}
}
cout << "-----------" << endl;
}
bool isEmpty() {
return root_ == NULL;
}
void outputMedian() {
cout.precision(1);
double median = findMedian();
if ((T)median == median) {
cout << (T)median << "\n";
} else {
cout << fixed << median << "\n";
}
}
private:
Node* root_;
};
int main(){
//Helpers for input and output
Treap treap;
int N;
cin >> N;
string s[N];
int x[N];
for(int i = 0; i < N; i++){
cin >> s[i] >> x[i];
if (s[i] == "r") {
bool result = treap.remove(x[i]);
if (!result || treap.isEmpty()) {
cout << "Wrong!\n";
} else {
treap.outputMedian();
}
} else if (s[i] == "a") {
treap.insert(x[i]);
treap.outputMedian();
}
}
return 0;
} |
a******3 发帖数: 113 | 2 本来看到版里这么多人讨论准备写这题的,看到楼主代码这么长,我还是先不写了。。 |
d**********x 发帖数: 4083 | 3 不用写这么长。。
据说比较暴力就能过。。
【在 a******3 的大作中提到】 : 本来看到版里这么多人讨论准备写这题的,看到楼主代码这么长,我还是先不写了。。
|
a******3 发帖数: 113 | 4
LZ这solution满分咯?
【在 d**********x 的大作中提到】 : 不用写这么长。。 : 据说比较暴力就能过。。
|
d**********x 发帖数: 4083 | 5 然后想了一下
hashtable + 2 heaps也不成问题,反正都是logN
这个平衡树就备用好了。。
{
/2;
_?
【在 d**********x 的大作中提到】 : 那题目貌似就没卡复杂度。。。枉我昨天下班后还捏着鼻子写了个treap。。。结果证 : 明是输出格式错了,只过了两三个case的可以考虑检查一下输出格式 : 思路大致就是用order statistics tree。每次查询都是O(logn)。手写最大问题在于没 : 法定制容器的行为。。。 : 好吧,然后想了一下,如果用两个heap加一个map的话也是可以的,因为只是查询 : median,没有要求随机查询kth元素,所以还是写复杂了 : 附上代码,treap是个随机平衡树,可以拿去用。 : #include : #include : #include
|
d**********x 发帖数: 4083 | 6 是啊。。。
【在 a******3 的大作中提到】 : : LZ这solution满分咯?
|
p*****2 发帖数: 21240 | 7 我就是用两个heap一个map。本来过了3个test cases。今天 调整了一下格式,又过了
几个,可是还有四个没过。不知道怎么回事。感觉我的算法应该没问题呀。 |
p*****2 发帖数: 21240 | 8
我是用了两个map。
【在 p*****2 的大作中提到】 : 我就是用两个heap一个map。本来过了3个test cases。今天 调整了一下格式,又过了 : 几个,可是还有四个没过。不知道怎么回事。感觉我的算法应该没问题呀。
|
d**********x 发帖数: 4083 | 9 再看看格式
昨天我就是搞了半天只能过俩case,后来发现double大数被我输出成科学计数法了。。
【在 p*****2 的大作中提到】 : 我就是用两个heap一个map。本来过了3个test cases。今天 调整了一下格式,又过了 : 几个,可是还有四个没过。不知道怎么回事。感觉我的算法应该没问题呀。
|
p*****2 发帖数: 21240 | 10
我现在是这么输出的,你看有什么问题吗?今天搞了一个上午了。Heap里存的是Long型
if(maxCount>minCount) return maxHeap.head.toString
else{
val sum=maxHeap.head+minHeap.head
if(sum%2==0) return (sum/2).toString
else return (sum/2).toString+".5"
}
【在 d**********x 的大作中提到】 : 再看看格式 : 昨天我就是搞了半天只能过俩case,后来发现double大数被我输出成科学计数法了。。
|
|
|
d**********x 发帖数: 4083 | 11 哈哈哈
他那个题目叙述错了,输入里面有负数
(-1 + 0) / 2会round到0
然后你就输出0.5了
。。
【在 p*****2 的大作中提到】 : : 我现在是这么输出的,你看有什么问题吗?今天搞了一个上午了。Heap里存的是Long型 : if(maxCount>minCount) return maxHeap.head.toString : else{ : val sum=maxHeap.head+minHeap.head : if(sum%2==0) return (sum/2).toString : else return (sum/2).toString+".5" : }
|
p*****2 发帖数: 21240 | 12
靠。太黑了呀。多谢。我去试试了。
【在 d**********x 的大作中提到】 : 哈哈哈 : 他那个题目叙述错了,输入里面有负数 : (-1 + 0) / 2会round到0 : 然后你就输出0.5了 : : 。。
|
p*****2 发帖数: 21240 | 13 改了改,还是有一个test case fail。这个输出有问题吗?
if(maxCount>minCount) return maxHeap.head.toString
else{
val sum:Long=maxHeap.head+minHeap.head
if(sum%2==0) return (sum/2).toString
else return "%.1f".format(sum.toDouble/2)
} |
d**********x 发帖数: 4083 | 14 这个就不知了。。。多测测?
【在 p*****2 的大作中提到】 : 改了改,还是有一个test case fail。这个输出有问题吗? : if(maxCount>minCount) return maxHeap.head.toString : else{ : val sum:Long=maxHeap.head+minHeap.head : if(sum%2==0) return (sum/2).toString : else return "%.1f".format(sum.toDouble/2) : }
|
p*****2 发帖数: 21240 | 15
哎。最烦输出格式这些东西了。不过多谢大牛了。
【在 d**********x 的大作中提到】 : 这个就不知了。。。多测测?
|
p****e 发帖数: 3548 | 16 大牛做过Arithmetic Progressions吗 |
d**********x 发帖数: 4083 | 17 Orz
非牛,那我去做做
【在 p****e 的大作中提到】 : 大牛做过Arithmetic Progressions吗
|
p*****2 发帖数: 21240 | 18
你太客气了。我觉得你很牛。
【在 d**********x 的大作中提到】 : Orz : 非牛,那我去做做
|
p****e 发帖数: 3548 | 19 大牛啊
题目有点长,为了帮你节省时间,有trick的
题目的解是
K = p1 + p2 + ... +pn
V = (K!*d1^p1*d2^p2*...*dn^pn)%1000003
a的值是没用的
就是怎样优化更新和查询的问题,求指导怎样才能过最后三个case
【在 d**********x 的大作中提到】 : Orz : 非牛,那我去做做
|
d**********x 发帖数: 4083 | 20 太强大了!
直接没看懂题。。求讲解怎么推的公式。。
另外没过的原因是timeout么。。
【在 p****e 的大作中提到】 : 大牛啊 : 题目有点长,为了帮你节省时间,有trick的 : 题目的解是 : K = p1 + p2 + ... +pn : V = (K!*d1^p1*d2^p2*...*dn^pn)%1000003 : a的值是没用的 : 就是怎样优化更新和查询的问题,求指导怎样才能过最后三个case
|
|
|
p****e 发帖数: 3548 | 21 是timeout,前面都过了
【在 d**********x 的大作中提到】 : 太强大了! : 直接没看懂题。。求讲解怎么推的公式。。 : 另外没过的原因是timeout么。。
|
d**********x 发帖数: 4083 | 22 复杂度多少?
【在 p****e 的大作中提到】 : 是timeout,前面都过了
|
p****e 发帖数: 3548 | 23 O(qlogNlogK)吧
【在 d**********x 的大作中提到】 : 复杂度多少?
|
p*****2 发帖数: 21240 | 24 靠。终于过了median。题目说的太不清楚了。 |
m****1 发帖数: 41 | 25 两个multiset解,保持两边的平衡就行,边界有点暴力 |
p****e 发帖数: 3548 | 26 gx, 到底里面有没负数的
【在 p*****2 的大作中提到】 : 靠。终于过了median。题目说的太不清楚了。
|
p*****2 发帖数: 21240 | 27
有负数。按照32bit signed int做就可以了。
【在 p****e 的大作中提到】 : gx, 到底里面有没负数的
|
p****e 发帖数: 3548 | 28 终于过了
原来的code过于关心查询速度,他家的test case着重于更新
【在 d**********x 的大作中提到】 : 复杂度多少?
|
d**********x 发帖数: 4083 | 29 - -
您还是给讲解下最初的公式怎么推的吧
【在 p****e 的大作中提到】 : 终于过了 : 原来的code过于关心查询速度,他家的test case着重于更新
|
p****e 发帖数: 3548 | 30 类似导数,每减一次就是求一次导,函数是x^K, 那些dn就是分母
所以最后答案就是那个了
严格证明就不懂了
median刚也过了,只要一个map就行了
【在 d**********x 的大作中提到】 : - - : 您还是给讲解下最初的公式怎么推的吧
|
|
|
r**h 发帖数: 1288 | 31 每个数列都看成一个pi次多项式,他们的积的最高次项就是(d1^p1*d2^p2*...*dn^pn)
,求sum(pi)阶导数再加上一个阶乘项
最后三个全部超时
尝试着先暂存一些阶乘的中间结果来减少每次阶乘的次数,结果完全不顶用- -;
【在 p****e 的大作中提到】 : 类似导数,每减一次就是求一次导,函数是x^K, 那些dn就是分母 : 所以最后答案就是那个了 : 严格证明就不懂了 : median刚也过了,只要一个map就行了
|
p****e 发帖数: 3548 | 32 阶乘要存到1000003,如果K大于等于那个数,V直接为0
【在 r**h 的大作中提到】 : 每个数列都看成一个pi次多项式,他们的积的最高次项就是(d1^p1*d2^p2*...*dn^pn) : ,求sum(pi)阶导数再加上一个阶乘项 : 最后三个全部超时 : 尝试着先暂存一些阶乘的中间结果来减少每次阶乘的次数,结果完全不顶用- -;
|
r**h 发帖数: 1288 | 33 嗯,这个优化我有做的
不过还是过不了啊
【在 p****e 的大作中提到】 : 阶乘要存到1000003,如果K大于等于那个数,V直接为0
|
p****e 发帖数: 3548 | 34 贴code的话可以帮你看看
【在 r**h 的大作中提到】 : 嗯,这个优化我有做的 : 不过还是过不了啊
|
r**h 发帖数: 1288 | 35 有劳了:)
加了点注释
#include
#include
#define MAX 1000003
using namespace std;
// 求(di^pi) % 1000003
long long getMod(int base, long long exp){
long long mod = 1;
for(int i=exp; i>0; i--){
mod = (mod*base) % MAX;
}
return mod;
}
// 求(n!/m!) % 1000003,不过m都是1
long long factorialMod(long long n, long long m){
long long mod = n;
while(--n >= m){
mod = (mod*n)%MAX;
}
return mod;
}
int main(){
int n, q;
cin>>n;
int *a = new int[n+1];
int *d = new int[n+1];
int *p = new int[n+1];
// m的作用是预存(di^pi)%1000003 = m[i],
long long *m = new long long[n+1];
for(int i=0; i
cin>>a[i+1]>>d[i+1]>>p[i+1];
m[i+1] = getMod(d[i+1], p[i+1]);
}
cin>>q;
while(q--){
int ins, i, j, v;
cin>>ins;
// 更新pi
if(ins == 1){
cin>>i>>j>>v;
for(int st=i;st<=j;st++){
p[st] += v;
m[st] = (m[st]*getMod(d[st], v)) % MAX;
}
}
// 求值,di^pi的连乘项
else{
cin>>i>>j;
long long sumP = 0;
long long sumMod = 1;
for(int st=i; st<=j; st++){
sumP += p[st];
sumMod = (sumMod * m[st]) % MAX;
}
// 加上阶乘的部分,打印结果
if(sumP < MAX)
sumMod = (sumMod * factorialMod(sumP, 1)) % MAX;
else
sumMod = 0;
cout<
}
}
delete[] a;
delete[] d;
delete[] p;
delete[] m;
}
【在 p****e 的大作中提到】 : 贴code的话可以帮你看看
|
p****e 发帖数: 3548 | 36 1. pow(x,n)太慢了
2. cin cout都换成scanf printf
3. 数组m不要,更新部分只要更新p就可以了
4. 阶乘的值要存到1000003,方便查
5. 先判断K的值,再计算V
【在 r**h 的大作中提到】 : 有劳了:) : 加了点注释 : #include : #include : #define MAX 1000003 : using namespace std; : // 求(di^pi) % 1000003 : long long getMod(int base, long long exp){ : long long mod = 1; : for(int i=exp; i>0; i--){
|
d**********x 发帖数: 4083 | 37 我发现hackerrank卡复杂度都不是特严格。。
【在 p****e 的大作中提到】 : 类似导数,每减一次就是求一次导,函数是x^K, 那些dn就是分母 : 所以最后答案就是那个了 : 严格证明就不懂了 : median刚也过了,只要一个map就行了
|
d**********x 发帖数: 4083 | 38 我知道了。。我擦。。
【在 p****e 的大作中提到】 : 类似导数,每减一次就是求一次导,函数是x^K, 那些dn就是分母 : 所以最后答案就是那个了 : 严格证明就不懂了 : median刚也过了,只要一个map就行了
|
p****e 发帖数: 3548 | 39 同觉得他家的test case很奇怪
【在 d**********x 的大作中提到】 : 我发现hackerrank卡复杂度都不是特严格。。
|
r**h 发帖数: 1288 | 40 按照你说的每一部分都做了优化,终于将将通过了。最后几个case都是2.8x s...
真BT啊
谢谢啦~
【在 p****e 的大作中提到】 : 1. pow(x,n)太慢了 : 2. cin cout都换成scanf printf : 3. 数组m不要,更新部分只要更新p就可以了 : 4. 阶乘的值要存到1000003,方便查 : 5. 先判断K的值,再计算V
|