http://blog.csdn.net/x_iya/article/details/8943264 使用樹狀數組，上面是樹狀數組的介紹 有一個很大的坑是用cout的時候超時，改成PRintf就ok了，做題感覺輸入輸出還是用printf和scanf最快，最穩
#include<iostream>#include<string>#include<vector>#include<algorithm>#pragma warning(disable:4996)using namespace std;int c[100001] = {0};int lowbit(int n){ return n&(-n);}int GetSum(int index){ int sum=0; while (index != 0) { sum += c[index]; index -= lowbit(index); } return sum;}void Add(int value, int index){ while (index < 100000) { c[index] += value; index += lowbit(index); }}int Getmid(int size){ int index = (1 + size) / 2; int low = 1, high = 100000,mid; while (low < high) { mid = (low + high) / 2; if (GetSum(mid) < index) low = mid + 1; else high = mid; } return low;}int main(){ vector<int> sort_vec; std::ios::sync_with_stdio(false);// cout << unitbuf;// freopen("0.txt", "w", stdout); vector<int> vec; int N; cin >> N; for (int t = 0;t < N;t++) { string str; cin >> str; switch (str[1]) { case 'o': { if (vec.empty()) printf("Invalid/n" ); else { int temp = vec.back(); printf("%d/n", temp); Add(-1, temp); vec.pop_back(); } } break; case 'e': { if (vec.empty()) printf("Invalid/n"); else printf("%d/n", Getmid(vec.size())); } break; case 'u': { int x; cin >> x; vec.push_back(x); Add(1, x); } break; } }}新聞熱點
疑難解答
