Ice-cream Tycoon9(线段树）

线段树的一些基本应用，就是函数写了很多，有点繁琐。

以每个物品的单价建树，刚开始写了个裸的想水过去直接MLE了，然后又离散化了下。

离散化单价后建树，lz数组用来清零，s数组保存结点所含物品个数，co数组保存结点所含物品的所有花费，以找第k大的方式找到第n个物品所在的结点位置i，求出前i-1个结点所包含的物品数量m以及花费ts,那么这n个物品的总花费就为sum = ts+(n-m)*pri[i] pri表示i离散前的价格，sum与给出的t进行比较得出答案。若可以卖出，则把1--(i-1)清零，把i位置数量减少n-m。

不小心把t也放去离散化了，re 了两次。。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 100010

 #define LL __int64

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 LL s[N<<],lz[N<<],co[N<<];

 int po[N*],a[N],pp[N];

 struct node

 {

     int x;

     LL y;

     char s[];

 }p[N];

 void up(int w)

 {

     s[w] = s[w<<]+s[w<<|];

     co[w] = co[w<<]+co[w<<|];

 }

 void down(int w,int m)

 {

     if(lz[w]!=-)

     {

         lz[w<<] = lz[w<<|] = lz[w];

         s[w<<] = co[w<<] = ;

         s[w<<|] = co[w<<|] = ;

         lz[w] = -;

     }

 }

 void build(int l,int r,int w)

 {

     lz[w] = -;

     if(l==r)

     {

         s[w] = co[w] = ;

         return ;

     }

     int m = (l+r)>>;

     build(l,m,w<<);

     build(m+,r,w<<|);

     up(w);

 }

 void update(int a,int b,int l,int r,int w)

 {

     if(a<=l&&b>=r)

     {

         s[w]  = ;

         co[w] = ;

         lz[w] = ;

         return ;

     }

     down(w,r-l+);

     int m = (l+r)>>;

     if(a<=m)

     update(a,b,l,m,w<<);

     if(b>m)

     update(a,b,m+,r,w<<|);

     up(w);

 }

 void upset(int p,int d,int l,int r,int w)

 {

     if(l==r)

     {

         s[w]+=d;

         co[w]+=(LL)d*pp[l];

         return ;

     }

     down(w,r-l+);

     int m = (l+r)>>;

     if(p<=m) upset(p,d,l,m,w<<);

     else upset(p,d,m+,r,w<<|);

     up(w);

 }

 LL query(int a,int b,int l,int r,int w)

 {

     if(a<=l&&b>=r) return s[w];

     int m = (l+r)>>;

     LL res = ;

     down(w,r-l+);

     if(a<=m) res+=query(a,b,l,m,w<<);

     if(b>m) res+=query(a,b,m+,r,w<<|);

     return res;

 }

 LL queryp(int a,int b,int l,int r,int w)

 {

     if(a<=l&&b>=r) return co[w];

     int m = (l+r)>>;

     LL res = ;

     down(w,r-l+);

     if(a<=m) res+=queryp(a,b,l,m,w<<);

     if(b>m) res+=queryp(a,b,m+,r,w<<|);

     return res;

 }

 int find(int k,int l,int r,int w)

 {

     if(l==r)

     {

         return l;

     }

     down(w,r-l+);

     int m = (l+r)>>;

     if(k<=s[w<<])

     return find(k,l,m,w<<);

     else return find(k-s[w<<],m+,r,w<<|);

 }

 int main()

 {

     int x,i,j=;

     LL y;

     int g = ;

     while(scanf("%s%d%I64d",p[j].s,&p[j].x,&p[j].y)!=EOF)

     {

         if(p[j].s[]=='A')

         a[j] = p[j].y;

         else a[j] = ;

         j++;

     }

     sort(a,a+j);

     //int o = 0;

     po[a[]] = ++g;

     pp[g] = a[];

     for(i =  ;i < j ; i++)

     if(a[i]!=a[i-])

     {

         po[a[i]] = ++g;

         pp[g] = a[i];

     }

     build(,g,);

     for(i =   ;i < j; i++)

     {

         x = p[i].x;

         if(p[i].s[]=='A')

         y = po[p[i].y];

         else y = p[i].y;

         if(p[i].s[]=='A')

         {

             upset(y,x,,g,);

         }

         else

         {

             if(s[]<x)

             {

                 puts("UNHAPPY");

                 continue;

             }

             int k = find(x,,g,);

             LL ts = ;

             if(k>)

             ts = query(,k-,,g,);

             LL tp = ;

             if(k>)

             tp = queryp(,k-,,g,);

             LL sum = tp+(x-ts)*pp[k];

            // printf("%I64d\n",sum);

             if(sum<=y)

             {

                 puts("HAPPY");

                 if(k>)

                 update(,k-,,g,);

                 upset(k,ts-x,,g,);

             }

             else puts("UNHAPPY");

         }

     }

     return ;

 }

巴特西

Ice-cream Tycoon9(线段树）

最新文章

热门文章