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

ATHY LEO KAINE WALT MICK GRACE SANDY JACK TOM BOB
WALT MICK GRACE SANDY JACK TOM BOB ADAM DAM

【分析】我就不吐槽HN抄袭浙江的题目了。。这道题的坑爹之处是字符串的处理。如何判断一个字符串是否出现？哈希本来是个好选择，但是我生怕25万的数据会被卡，只好硬生生地开了一棵字母树。。

为了巩固splay，全是手码的，于是乎调了半天， rz。说一下如何查询。他要找排名从K开始的10个人，我就设L=K,R=K+9。那么我们只需在正常的查询（可参见之前的程序）里把一个固定的值改成一个范围~~

还有，开始我一直T，后来一气之下，在询问时也找了个点splay一下，然后瞬秒出解。没事多转转~~

【AC代码】

/**************************************************************
    Problem: 1862
    User: jiangshibiao
    Language: C++
    Result: Accepted
    Time:1148 ms
    Memory:50828 kb
****************************************************************/
 
#include
     
      
#include
      
        #define N 300005 using namespace std; int son[N][3],Num[N][3],f[N],a[N],b[N],trie[N][27],L[N],score[N],ans[N]; char Str[N][12],opt[12]; int k,i,num,add,now,flag,tree,root,node,left,right,tot,Q,l,n,j,PRE; 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; } inline void splay(int x) { int y; while (f[x]) { y=f[x]; if (!f[y]) { if (x==son[y][1]) Rotate(x,2);else Rotate(x,1);continue; } if (y==son[f[y]][1]) { if (x==son[y][1]) Rotate(y,2),Rotate(x,2); else Rotate(x,1),Rotate(x,2); } else { if (x==son[y][2]) Rotate(y,1),Rotate(x,1); else Rotate(x,2),Rotate(x,1); } } root=x; } inline void insert(int x,int num,int add) { if (!x) { root=++node; a[node]=add; b[node]=num; return; } if (add
       
        b[x]) { if (!son[x][1]) son[x][1]=++node,a[node]=add,b[node]=num,f[node]=x; else insert(son[x][1],num,add); Num[x][1]++; } else { if (!son[x][2]) son[x][2]=++node,a[node]=add,b[node]=num,f[node]=x; else insert(son[x][2],num,add); Num[x][2]++; } } inline void del(int x,int num,int add) { if (!x) return; if (add==a[x]&&num==b[x]) { splay(x); int find=son[x][1],temp=son[x][2]; if (!find&&!temp){root=0;return;} if (!find) {root=son[x][2];f[son[x][2]]=0;return;} if (!temp) {root=son[x][1];f[son[x][1]]=0;return;} while (son[find][2]) find=son[find][2]; f[son[x][1]]=0;splay(find);Num[find][2]+=Num[temp][1]+Num[temp][2]+1; son[find][2]=temp; f[temp]=find;root=find; return; } if (add
        
         b[x]) del(son[x][1],num,add); else del(son[x][2],num,add); } int walk(int k,int p) { if (p==l) {tree=k;return L[k] L[k]:L[k]=i;} if (trie[k][opt[p]-65]) return walk(trie[k][opt[p]-65],p+1); trie[k][opt[p]-65]=++tot;flag=0; return walk(tot,p+1); } int Kth(int x,int now) { if (!x) return 0; if (add==a[x]&&num==b[x]) { PRE=x; return now+1+Num[x][2]; } if (add
         
          b[x]) return Kth(son[x][1],now+Num[x][2]+1); return Kth(son[x][2],now); } void Ask(int x,int now) { if (!x) return; int temp=Num[x][2]+now; if (temp>=left) Ask(son[x][2],now); if (temp+1>=left&&temp+1<=right) { ans[++n]=b[x]; PRE=x; } if (temp+1
          
           ='0'&&opt[1]<='9') { k=0;n=0; for (j=1;j
           
            
 【BZOJ1503】
             
             
             
             1503: [NOI2004]郁闷的出纳员 Time Limit: 5 Sec Memory Limit: 64 MB
             
 Submit: 5542 Solved: 1968
             
 
             
            Description 
            OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。工资的频繁调整很让员工反感，尤其是集体扣除工资的时候，一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去，同样，每当公司招聘了一位新员工，我就得为他新建一个工资档案。老板经常到我这边来询问工资情况，他并不问具体某位员工的工资情况，而是问现在工资第k多的员工拿多少工资。每当这时，我就不得不对数万个员工进行一次漫长的排序，

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

1503: [NOI2004]郁闷的出纳员

Description