﻿

# numbers_tree

Jan 12th, 2021
608
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /// cu Caught fatal signal 11 - pe pbinfo
2. #include <bits/stdc++.h>
3. #define NMAX 100005
4. #define MAX 1000001
5. using namespace std;
6. ifstream fin("numbers_tree.in");
7. ofstream fout("numbers_tree.out");
8. int n, Q;
9. bool isPrime[MAX], A[NMAX];
10. inline int left(int p) { return 2*p; }
11. inline int right(int p) { return (2*p) + 1; }
12. struct Node
13. {
14.     int sum = 0;
15.     int prefix=0;
16.     int suffix=0;
17.     int ans=0;
18.     int lazy = 0;
19.     void resetNode()
20.     {
21.         sum = 0;
22.         prefix=0;
23.         suffix=0;
24.         ans=0;
25.         lazy = 0;
26.     }
27.     void setSum(int val)
28.     {
29.         sum = val;
30.         prefix=suffix=ans=max(0,val);
31.     }
32.     void combine(Node &a, Node &b, int &tl, int &tr, int &tm)
33.     {
34.         sum = a.sum + b.sum;
35.         prefix = max(a.prefix, a.prefix + (a.prefix==tm-tl+1)*b.prefix);
36.         suffix = max(b.suffix, b.suffix + a.suffix * (b.suffix==tr - tm));
37.         ans=max(a.ans,max(b.ans,a.suffix+b.prefix));
38.     }
39. };
40. Node st[4 * NMAX + 7];
41. void sieveOfEratosthenes(bool isPrime[])
42. {
43.     isPrime[0]=isPrime[1] = false;
44.     for(int pi = 2; pi * pi <= MAX; ++pi)
45.     {
46.         if (isPrime[pi] == true)
47.             for(int i = pi * 2; i <= MAX; i += pi)
48.                 isPrime[i] = false;
49.     }
50. }
51. void build(int p, int l, int r)
52. {
53.     if (l == r)
54.     {
55.         st[p].setSum(A[l]);
56.         return;
57.     }
58.     int mid = l + (r - l)/2;
59.     build(left(p), l, mid);
60.     build(right(p), mid+1, r);
61.     st[p].combine(st[left(p)], st[right(p)],l,r,mid);
62. }
63.
64. void pushDown(int p, int l, int r)
65. {
66.     if (st[p].lazy == 0) return;
67.     int mid = l + (r - l)/2;
68.     st[left(p)].setSum((mid-l+1) * st[p].lazy);
69.     st[right(p)].setSum((r-mid+1) * st[p].lazy);
70.     st[left(p)].lazy = st[right(p)].lazy = st[p].lazy;
71.     st[p].lazy = 0;
72. }
73. void updateRangeLazy(int p, int l, int r, int i, int j, int val)
74. {
75.     if (i == l && j == r)
76.     {
77.         st[p].setSum((r - l + 1) * val);
78.         if (l != r) st[p].lazy = val;
79.         return;
80.     }
81.     pushDown(p, l, r);
82.     int mid = l + (r - l)/2;
83.     if(j<= mid) updateRangeLazy(left(p), l, mid, i, j, val);
84.     else if(i>mid) updateRangeLazy(right(p), mid + 1, r, i, j, val);
85.     else
86.     {
87.         updateRangeLazy(left(p), l, mid, i, mid, val);
88.         updateRangeLazy(right(p), mid + 1, r, mid + 1, j, val);
89.     }
90.     st[p].combine(st[left(p)], st[right(p)],i,j,mid);
91. }
92.
93. Node queryLazy(int p, int l, int r, int i, int j)
94. {
95.     if (i == l && j == r) return st[p];
96.
97.     pushDown(p, l, r);
98.
99.     int mid = l + (r - l)/2;
100.     if(j<= mid) return queryLazy(left(p), l, mid, i, j);
101.     if(i > mid)return queryLazy(right(p), mid + 1, r, i, j);
102.     Node ret;
103.     Node ln = queryLazy(left(p), l, mid, i, mid);
104.     Node rn = queryLazy(right(p), mid + 1, r, mid+1, j);
105.     ret.combine(ln, rn, i, j,mid);
106.     return ret;
107. }
108.
109. int main()
110. {
111.     int x, q, y, val;
112.     memset(isPrime, true, sizeof isPrime);
113.     sieveOfEratosthenes(isPrime);
114.     fin>>n>>Q;
115.     for(int i=0; i<n; i++)
116.     {
117.         fin>>x;
118.         if(isPrime[x])
119.             A[i]=1;
120.     }
121.     build(1,0,n-1);
122.     while(Q)
123.     {
124.         fin>>q;
125.         if(q==1)
126.         {
127.             fin>>x>>y>>val;
128.             if(isPrime[val])
129.                 updateRangeLazy(1,0,n-1, x-1,y-1,1);
130.             else
131.                 updateRangeLazy(1,0,n-1, x-1,y-1,0);
132.         }
133.         else if(q==2)
134.         {
135.             fin>>x>>y;
136.             Node sol=queryLazy(1,0,n-1,x-1,y-1);
137.             fout<<(y - x + 1) - sol.sum<<'\n';
138.         }
139.         else
140.         {
141.             fin>>x>>y;
142.             Node sol=queryLazy(1,0,n-1,x-1,y-1);
143.             fout<<sol.ans<<'\n';
144.         }
145.         --Q;
146.     }
147.     return 0;
148. }
149.
RAW Paste Data