• 智乃酱的平方数列（线段树维护2次函数）

    想必你一定会用线段树维护等差数列吧？让我们来看看它的升级版。

    请你维护一个长度为5×10^5的数组，一开始数组中每个元素都为0，要求支持以下两个操作：

    1、区间[l,r]加自然数的平方数组，即al​+=1，al+1​+=4，al+2​+=9，al+3​+=16...ar​+=(r−l+1)∗(r−l+1)
    2、区间[l,r]查询区间和mod 10^9+7


     

    输入描述:

    第一行输入n,m,(1≤n,m≤5×105)n,m。
接下来m行，对于每行，先读入一个整数q。
当q的值为1时，还需读入两个整l,r,(1≤l≤r≤n)表示需要对区间[l,r]进行操作，让第一个元素加1，第二个元素加4，第三个元素加9以此类推。
当q的值为2时，还需读入两个整数l,r(1≤l≤r≤n)表示查询l到r的元素和

    输出描述:

    对于每一个q=2，输出一行一个非负整数，表示l到r的区间和mod 10^9+7。


     

    示例1

    输入

    4 4
2 1 4
1 1 4
1 3 4
2 1 4

    输出

    0
35

    示例2

    输入

    10 6
1 1 6
1 8 9
1 3 6
2 1 10
1 1 10
2 1 10

    输出

    126
511

    [l,r]添加平方数列

    对于任意位置x属于[l,r]

    增加的值应当是( x − ( l − 1 ) ) ^2

    展开 ：x^2   -  2(l-1)x  +(l-1)^2

    维护6个系数，分开来求

    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. #define int long long
    4. const int N=5e5+10;
    5. const int mod=1e9+7;
    6. int n,m;
    7. struct node
    8. {
    9.     int sum0,sum1,sum2,lz0,lz1,lz2;
    10. } t[N*4];
    11. void pushdown(int i,int l,int r)
    12. {
    13.     if(t[i].lz0)
    14.     {
    15.         int k=t[i].lz0;
    16.         int mid=(l+r)>>1;
    17.         t[i<<1].sum0+=k*(mid-l+1)%mod;
    18.         t[i<<1].sum0%=mod;
    19.         t[i<<1|1].sum0+=k*(r-mid)%mod;
    20.         t[i<<1|1].sum0%=mod;
    21.         t[i<<1].lz0+=k;
    22.         t[i<<1].lz0%=mod;
    23.         t[i<<1|1].lz0+=k;
    24.         t[i<<1|1].lz0%=mod;
    25.         t[i].lz0=0;
    26.     }
    27.     if(t[i].lz1)
    28.     {
    29.         int k=t[i].lz1;
    30.         int mid=(l+r)>>1;
    31.         t[i<<1].sum1+=k*((mid+l)*(mid-l+1)/2%mod)%mod;
    32.         t[i<<1].sum1%=mod;
    33.         t[i<<1|1].sum1+=k*((r+mid+1)*(r-mid)/2%mod)%mod;
    34.         t[i<<1|1].sum1%=mod;
    35.         t[i<<1].lz1+=k;
    36.         t[i<<1].lz1%=mod;
    37.         t[i<<1|1].lz1+=k;
    38.         t[i<<1|1].lz1%=mod;
    39.         t[i].lz1=0;
    40.     }
    41.     if(t[i].lz2)
    42.     {
    43.         int k=t[i].lz2;
    44.         int mid=(l+r)>>1;
    45.         t[i<<1].sum2+=k*((mid*(mid+1)/2*(2*mid+1)/3%mod)-((l-1)*((l-1)+1)/2*(2*(l-1)+1)/3%mod)+mod)%mod%mod;
    46.         t[i<<1].sum2%=mod;
    47.         t[i<<1|1].sum2+=k*((r*(r+1)/2*(2*r+1)/3%mod)-((mid+1-1)*((mid+1-1)+1)/2*(2*(mid+1-1)+1)/3%mod)+mod)%mod%mod;
    48.         t[i<<1|1].sum2%=mod;
    49.         t[i<<1].lz2+=k;
    50.         t[i<<1].lz2%=mod;
    51.         t[i<<1|1].lz2+=k;
    52.         t[i<<1|1].lz2%=mod;
    53.         t[i].lz2=0;
    54.     }
    55. }
    56. void build(int i,int l,int r)
    57. {
    58.     t[i].lz0=t[i].lz1=t[i].lz2=0;
    59.     if(l==r)
    60.     {
    61.         t[i].sum0=t[i].sum1=t[i].sum2=0;
    62.         return ;
    63.     }
    64.     int mid=(l+r)>>1;
    65.     build(i<<1,l,mid);
    66.     build(i<<1|1,mid+1,r);
    67.     //pushup(rt);
    68. }
    69. void update0(int rt,int l,int r,int L,int R,int k)
    70. {
    71.     if(L<=l&&r<=R)
    72.     {
    73.         t[rt].sum0+=k*(r-l+1)%mod;
    74.         t[rt].sum0%=mod;
    75.         t[rt].lz0+=k;
    76.         t[rt].lz0%=mod;
    77.         return ;
    78.     }
    79.     pushdown(rt,l,r);
    80.     int mid=(l+r)>>1;
    81.     if(L<=mid) update0(rt<<1,l,mid,L,R,k);
    82.     if(R>mid)update0(rt<<1|1,mid+1,r,L,R,k);
    83.     t[rt].sum0=(t[rt<<1].sum0+t[rt<<1|1].sum0)%mod;
    84.     return;
    85. }
    86. void update1(int rt,int l,int r,int L,int R,int k)
    87. {
    88.     if(L<=l&&r<=R)
    89.     {
    90.         t[rt].sum1+=k*((r+l)*(r-l+1)/2%mod)%mod;
    91.         t[rt].sum1%=mod;
    92.         t[rt].lz1+=k;
    93.         t[rt].lz1%=mod;
    94.         return;
    95.     }
    96.     pushdown(rt,l,r);
    97.     int mid=(l+r)>>1;
    98.     if(L<=mid) update1(rt<<1,l,mid,L,R,k);
    99.     if(R>mid)update1(rt<<1|1,mid+1,r,L,R,k);
    100.     t[rt].sum1=(t[rt<<1].sum1+t[rt<<1|1].sum1)%mod;
    101.     return;
    102. }
    103. void update2(int rt,int l,int r,int L,int R,int k)
    104. {
    105.     if(L<=l&&r<=R)
    106.     {
    107.         t[rt].sum2+=k*((r*(r+1)/2*(2*r+1)/3%mod)-((l-1)*((l-1)+1)/2*(2*(l-1)+1)/3%mod)+mod)%mod%mod;
    108.         t[rt].sum2%=mod;
    109.         t[rt].lz2+=k;
    110.         t[rt].lz2%=mod;
    111.         return;
    112.  
    113.     }
    114.     pushdown(rt,l,r);
    115.     int mid=(l+r)>>1;
    116.     if(L<=mid) update2(rt<<1,l,mid,L,R,k);
    117.     if(R>mid)update2(rt<<1|1,mid+1,r,L,R,k);
    118.     t[rt].sum2=(t[rt<<1].sum2+t[rt<<1|1].sum2)%mod;
    119.     return;
    120. }
    121. int query0(int rt,int l,int r,int L,int R)
    122. {
    123.     if(L<=l&&R>=r)
    124.     {
    125.         return t[rt].sum0;
    126.     }
    127.     pushdown(rt,l,r);
    128.     int mid=(l+r)>>1;
    129.     int ans=0;
    130.     if(mid >= R) ans=ans+query0(rt<<1, l, mid, L, R),ans%=mod;
    131.     else if(mid < L) ans=ans+query0(rt<<1|1, mid + 1, r, L, R),ans%=mod;
    132.     else
    133.     {
    134.         ans=ans+query0(rt<<1, l, mid, L, mid)+query0(rt<<1|1, mid + 1, r, mid + 1, R),ans%=mod;
    135.     }
    136.     return ans;
    137. }
    138. int query1(int rt,int l,int r,int L,int R)
    139. {
    140.     if(L<=l&&R>=r)
    141.     {
    142.         return t[rt].sum1;
    143.     }
    144.     pushdown(rt,l,r);
    145.     int mid=(l+r)>>1;
    146.     int ans=0;
    147.     if(mid >= R) ans=ans+query1(rt<<1, l, mid, L, R),ans%=mod;
    148.     else if(mid < L) ans=ans+query1(rt<<1|1, mid + 1, r, L, R),ans%=mod;
    149.     else
    150.     {
    151.         ans=ans+query1(rt<<1, l, mid, L, mid)+query1(rt<<1|1, mid + 1, r, mid + 1, R),ans%=mod;
    152.     }
    153.     return ans;
    154. }
    155. int query2(int rt,int l,int r,int L,int R)
    156. {
    157.     if(L<=l&&R>=r)
    158.     {
    159.         return t[rt].sum2;
    160.     }
    161.     pushdown(rt,l,r);
    162.     int mid=(l+r)>>1;
    163.     int ans=0;
    164.     if(mid >= R) ans=ans+query2(rt<<1, l, mid, L, R),ans%=mod;
    165.     else if(mid < L) ans=ans+query2(rt<<1|1, mid + 1, r, L, R),ans%=mod;
    166.     else
    167.     {
    168.         ans=ans+query2(rt<<1, l, mid, L, mid)+query2(rt<<1|1, mid + 1, r, mid + 1, R),ans%=mod;
    169.     }
    170.     return ans;
    171. }
    172. signed main()
    173. {
    174.  
    175.     cin>>n>>m;
    176.     build(1,1,n);
    177.     for(int i=1; i<=m; i++)
    178.     {
    179.         int op;
    180.         cin>>op;
    181.         if(op==1)
    182.         {
    183.             int l,r;
    184.             cin>>l>>r;
    185.             update0(1,1,n,l,r,(l-1)*(l-1)%mod);
    186.             update1(1,1,n,l,r,(-2*(l-1)%mod+mod)%mod);
    187.             update2(1,1,n,l,r,1);
    188.         }
    189.         else
    190.         {
    191.             int l,r;
    192.             cin>>l>>r;
    193.             cout<<(query0(1,1,n,l,r)%mod+query1(1,1,n,l,r)%mod+query2(1,1,n,l,r)%mod)%mod<<"\n";
    194.         }
    195.     }
    196.     return 0;
    197. }

  • 相关阅读:
    Nginx的安全控制
    Jmeter常用参数化技巧总结
    基于pytest-bdd的项目目录结构和命名规范
    【成为红帽工程师】第三天 web服务器
    使用PHP实现对称加密和解密过程,真的是太简单了!
    leetcode刷题_验证回文字符串 Ⅱ
    C++【STL】【vector类的使用】【to be continue】
    Perl爬虫程序
    基于昇思MindQuantum， 实现微分方程求解
    【PCL专栏】三维点云空洞修复介绍（一）
  • 原文地址：https://blog.csdn.net/m0_61949623/article/details/127113467