• Shortsighted(线段树维护2次函数)


    While practicing for The 2019 ICPC Asia Jakarta Regional Contest, Budi stumbled upon an interesting problem on data structure topic. Unfortunately, he misread the problem, but he argues that the problem he thinks of is much more interesting than the original one, thus, this problem.
    Let function f(L, R) on an array of integers A 1..N be defined as incrementing every element in the subarray A i,j each by 1 for all L ≤ i ≤ j ≤ R. In other words, function f(L, R) can be written as follows (in pseudocode).


    Given an array A of N elements (initially A i = 0 for all i = 1..N), your task is to perform Q queries on A of the following types.
    • 1 L R — perform f(L, R) on A.
    • 2 L R — output the sum of all A i where L ≤ i ≤ R.

    输入

    Input begins with a line containing two integers: N Q (1 ≤ N, Q ≤ 100 000) representing the size of A and the number of queries, respectively. The next Q lines each contains a query of the following types.
    • 1 L R (1 ≤ L ≤ R ≤ N)
    • 2 L R (1 ≤ L ≤ R ≤ N)
    There is at least one query of the second type.

    输出

    For each query of the second type in the same order as input, output in a line an integer representing the sum of all A i where L ≤ i ≤ R. As this output can be large, you need to modulo the output by 1 000 000 007.

    样例输入 Copy

    9 7
    1 2 5
    1 4 9
    2 2 7
    1 3 3
    2 2 7
    1 1 5
    2 1 9
    

    样例输出 Copy

    60
    61
    112
    

    提示

     

     暑假遗留问题属于是,没地方交了,但是样例确实过了

    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. pushdown(rt,l,r);
    114. int mid=(l+r)>>1;
    115. if(L<=mid) update2(rt<<1,l,mid,L,R,k);
    116. if(R>mid)update2(rt<<1|1,mid+1,r,L,R,k);
    117. t[rt].sum2=(t[rt<<1].sum2+t[rt<<1|1].sum2)%mod;
    118. return;
    119. }
    120. int query0(int rt,int l,int r,int L,int R)
    121. {
    122. if(L<=l&&R>=r)
    123. {
    124. return t[rt].sum0;
    125. }
    126. pushdown(rt,l,r);
    127. int mid=(l+r)>>1;
    128. int ans=0;
    129. if(mid >= R) ans=ans+query0(rt<<1, l, mid, L, R),ans%=mod;
    130. else if(mid < L) ans=ans+query0(rt<<1|1, mid + 1, r, L, R),ans%=mod;
    131. else
    132. {
    133. ans=ans+query0(rt<<1, l, mid, L, mid)+query0(rt<<1|1, mid + 1, r, mid + 1, R),ans%=mod;
    134. }
    135. return ans;
    136. }
    137. int query1(int rt,int l,int r,int L,int R)
    138. {
    139. if(L<=l&&R>=r)
    140. {
    141. return t[rt].sum1;
    142. }
    143. pushdown(rt,l,r);
    144. int mid=(l+r)>>1;
    145. int ans=0;
    146. if(mid >= R) ans=ans+query1(rt<<1, l, mid, L, R),ans%=mod;
    147. else if(mid < L) ans=ans+query1(rt<<1|1, mid + 1, r, L, R),ans%=mod;
    148. else
    149. {
    150. ans=ans+query1(rt<<1, l, mid, L, mid)+query1(rt<<1|1, mid + 1, r, mid + 1, R),ans%=mod;
    151. }
    152. return ans;
    153. }
    154. int query2(int rt,int l,int r,int L,int R)
    155. {
    156. if(L<=l&&R>=r)
    157. {
    158. return t[rt].sum2;
    159. }
    160. pushdown(rt,l,r);
    161. int mid=(l+r)>>1;
    162. int ans=0;
    163. if(mid >= R) ans=ans+query2(rt<<1, l, mid, L, R),ans%=mod;
    164. else if(mid < L) ans=ans+query2(rt<<1|1, mid + 1, r, L, R),ans%=mod;
    165. else
    166. {
    167. ans=ans+query2(rt<<1, l, mid, L, mid)+query2(rt<<1|1, mid + 1, r, mid + 1, R),ans%=mod;
    168. }
    169. return ans;
    170. }
    171. signed main()
    172. {
    173. cin>>n>>m;
    174. build(1,1,n);
    175. for(int i=1; i<=m; i++)
    176. {
    177. int op;
    178. cin>>op;
    179. if(op==1)
    180. {
    181. int l,r;
    182. cin>>l>>r;
    183. int len=r-l+1;
    184. update0(1,1,n,l,r,((-(l-1)*(l-1)-(l-1)*(len+1))%mod+mod)%mod);
    185. update1(1,1,n,l,r,((2*l+len-1)%mod+mod)%mod);
    186. update2(1,1,n,l,r,-1);
    187. }
    188. else
    189. {
    190. int l,r;
    191. cin>>l>>r;
    192. cout<<(query0(1,1,n,l,r)%mod+query1(1,1,n,l,r)%mod+query2(1,1,n,l,r)%mod)%mod<<"\n";
    193. }
    194. }
    195. return 0;
    196. }

  • 相关阅读:
    基于单片机的红外遥控解码程序设计与实现
    Docker入门
    nodejs事件循环
    Linux综合使用练习
    网络原理-UDP/TCP详解
    一个高频问题:异步操作会创建线程吗?
    面试题6 -- 腐烂的苹果(多源DFS)
    VsCode + gdb + gdbserver远程调试arm嵌入式linux C/C++程序
    零代码数字化管理工具——Workless
    使用 puppeteer 加载 html 文件来运行 js 文件
  • 原文地址:https://blog.csdn.net/m0_61949623/article/details/127114694