注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

工厂(factory)  

2016-05-20 14:12:07|  分类: 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

问题描述

小明的叔叔是一家工厂的厂长。叔叔的工厂有n个车间,编号为1n

管理工厂是很麻烦的事情,特别是在多次调整机器以及员工之后,统计总生产量更是难事。

i个车间在刚开始的时候机器生产力为ai,有bi个员工,那么这个车间的生产力就为ai*bi

工厂的总生产力定义为所有车间的生产力之和。

接下来的m天,每天叔叔就会调整一段区间的车间。

有两种调整:

第一种,是对于一段区间[l,r]的每一个车间重新分配每个车间的工人数为x

第二种,是对于一段区间[l,r]的每一个车间增加机器生产力x

现在,小明的叔叔想知道每天调整之后工厂的生产量变为多少。

输入格式

第一行两个整数nm,表示车场数以及天数。

接下来n行,每行描述一个车间。

i+1行描述第i个车间,包括两个整数aibi,意义如题目所述。

接下来m行,每一行表示一个修改操作。

Set l r x 表示对于一段区间[l,r]的每一个车间重新分配每个车间的工人数为x

Add l r x 表示对于一段区间[l,r]的每一个车间增加机器生产力x

输出格式

输出m行。

i行表示第i天调整后,工厂的总生产力。


===============================================

    线段树的经典应用。

    节点记录总人数,总机器生产力,总生产力,一个布尔变量标记人数有没有覆盖,一个标记增量。

    可分两部分讲。

    第一:更改一点

        Set时,将这段的人数全部变为x的话。

        {

            标记被覆盖

            总人数设定为x*此区间的车间数

            总生产力为总人数设定为x*此区间的车间数( x*a1+x*a2+x*a3+...+x*an=x*sum(a1~an) )

        }

        Add时,将这段的机器生产力加上x的话。

        {

            delta+=x;

            总机器生产力加上x*此区间的车间数

            总生产力为总人数加上为x*总人数

            ( b1(a1+x)+b2(a2+x)+...+bn(an+x)=b1*a1+a2*b2+...+bn*an+sum(b1~bn)*x )

        }

    第二、当前节点分封给子节点

        1,若这个节点被覆盖(人数都为 (总人数/此区间的车间数) )

         { 相当于Set子节点x,取消标记 }

        2,delta>0

         { 相当于Add子节点x,delta=0 }

==============================================

#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstdio>

#define Set(h,x) { h.ff=1; h.b=x*h.nu; h.sum=x*h.a; }
#define Add(h,x) { h.de+=x; h.a+=x*h.nu; h.sum+=x*h.b; }

using namespace std;

const int ML=100000;

struct Tnode {
int ll,rr,lc,rc,ff,nu;
long long sum,a,b,de;

void FZ(int le,int ri)
{
ll=le; rr=ri; nu=rr-ll+1;
sum=a=b=de=ff=0;
}
}f[ML*10];

int tp;

inline int Push(int le,int ri) {
f[tp++].FZ(le,ri);
return tp-1;
}

inline int Build(int le,int ri) {
int np=Push(le,ri);

if (le<ri)
{
int mid=(le+ri)>>1;

f[np].lc=Build(le,mid);
f[np].rc=Build(mid+1,ri);
}

return np;
}

int le,ri,x,ch;

void Updata1(int rp) {
Tnode &np=f[rp];

int tl=np.ll,tr=np.rr;

if (tr<le || tl>ri) return;

if (le<=tl && tr<=ri) { Add(np,x); return; } //更改

if (tl<tr)
{
Tnode &tlc=f[np.lc],&trc=f[np.rc];
/*===================分封====================*/
if (np.de>0)
{ Add(tlc,np.de); Add(trc,np.de); np.de=0; }

if (np.ff==1)
{
long long bx=np.b/np.nu;

if (np.ff) Set(tlc,bx);
if (np.ff) Set(trc,bx);

np.ff=0;
}
/*===========================================*/
Updata1(np.lc); Updata1(np.rc);

np.a=tlc.a+trc.a; np.sum=tlc.sum+trc.sum;
}
}

void Updata2(int rp) {
Tnode &np=f[rp];

int tl=np.ll,tr=np.rr;

if (tr<le || tl>ri) return;

if (le<=tl && tr<=ri) { Set(np,x); return; } //更改

if (tl<tr)
{
Tnode &tlc=f[np.lc],&trc=f[np.rc];
/*=====================分封==================*/
if (np.de>0)
{ Add(tlc,np.de); Add(trc,np.de); np.de=0; }

if (np.ff==1)
{
long long bx=np.b/np.nu;

if (np.ff) Set(tlc,bx);
if (np.ff) Set(trc,bx);

np.ff=0;
}
/*===========================================*/
Updata2(np.lc); Updata2(np.rc);

np.b=tlc.b+trc.b; np.sum=tlc.sum+trc.sum;
}
}

int main() {
ios::sync_with_stdio(false);

freopen("factory.in","r",stdin);
freopen("factory.out","w",stdout);

int n,m; cin>>n>>m;

int root=Build(1,n);

for (int i=1; i<=n; i++)
{
int aa,bb; cin>>aa>>bb;

le=ri=i; x=aa; Updata1(root);
le=ri=i; x=bb; Updata2(root);
}

for ( ; m>0; m--)
{
string st;

cin>>st>>le>>ri>>x;

if (st=="Set") Updata2(root); else Updata1(root);

cout<<f[root].sum<<endl;
}

return 0;
}


  评论这张
 
阅读(21)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018