# 11041: 【原1041】二哥打飞机

### 题目描述

author: yydcool 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1041

## Description

“实在是太不爽了，看我把这些飞机全部打下来！”--二哥

N<=100000,二哥开口次数<=10000

## Sample Input

``````5
1 2 3 4 5
findmin 4
decrease 5 1
findmin 3
decrease 5 10
findmin 3
findmin -100
``````

## Sample Output

``````5
4
4
5
``````

## FineArtz's solution

``````/* 二哥打飞机 */
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

class cmp{
public:
bool operator()(pair<int, int> p1, pair<int, int> p2){
return (p1.second < p2.second || (p1.second == p2.second && p1.first < p2.first));
}
};

class Plane{
public:
bool operator <(const Plane &p){
return (h < p.h || (h == p.h && ind < p.ind));
}

int h = 0, ind = 0;
};

int n;
Plane a[100005];
int pos[100005];

void siftup(int x){
while (x > 1){
if (a[x] < a[x / 2]){
a[0] = a[x / 2];
a[x / 2] = a[x];
a[x] = a[0];
pos[a[x].ind] = x;
pos[a[x / 2].ind] = x / 2;
x /= 2;
}
else
break;
}
}

void makeheap(){
for (int i = n / 2 + 1; i <= n; ++i)
siftup(i);
}

int dfs(int x, int i){
if (a[i].h > x)
return i;
int r1 = 0, r2 = 0;
if (i * 2 <= n){
r1 = dfs(x, i * 2);
}
if (i * 2 + 1 <= n){
r2 = dfs(x, i * 2 + 1);
}
if (r1 == 0)
return r2;
else if (r2 == 0)
return r1;
else
return (a[r1] < a[r2] ? r1 : r2);
}

void findmin(int x){
int r = dfs(x, 1);
cout << a[r].ind << endl;
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
set<pair<int, int>, cmp> s;
cin >> n;
if (n <= 70000){
for (int i = 1; i <= n; ++i){
int h;
cin >> h;
s.insert(make_pair(i, h));
}
char ss[10];
while (cin >> ss){
if (ss[0] == 'd'){
int x, d;
cin >> x >> d;
auto it = find_if(s.begin(), s.end(), [x](pair<int, int> p){return p.first == x;});
auto t = *it;
t.second -= d;
s.erase(it);
s.insert(t);
}
else if (ss[0] == 'f'){
int x;
cin >> x;
auto it = find_if(s.begin(), s.end(), [x](pair<int, int> p){return p.second > x;});
cout << it->first << '\n';
}
}
}
else{
for (int i = 1; i <= n; ++i){
cin >> a[i].h;
a[i].ind = i;
pos[i] = i;
}
makeheap();
char s[10];
while (cin >> s){
if (s[0] == 'd'){
int x, d;
cin >> x >> d;
a[pos[x]].h -= d;
siftup(pos[x]);
}
else if (s[0] == 'f'){
int x;
cin >> x;
findmin(x);
}
}
}
return 0;
}
``````

## ligongzzz's solution

``````#include <iostream>
#include <string>
#include <map>
#include <set>
#include <vector>
using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int n;
cin >> n;

map<int, set<int>> mdata;
vector<int> vdata(n + 1);

for (int i = 1; i <= n; ++i) {
int temp;
cin >> temp;

if (mdata.find(temp) == mdata.end()) {
set<int> stmp;
stmp.insert(i);
mdata.insert(make_pair(temp, stmp));
}
else {
mdata[temp].insert(i);
}
vdata[i] = temp;
}

string op;
while (cin >> op) {
if (op == "findmin") {
int val;
cin >> val;

auto p = mdata.upper_bound(val);
cout << *(p->second.begin()) << "\n";
}
else if (op == "decrease") {
int i, j;
cin >> i >> j;
mdata[vdata[i]].erase(i);
vdata[i] -= j;
mdata[vdata[i]].insert(i);
}
}

return 0;
}
``````

## WashSwang's solution

``````#include <iostream>
#include <cstring>
using namespace std;
struct node{
int n,h;
};
char cmd[200];
node heap[200000];
int ptr[200000],num,x,d;
inline int ls(int x){ return x<<1;}
inline int rs(int x){ return x<<1|1;}
void minheapify(int x){
int s=x;
while (true){
if (ls(x)<=num&&(heap[ls(x)].h<heap[s].h||(heap[ls(x)].h==heap[s].h&&heap[ls(x)].n<heap[s].n))) s=ls(x);
if (rs(x)<=num&&(heap[rs(x)].h<heap[s].h||(heap[rs(x)].h==heap[s].h&&heap[rs(x)].n<heap[s].n))) s=rs(x);
if (s!=x)
{
swap(ptr[heap[s].n],ptr[heap[x].n]);
swap(heap[s],heap[x]);
x=s;
}
else break;
}
}
void modify(int x,int d){
heap[ptr[x]].h-=d;
minheapify(ptr[x]);
int cur=ptr[x];
while (cur>1){
if (heap[cur].h<heap[cur/2].h||(heap[cur].h==heap[cur/2].h&&heap[cur].n<heap[cur/2].n)){
swap(ptr[heap[cur].n],ptr[heap[cur/2].n]);
swap(heap[cur],heap[cur/2]);
cur/=2;
}
else break;
}
}
int findmin(int x,int cur){
int ans=0x3f3f3f3f,index=0x3f3f3f3f,tmp;
if (heap[cur].h<=x){
if (ls(cur)<=num){
tmp=findmin(x,ls(cur));
if (tmp<=num&&(heap[ptr[tmp]].h<ans||(heap[ptr[tmp]].h==ans&&tmp<index))) {
ans = heap[ptr[tmp]].h;
index = tmp;
}
}
if (rs(cur)<=num){
tmp=findmin(x,rs(cur));
if (tmp<=num&&(heap[ptr[tmp]].h<ans||(heap[ptr[tmp]].h==ans&&tmp<index))) {
ans = heap[ptr[tmp]].h;
index = tmp;
}
}
return index;
}
else return heap[cur].n;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin>>num;
for (int i=1;i<=num;++i) {
cin>>heap[i].h;
heap[i].n=i;
ptr[i]=i;
}
for (int i=num;i>=1;--i)
minheapify(i);
while (cin>>cmd){
if (strcmp(cmd,"findmin")==0){
cin>>x;
cout<<findmin(x,1)<<endl;
}
if (strcmp(cmd,"decrease")==0){
cin>>x>>d;
modify(x,d);
}
}
return 0;
}
``````

## yyong119's solution

``````#include <iostream>
#include <algorithm>
#define ERRORNUM 0x7fffffff
using namespace std;
const int SIZE = 100010;
int plane[SIZE];
pair<int, int> heap[SIZE];
int N;

void MinHeap(int pos) {

pair<int, int> tmp;
for (; pos > 1 && heap[pos >> 1] > heap[pos]; pos >>= 1) {
tmp = heap[pos >> 1];
heap[pos >> 1] = heap[pos];
heap[pos] = tmp;
}
}

void Maintain(int planeIndex, int decrease_height) {

int pos = plane[planeIndex];
pair<int, int> tmp;
heap[pos].first -= decrease_height;
for (; pos > 1 && heap[pos >> 1] > heap[pos]; pos >>= 1) {
tmp = heap[pos >> 1];
heap[pos >> 1] = heap[pos];
heap[pos] = tmp;
plane[heap[pos].second] = pos;
plane[heap[pos >> 1].second] = pos >> 1;
}
}

int FindMin(int min_height, int root_pos = 1) {

if (root_pos > N) return ERRORNUM;
if (heap[root_pos].first > min_height) return heap[root_pos].second;
return min(FindMin(min_height, root_pos << 1), FindMin(min_height, root_pos << 1 | 1));
}

int main() {

ios::sync_with_stdio(false);
cin >> N;
for (int i = 1; i <= N; ++i) {
cin >> heap[i].first;
heap[i].second = i;
MinHeap(i);
}
for (int i = 1; i <= N; ++i) plane[heap[i].second] = i;
char op[10];
while (cin >> op) {
if (op[0] == 'd') {
int planeIndex, decrease_height;
cin >> planeIndex >> decrease_height;
Maintain(planeIndex, decrease_height);
}
else {
int min_height;
cin >> min_height;
int planeIndex = FindMin(min_height);
cout << planeIndex << '\n';
}
}
return 0;
}
``````