频道栏目
首页 > 程序开发 > Web开发 > PHP教程 > PHP应用 > 代码收藏 > 正文
hdu 4037 Development Value(线段树维护数学公式)
2016-01-07 14:15:52           
收藏   我要投稿

Development Value

Time Limit: 5000/3000 MS (Java/Others)Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 609Accepted Submission(s): 118



Problem Description

StarCraft 2 (SC2) is a famous game. More and more people fall in love with this game.

\

As a crazy fan of SC2, Ahua (flower fairy) play it day and night. Recently, he found that the most important part of being a top player of SC2 is economic development, which means you should get as much mine as possible by training SCVs (space construction vehicle) to collect mine. Train a SCV at ith second costs Ci units of mine. After training, this SCV can collect Di units of mine each second. Training a SCV needs one second of time.

Based on that, he composes a formula to evaluate the development in a time span from xth second to yth second. Assume at xth second, Ahua has no SCV and mine. He trains one SCV at each second during xth second and yth second (the mount of mine can be negative, so that he always can train SCV). Each SCV will collect some amount of mines for Ahua in each second after it was trained. At ith second Ahua has Mi units of mine in total. The development value is defined as sum(Mi) (x ≤ i ≤ y). Now he asks you to help him calculate the development value. To make it more interesting, Ahua can apply following operations:

Cost x y z: the cost of training a SCV between xth second to yth second will increase by z units of mine. i.e. Ci for x ≤ i ≤ y will increase by z.

Collect x y z: each SCV trained between xth second and yth second can collect z more mines every second after it has been trained. i.e. Di for x ≤ i ≤ y will increase by z.

Query x y: output the development value between xth second and yth second.

 


Input

First line of the input is a single integer T (T ≤ 10), indicates there are T test cases.
For each test case, the first line is an integer N (1 ≤ N ≤ 100000), means the maximum time you should deal with.

Following N lines, each contain two integers Ci and Di (0 ≤ Ci, Di ≤ 100000), the cost and collect speed of SCV training in ith second initially as described above.

The next line is an integer Q (1 ≤ Q ≤ 10000), the number of operations you should deal with. Then Q lines followed, each line will be “Cost x y z”, "Collect x y z” or “Query x y”.
1 ≤ x ≤ y ≤ N, 0 ≤ z ≤ 100000

 


Output

For each test case, first output “Case k: “ in a single line, k is the number of the test case, from 1 to T. Then for each "Q x y", you should output a single line contains the answer mod 20110911.

 


Sample Input


1 5 1 3 2 3 3 1 2 2 3 3 5 Query 1 3 Cost 2 2 1 Query 1 3 Collect 1 1 5 Query 1 3

 


Sample Output


Case 1: 2 0 15

 


Source

The 36th ACM/ICPC Asia Regional Chengdu Site —— Online Contest

 


Recommend

lcy|We have carefully selected several similar problems for you:40384036403940324033

 

题意:

有一个游戏。里面要造矿兵。在第i秒造矿兵需要花费c[i]。然后之后的时间每秒该矿兵都会采d[i]的矿。然后询问。从x秒到y秒。每秒造一个矿兵.(在x秒的时候矿兵和矿都为0.但是矿可以为负数)。然后定义了一个mi。表示第i秒时的总矿数。然后要你输出.Σmi(x<=i<=y)。

 

思路:

先推公式。

1,考虑花费
时刻j 从x时刻到j时刻造农民的总花费
x C(x)
x+1 C(x)+C(x+1)
x+2 C(x)+C(x+1)+C(x+2)
......
y C(x)+C(x+1)+...+C(y)
对第二栏求和,每一列是C(i)*(y-i+1),再对这个从x到y求和,得sigma(C(i)*(y+1-i))
分成两项(y+1)*sigma(C(i))-sigma(C(i)*i)

2,考虑采矿
对于i时刻被造出的农民,到j时刻总共采的矿数是D(i)*(j-i),对这个从x到j求和就是j时刻之前造的农民到j时刻为止总共采的矿数,即sigma(D(i)*(j-i))(对i从x到j求和),再对j从x到y求和就是答案。但是这个形式的求和式不适合用线段树维护,做些变形:
时刻j sigma(D(i)*(j-i))
x D(x)*0
x+1 D(x)*1+D(x+1)*0
x+2 D(x)*2+D(x+1)*1+D(x+2)*0
......
y D(x)*(y-x)+D(x+1)*(y-x-1)+......+D(y-1)*1+D(y)*0
对第二栏求和,每列是D(i)*(y-i)*(y-i+1)/2,再对这个从x到y求和,sigma(D(i)*(y-i)*(y-i+1)/2).
把和式拆成几项方便维护:1/2*( y*(y+1)sigma(D(i)) - (2*y+1)sigma(D(i)*i) + sigma(D(i)*i^2))

然后最后的答案就是采矿-花费。

然后只需要用一颗线段树来维护。

sigma(ci),sigma(i*ci),sigma(di),sigma(i*di),sigma(i*i*di).

然后按一般的更新查询就完了。

对于除二取模的问题。

(1)模数乘2,所有中间过程直接取模,最后得数/2
(2)直接取模,最后答案是ret,如果ret是偶数,答案是ret/2,如果是奇数,答案是(ret + mod) / 2

详细见代码:

 

[cpp] view plaincopy在CODE上查看代码片派生到我的代码片

 

  1. #include<algorithm>  
  2. #include<iostream>  
  3. #include<string.h>  
  4. #include<stdio.h>  
  5. using namespace std;  
  6. const int INF=0x3f3f3f3f;  
  7. const int maxn=100010;  
  8. typedef long long ll;  
  9. const ll mod=20110911*2;  
  10. #define lson L,mid,ls  
  11. #define rson mid+1,R,rs  
  12. ll sm[maxn],ss[maxn],sc[maxn<<2],sd[maxn<<2],siid[maxn<<2];  
  13. ll sic[maxn<<2],sid[maxn<<2],ac[maxn<<2],ad[maxn<<2];  
  14. ll asc,aic,asd,aid,aiid;  
  15. void addc(int L,int R,int rt,ll d)  
  16. {  
  17.     ac[rt]=(ac[rt]+d)%mod;  
  18.     sc[rt]=(sc[rt]+(R-L+1)*d)%mod;  
  19.     sic[rt]=(sic[rt]+(sm[R]-sm[L-1])*d)%mod;  
  20. }  
  21. void addd(int L,int R,int rt,ll d)  
  22. {  
  23.     ad[rt]=(ad[rt]+d)%mod;  
  24.     sd[rt]=(sd[rt]+(R-L+1)*d)%mod;  
  25.     sid[rt]=(sid[rt]+(sm[R]-sm[L-1])*d)%mod;  
  26.     siid[rt]=(siid[rt]+(ss[R]-ss[L-1])*d)%mod;  
  27. }  
  28. void PushDown(int L,int R,int rt)  
  29. {  
  30.     int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;  
  31.     if(ad[rt])  
  32.         addd(lson,ad[rt]),addd(rson,ad[rt]),ad[rt]=0;  
  33.     if(ac[rt])  
  34.         addc(lson,ac[rt]),addc(rson,ac[rt]),ac[rt]=0;  
  35. }  
  36. void PushUp(int rt)  
  37. {  
  38.     int ls=rt<<1,rs=ls|1;  
  39.     sc[rt]=(sc[ls]+sc[rs])%mod;  
  40.     sic[rt]=(sic[ls]+sic[rs])%mod;  
  41.     sd[rt]=(sd[ls]+sd[rs])%mod;  
  42.     sid[rt]=(sid[ls]+sid[rs])%mod;  
  43.     siid[rt]=(siid[ls]+siid[rs])%mod;  
  44. }  
  45. void build(int L,int R,int rt)  
  46. {  
  47.     ac[rt]=ad[rt]=0;  
  48.     if(L==R)  
  49.     {  
  50.         scanf("%I64d%I64d",&sc[rt],&sd[rt]);  
  51.         sic[rt]=(L*sc[rt])%mod;  
  52.         sid[rt]=(L*sd[rt])%mod;  
  53.         siid[rt]=(sid[rt]*L)%mod;  
  54.         return;  
  55.     }  
  56.     int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;  
  57.     build(lson);  
  58.     build(rson);  
  59.     PushUp(rt);  
  60. }  
  61. void update(int L,int R,int rt,int l,int r,ll d,int op)  
  62. {  
  63.     if(l<=L&&R<=r)  
  64.     {  
  65.         if(op)  
  66.             addd(L,R,rt,d);  
  67.         else  
  68.             addc(L,R,rt,d);  
  69.         return;  
  70.     }  
  71.     int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;  
  72.     PushDown(L,R,rt);  
  73.     if(l<=mid)  
  74.         update(lson,l,r,d,op);  
  75.     if(r>mid)  
  76.         update(rson,l,r,d,op);  
  77.     PushUp(rt);  
  78.     //printf("%d->%d sc")  
  79. }  
  80. void qu(int L,int R,int rt,int l,int r)  
  81. {  
  82.     if(l<=L&&R<=r)  
  83.     {  
  84.         asc=(asc+sc[rt])%mod;  
  85.         aic=(aic+sic[rt])%mod;  
  86.         asd=(asd+sd[rt])%mod;  
  87.         aid=(aid+sid[rt])%mod;  
  88.         aiid=(aiid+siid[rt])%mod;  
  89.         return;  
  90.     }  
  91.     int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;  
  92.     PushDown(L,R,rt);  
  93.     if(l<=mid)  
  94.         qu(lson,l,r);  
  95.     if(r>mid)  
  96.         qu(rson,l,r);  
  97.     PushUp(rt);  
  98. }  
  99. int main()  
  100. {  
  101.     int i,t,n,q,x,y,z,cas=1;  
  102.     char cmd[20];  
  103.     for(i=1;i<maxn;i++)  
  104.     {  
  105.         sm[i]=(sm[i-1]+i)%mod;  
  106.         ss[i]=(ss[i-1]+(ll)i*i)%mod;  
  107.     }  
  108.     scanf("%d",&t);  
  109.     while(t--)  
  110.     {  
  111.         scanf("%d",&n);  
  112.         build(1,n,1);  
  113.         scanf("%d",&q);  
  114.         printf("Case %d:\n",cas++);  
  115.         while(q--)  
  116.         {  
  117.             asc=aic=asd=aid=aiid=0;  
  118.             scanf("%s%d%d",cmd,&x,&y);  
  119.             if(cmd[0]!='Q')  
  120.                 scanf("%d",&z);  
  121.             if(cmd[2]=='s')  
  122.                 update(1,n,1,x,y,z,0);  
  123.             else if(cmd[2]=='l')  
  124.                 update(1,n,1,x,y,z,1);  
  125.             else  
  126.             {  
  127.                 qu(1,n,1,x,y);  
  128.                 ll ans=((ll)y*(y+1)*asd-(2*y+1)*aid+aiid)%mod;  
  129.                 ans-=2*((y+1)*asc-aic);  
  130.                 ans%=mod;  
  131.                 ans=(ans+mod)%mod;  
  132.                 //printf("asc %I64d aic %I64d asd %I64d aid %I64d aiid %I64d\n",asc,aic,asd,aid,aiid);  
  133.                 printf("%I64d\n",ans/2);  
  134.             }  
  135.         }  
  136.     }  
  137.     return 0;  
  138. }  
点击复制链接 与好友分享!回本站首页
相关TAG标签 线段 公式 数学
上一篇:iOS 单例模式
下一篇:SDL2源代码分析7:显示(SDL_RenderPresent())
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站