营业额统计 Treap TYVJ1185-白红宇

营业额统计 Treap TYVJ1185

阅读量：6568 次

发布时间：2019-06-24

本文共 1194 字，大约阅读时间需要 3 分钟。

题目连接：

相关知识：平衡树

题目不再赘述，比较简单的平衡树入门题，而且不用删除查询操作，只要直接要用数据结构模块就可以，在插入的时候更新答案，因为插入也是慢慢向着插入数值大小走的。

View Code

#include
      
        #include
       
         #include
        
          #include
         
           #include
          
            using namespace std; #define INF 20000000 #define MaxN 40000 struct treap {
    int x,p,l,r;        }a[MaxN]; int n,tot,ans,root,Max; void turnright(int &t) {
    int t1=a[t].l;      a[t].l=a[t1].r;      a[t1].r=t;      t=t1;      } void turnleft(int &t) {
    int t1=a[t].r;      a[t].r=a[t1].l;      a[t1].l=t;      t=t1;      } void insert(int &t,int x) {
    if (t==0)      {
                  tot++;               t=tot;               a[t].l=0;               a[t].r=0;               a[t].x=x;               a[t].p=rand();               } else      {
    if (abs(a[t].x-x)
           
            a[t].x) { insert(a[t].r,x); if (a[a[t].r].p < a[t].p) turnleft(t); } } } int main() { int x; scanf("%d",&n); for (int i=1;i<=n;i++) { Max=INF; scanf("%d",&x); insert(root,x); if (i==1) ans+=x; else ans+=Max; } printf("%d\n",ans); // system("pause"); return 0; }