我一看，这不是bst么？可是我是来刷noip的知识点的呀？
再一看，只需要输出全局最大最小。
猛然间，我想起了一个去世（假的）兄弟滑动窗口的做法。
他使用一个堆。只考虑对答案有影响的点。对堆中储存大小和位置。
如果堆顶元素的位置不在当前区间内，则一直弹出，知道堆为空或者位于当前区间内？
对答案没有影响的点，就让他烂在堆里。
这个题也可以这么做。只需要记录一下每个花的编号。
处理的时候是需要看是否被删除就可以了。
#include<cstdio>
#include<algorithm>
#include<queue>
#include<iostream>
using std::priority_queue;
const int maxn=1001000;
struct node
{
int p;
int C;
int W;
node(int a=0,int b=0,int c=0){ p=a;C=b;W=c; }
bool operator < (const node &a )const
{
return C>a.C;
}
};
priority_queue<node>Max;
priority_queue<node>Min;
bool vis[maxn],alive[maxn];
int main()
{
int opt,c,w,tot=0;
while(true)
{
tot++;
scanf("%d",&opt);
if(opt==1)
{
scanf("%d%d",&w,&c);
if(vis[c]) continue;
vis[c]=true;
alive[tot]=true;
node pas(tot,c,w);
Min.push(pas);
pas.C*=-1;Max.push(pas);
}
if(opt==2)
{
if(Max.empty()) continue;
node pas=Max.top(); Max.pop();
while(!alive[pas.p]&&!Max.empty())
{
pas=Max.top();
Max.pop();
}
if(!alive[pas.p]) continue;
pas.C*=-1;
alive[pas.p]=false;
vis[pas.C]=false;
}
if(opt==3)
{
if(Min.empty()) continue;
node pas=Min.top(); Min.pop();
while(!alive[pas.p]&&!Min.empty())
{
pas=Min.top();
Min.pop();
}
if(!alive[pas.p]) continue;
alive[pas.p]=false;
vis[pas.C]=false;
}
if(opt==-1)
break;
}
int totC=0,totW=0;
while(!Min.empty())
{
node pas=Min.top();
Min.pop();
if(!alive[pas.p]) continue;
totC+=pas.C;
totW+=pas.W;
}
printf("%d %d",totW,totC);
}