首页 > > 程序设计 > C/C++ >

洛谷 P1438 无聊的数列

2018-06-17 21:38:03来源：未知阅读 ()

https://www.luogu.org/problemnew/show/1438

lazytag记录一下某个区间需要加的等差数列的首项和公差。由于区间长度已知（r-l+1），仅由此就可以推出这个区间每一个数要加上的数。

可以发现两个等差数列每一项相加，得到的还是等差数列，而且是首项和公差分别相加。

对于区间的分解（标记的下传），要用等差数列通项/求和/求项数公式手算一下。由父区间应加上的首项和公差可以推出其子区间应加上的首项和公差，大概就是公差不变，两个子区间的首项分别是父区间的首项和父区间数列的某一项（要推一下的）。

其实可以改成区间查询的。

由于只需要单点查，有更简单的方法：只记录原数列的差分数列。

时间长原因：手算错太多次/太慢

 1 #include<cstdio>
 2 #include<iostream>
 3 #define ls (num<<1)
 4 #define rs (num<<1|1)
 5 #define mid ((l+r)>>1)
 6 typedef long long LL;
 7 LL t[800100],kk[800100],dd[800100],a[200100];
 8 LL L,R,k,d,n,m;
 9 void pushdown(LL l,LL r,LL num)
10 {
11     if(kk[num]!=0||dd[num]!=0)
12     {
13         t[ls]+=((2*kk[num]+dd[num]*(mid-l))*(mid-l+1)/2);
14         t[rs]+=((2*kk[num]+dd[num]*(mid-l+1+r-l))*(r-mid)/2);
15         kk[ls]+=kk[num];
16         dd[ls]+=dd[num];
17         kk[rs]+=(kk[num]+dd[num]*(mid-l+1));
18         dd[rs]+=dd[num];
19         kk[num]=0;dd[num]=0;
20     }
21 }
22 void build(LL l,LL r,LL num)
23 {
24     if(l==r)
25     {
26         t[num]=a[l];
27         return;
28     }
29     build(l,mid,ls);
30     build(mid+1,r,rs);
31     t[num]=t[ls]+t[rs];
32 }
33 void change(LL l,LL r,LL num)
34 {
35     if(L<=l&&r<=R)
36     {
37         t[num]+=((2*(k+d*(l-L))+d*(r-l))*(r-l+1)/2);
38         kk[num]+=(k+d*(l-L));
39         dd[num]+=d;
40         return;
41     }
42     pushdown(l,r,num);
43     if(L<=mid)    change(l,mid,ls);
44     if(mid<R)        change(mid+1,r,rs);
45     t[num]=t[ls]+t[rs];
46 }
47 LL query(LL l,LL r,LL num)
48 {
49     if(L<=l&&r<=R)
50         return t[num];
51     pushdown(l,r,num);
52     LL ans=0;
53     if(L<=mid)    ans+=query(l,mid,ls);
54     if(mid<R)    ans+=query(mid+1,r,rs);
55     return ans;
56 }
57 int main()
58 {
59     LL i,tt;
60     scanf("%lld%lld",&n,&m);
61     for(i=1;i<=n;i++)
62         scanf("%lld",&a[i]);
63     build(1,n,1);
64     while(m--)
65     {
66         scanf("%lld",&tt);
67         if(tt==1)
68         {
69             scanf("%lld%lld%lld%lld",&L,&R,&k,&d);
70             change(1,n,1);
71         }
72         else
73         {
74             scanf("%lld",&L);R=L;
75             printf("%lld\n",query(1,n,1));
76         }
77     }
78     return 0;
79 }