splay专题复习――bzoj 3224 & 1862 & 1503 题解 - c++编程基础

然后告诉他答案。好了，现在你已经对我的工作了解不少了。正如你猜的那样，我想请你编一个工资统计程序。怎么样，不是很困难吧？

Input

Output

输出文件的行数为F命令的条数加一。对于每条F命令，你的程序要输出一行，仅包含一个整数，为当前工资第k多的员工所拿的工资数，如果k大于目前员工的数目，则输出-1。输出文件的最后一行包含一个整数，为离开公司的员工的总数。

Sample Input

9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2

Sample Output

10
20
-1
2

HINT

I命令的条数不超过100000 A命令和S命令的总条数不超过100 F命令的条数不超过100000 每次工资调整的调整量不超过1000 新员工的工资不超过100000

【分析】这道题说起来也是辛酸的历史。首先谈谈如何处理增加和减少工资的问题。我傻叉地开了一个f数组。每次判断一个splay中的结点时，他的实际权值是a[x]+f[q]-f[b[x]-1]。其中a[x]是刚进来的工资，q是现在这个询问，b[x]是x刚进来的时候所在的询问。（有点类似于前缀和的思想）后来网上看了一下，可以直接开一个数组记录~~~

再说明一下如何删除。（真是爽！）假设要删除

【代码】

/**************************************************************
    Problem: 1503
    User: jiangshibiao
    Language: C++
    Result: Accepted
    Time:1372 ms
    Memory:16040 kb
****************************************************************/
 
#include
             
              
#define N 300005
using namespace std;
int son[N][3],num[N][3],f[N],a[N],b[N],T[N];
char Str[N][12],opt[12],s[5];
int k,i,root,node,P,Min,q,Q,l,n,j,PRE,away;
void Rotate(int x,int w)
{
  int y=f[x],z=f[y];
  son[y][3-w]=son[x][w];
  if (son[x][w]) f[son[x][w]]=y;
  f[x]=z;
  num[y][3-w]=num[x][w];
  num[x][w]+=num[y][w]+1;
  if (z)
    if (son[z][1]==y) son[z][1]=x;else son[z][2]=x;
  f[y]=x;son[x][w]=y;
}
void splay(int x)
{
  while (f[x])
  {
    int y=f[x],z=f[y];
    if (!z)
    {
      if (son[y][1]==x) Rotate(x,2);else Rotate(x,1);
      continue;
    }
    if (son[z][1]==y)
    {
      if (son[y][1]==x) Rotate(y,2),Rotate(x,2);
      else Rotate(x,1),Rotate(x,2);
    }
    else
    {
      if (son[y][2]==x) Rotate(y,1),Rotate(x,1);
      else Rotate(x,2),Rotate(x,1);
    }
  }
  root=x;
}
void insert(int x)
{
  if (!x){a[++node]=P;b[node]=q;return;}
  if (P
              
               =P) return Ask(son[x][2],now); else return Ask(son[x][1],temp+1); } int main() { scanf("%d%d",&Q,&Min); for (q=1;q<=Q;q++) { scanf("%s%d",s,&P);T[q]=T[q-1]; if (s[0]=='I') { if (P

splay专题复习――bzoj 3224 & 1862 & 1503 题解(三)

Input

Output

Sample Input

Sample Output

HINT