atcoder square869120Contest#3 F 寿司

省选round1的时候dalao的推荐——atcoder的题目码量不大，但很巧妙，题目比较难找，挂个链冷静一下：http://s8pc-3.contest.atcoder.jp/tasks/s8pc_3_f

还行吧。。。

好久没写标记下传的线段树了（这次一写就是个双标记）居然能一遍写对核心代码（没开longlongRE了一发，改longlong就A了）

因为本来都是0，就好处理了

对于这道题我的理解是灌水（水泥）：每次在a的地方灌b体积的水，如果平就往左灌

感性理解得到单调性（数学归纳可证），而且被灌的地方分成三个阶段：先填平，再竖直向上涨，最后在左边的一段填1

二分填到哪里位置，然后直接（用线段树）模拟就可以了，复杂度两个log

 #include <bits/stdc++.h>

 #define sum(x,y) que(1,1,n,x,y)

 #define change(x,y,z) chan(1,1,n,x,y,z)

 #define add(x,y,z) Plus(1,1,n,x,y,z)

 #define mid (l+r>>1)

 using namespace std;

 long long sum[],fg[],ad[];

 long long n,m,a,b;

 void down(int now,int l,int r)

 {

     if(fg[now])

     {

         fg[now]+=ad[now];

         fg[now<<]=fg[now];

         fg[now<<|]=fg[now];

         ad[now]=ad[now<<]=ad[now<<|]=fg[now]=;

         sum[now<<]=fg[now<<]*(mid-l+);

         sum[now<<|]=fg[now<<|]*(r-mid);

     }

     if(ad[now])

     {

         ad[now<<]+=ad[now];

         ad[now<<|]+=ad[now];

         sum[now<<]+=ad[now]*(mid-l+);

         sum[now<<|]+=ad[now]*(r-mid);

         ad[now]=;

     }

 }

 void updata(int now)

 {

     sum[now]=sum[now<<]+sum[now<<|];

 }

 void chan(int now,int l,int r,int x,int y,long long z)

 {

     if(l==x && r==y)

     {

         fg[now]=z;

         ad[now]=;

         sum[now]=z*(r-l+);

         return;

     }

     down(now,l,r);

     if(x<=mid)

         chan(now<<,l,mid,x,min(mid,y),z);

     if(y>mid)

         chan(now<<|,mid+,r,max(mid+,x),y,z);

     updata(now);

 }

 void Plus(int now,int l,int r,int x,int y,long long z)

 {

     if(l==x && r==y)

     {

         ad[now]+=z;

         sum[now]+=z*(r-l+);

         return;

     }

     down(now,l,r);

     if(x<=mid)

         Plus(now<<,l,mid,x,min(mid,y),z);

     if(y>mid)

         Plus(now<<|,mid+,r,max(mid+,x),y,z);

     updata(now);

 }

 long long que(int now,int l,int r,int x,int y)

 {

     if(l==x && r==y)

         return sum[now];

     down(now,l,r);

     long long ret=;

     if(x<=mid)

         ret+=que(now<<,l,mid,x,min(y,mid));

     if(y>mid)

         ret+=que(now<<|,mid+,r,max(x,mid+),y);

     return ret;

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;i++)

     {

         scanf("%d%lld",&a,&b);

         int l=,r=a;

         for(;l<r;)

             if(sum(mid,mid)*(a-mid+)-sum(mid,a)<=b)

                 r=mid;

             else

                 l=mid+;

         b-=sum(l,l)*(a-l+)-sum(l,a);

         change(l,a,sum(l,l));

         add(l,a,b/(a-l+));

         if(b%(a-l+))

         add(l,l+b%(a-l+)-,);

     }

     for(int i=;i<=n;i++)

         printf("%lld\n",sum(i,i));

     return ;

 }

巴特西

atcoder square869120Contest#3 F 寿司

最新文章

热门文章