bzoj1112 [POI2008]砖块Klo-白红宇

bzoj1112 [POI2008]砖块Klo

阅读量：6918 次

发布时间：2019-06-27

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

分析

通过小学数学我们可以知道对于k个数，我们取它们的中位数x时可以使答案最优。所以我们枚举每一个连续的长度为k的区间，用treap维护，求出所有数都变成x的花费。注意在这里treap还需要记录它的子树的值的和以便最后计算答案的时候使用。具体实现见代码。记得开long long。

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;const long long inf = 1e13+7;long long siz[110000],sum[110000],son[2][110000],a[110000],rd[110000];long long n,m,cnt,root,b[110000];inline void up(long long x){ siz[x]=siz[son[0][x]]+siz[son[1][x]]+1; sum[x]=sum[son[0][x]]+sum[son[1][x]]+a[x];}inline void rot(long long &rt,long long p){ long long t=son[p][rt]; son[p][rt]=son[!p][t],son[!p][t]=rt;up(rt),up(t);rt=t;} inline void ins(long long &rt,long long x){ if(!rt){rt=++cnt;sum[rt]=x;siz[rt]=1;a[rt]=x;rd[rt]=rand();return;} siz[rt]++; sum[rt]+=x; if(x<=a[rt]){ins(son[0][rt],x);if(rd[son[0][rt]]
                   
                    rd[son[1][rt]]){rot(rt,1);del(son[0][rt],x);} else {rot(rt,0);del(son[1][rt],x);} up(rt);return; } if(a[rt]>x)del(son[0][rt],x);else del(son[1][rt],x);up(rt);}long long res1,res2,s1,s2;inline long long fk(long long rt,long long k){ if(siz[son[0][rt]]==k-1){ s1+=siz[son[0][rt]],s2+=siz[son[1][rt]]; res1+=sum[son[0][rt]],res2+=sum[son[1][rt]];return a[rt]; } if(siz[son[0][rt]]>=k){ s2+=siz[son[1][rt]]+1,res2+=sum[son[1][rt]]+a[rt]; return fk(son[0][rt],k); }else { s1+=siz[son[0][rt]]+1,res1+=sum[son[0][rt]]+a[rt]; return fk(son[1][rt],k-1-siz[son[0][rt]]); }}inline long long getans(){ res1=res2=s1=s2=0; long long x=fk(root,(m-1)/2+1); return res2-s2*x+s1*x-res1;}int main(){ srand(time(0)+20021023); long long i,j,k,ans=inf; scanf("%lld%lld",&n,&m); for(i=1;i<=n;i++)scanf("%lld",&b[i]); for(i=1;i

转载于:https://www.cnblogs.com/yzxverygood/p/9506634.html

你可能感兴趣的文章