L3-002. 堆栈
大家都知道“堆栈”是一种“先进后出”的线性结构，基本操作有“入栈”（将新元素插入栈顶）和“出栈”（将栈顶元素的值返回并从堆栈中将其删除）。现请你实现一种特殊的堆栈，它多了一种操作叫“查中值”，即返回堆栈中所有元素的中值。对于N个元素，若N是偶数，则中值定义为第N/2个最小元；若N是奇数，则中值定义为第(N+1)/2个最小元。
输入格式：
输入第一行给出正整数N（<= 105）。随后N行，每行给出一个操作指令，为下列3种指令之一：
Push key
Pop
PeekMedian
其中Push表示入栈，key是不超过105的正整数；Pop表示出栈；PeekMedian表示查中值。
输出格式：
对每个入栈指令，将key入栈，并不输出任何信息。对每个出栈或查中值的指令，在一行中打印相应的返回结果。若指令非法，就打印“Invalid”。
输入样例：
17
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop
输出样例：
Invalid
Invalid
3
2
2
1
2
4
4
5
3
Invalid
题目链接：PAT L3-002
以前是看别人代码过的，并不懂其中的意思，又把这题拿出来做了一下，线段树的话应该是只能查询当前所含范围1~n内的第K大值，已经定死就是build的那个范围。
做法就是对已出现的值的范围建树，然后每一次更新就把这个值对应的叶子节点++或--，用cnt记录当前区间内出现了几个数，这样一来查询就好办了，若左子树cnt大于等于k，则肯定在左子树，反之则在右子树，但此时就不是K了，因为k已经大于左子树的cnt了，就是说还剩下k-lson.cnt个数，比如我要查第10大，左边6个右边10个，一共14个数，那肯定就直接从右边开始数10-6个即右边的第4个。懂了这个就是一个裸的线段树单点更新查询稍微变化一下的题目了，用cin第二组会超时用scanf比较快
16.10.3更新
主席树入门之后试着用主席树的解法写了一下，push简单，pop怎么办呢？当然是把对应的cnt减1即可，因此更新函数参数中加一个delta表示到底是加1（push）还是减1（pop），然后用一个变量C记录弹出或压入栈的次数（即变化次数），此题根的范围S恒为root[1-1]即root[0]，一开始这里写成root[1]发现数据对不上，后来突然记起来主席树的区间范围是[L-1,R]因此要减1，E就可以用root[C]。然后就可以写了，PAT的数据比较弱不知道有没有存在问题，有问题的话可以直接回复一下：）。此外这题不用离散化，那对应的查询返回值直接就是答案了
普通线段树代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<bitset>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(x,y) memset(x,y,sizeof(x))
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
typedef pair<int,int> pii;
typedef long long LL;
const double PI=acos(-1.0);
const int N=1e5+10;
struct seg
{
int l,mid,r;
int cnt;
};
seg T[N<<2];
void pushup(int k)
{
T[k].cnt=T[LC(k)].cnt+T[RC(k)].cnt;
}
void build(int k,int l,int r)
{
T[k].l=l;
T[k].r=r;
T[k].mid=MID(l,r);
T[k].cnt=0;
if(l==r)
return ;
build(LC(k),l,T[k].mid);
build(RC(k),T[k].mid+1,r);
pushup(k);
}
void update(int k,int x,int val)
{
if(T[k].l==T[k].r&&T[k].l==x)
T[k].cnt+=val;
else
{
if(x<=T[k].mid)
update(LC(k),x,val);
else
update(RC(k),x,val);
pushup(k);
}
}
int query(int rt,int k)
{
if(T[rt].l==T[rt].r)
return T[rt].r;
else
{
if(k<=T[LC(rt)].cnt)
return query(LC(rt),k);
else
return query(RC(rt),k-T[LC(rt)].cnt);
}
}
int st[N];
int main(void)
{
int n,top,val;
char ops[15];
while (~scanf("%d",&n))
{
top=0;
build(1,1,N-5);
while (n--)
{
scanf("%s",ops);
if(ops[1]=='o')
{
if(!top)
puts("Invalid");
else
{
update(1,st[top-1],-1);
printf("%d\n",st[top-1]);
--top;
}
}
else if(ops[1]=='u')
{
scanf("%d",&val);
update(1,val,1);
st[top++]=val;
}
else if(ops[1]=='e')
{
if(!top)
puts("Invalid");
else
printf("%d\n",query(1,(top+1)>>1));
}
}
}
return 0;
}
主席树代码（注意查询的时候根范围是root[1-1]~root[C]）
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(x,y) memset(x,y,sizeof(x))
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
typedef pair<int,int> pii;
typedef long long LL;
const double PI=acos(-1.0);
const int N=1e5+7;
struct seg
{
int lson,rson;
int cnt;
};
seg T[N*20];
vector<int>pos;
int tot,root[N];
void init()
{
tot=0;
CLR(root,0);
pos.clear();
}
void build(int &cur,const int &l,const int &r)
{
cur=++tot;
T[cur].cnt=0;
if(l==r)
return ;
int mid=MID(l,r);
build(T[cur].lson,l,mid);
build(T[cur].rson,mid+1,r);
}
void update(int &cur,const int &ori,const int &l,const int &r,const int &val,const int &delta)
{
cur=++tot;
T[cur]=T[ori];
T[cur].cnt+=delta;
if(l==r)
return ;
int mid=MID(l,r);
if(val<=mid)
update(T[cur].lson,T[ori].lson,l,mid,val,delta);
else
update(T[cur].rson,T[ori].rson,mid+1,r,val,delta);
}
int query(const int &S,const int &E,const int &l,const int &r,const int &k)
{
if(l==r)
return l;
int mid=MID(l,r);
int cnt=T[T[E].lson].cnt-T[T[S].lson].cnt;
if(k<=cnt)
return query(T[S].lson,T[E].lson,l,mid,k);
else
return query(T[S].rson,T[E].rson,mid+1,r,k-cnt);
}
int main(void)
{
int n,val;
char ops[12];
while (~scanf("%d",&n))
{
init();
int C=0;
int SZ=N-5;
build(root[C],1,SZ);
while (n--)
{
scanf("%s",ops);
if(ops[1]=='o')
{
if(pos.empty())
puts("Invalid");
else
{
val=pos.back();
pos.pop_back();
++C;
update(root[C],root[C-1],1,SZ,val,-1);
printf("%d\n",val);
}
}
else if(ops[1]=='u')
{
scanf("%d",&val);
pos.push_back(val);
++C;
update(root[C],root[C-1],1,SZ,val,1);
}
else
{
int T=(int)pos.size();
if(!T)
puts("Invalid");
else
{
int indx=query(root[1-1],root[C],1,SZ,(T+1)>>1);//注意范围是L-1~R，因此是从root[0]开始
//这里直接输出下标，因为没有离散化的时候是直接用数值更新的
printf("%d\n",indx);
}
}
}
}
return 0;
}