mihaimarcel21

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