fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define lld long long
  5. #define MAX 100005
  6.  
  7. lld a[MAX];
  8. template<class T>
  9. class BIT
  10. {
  11.     T *tree;
  12.     int size;
  13.     public:
  14.  
  15.         BIT(int sz)
  16.         {
  17.             tree = new T[sz+1];
  18.             for(int i=0;i<=sz;i++)
  19.                 tree[i] = 0;
  20.             size = sz;
  21.         }
  22.         void update(int idx,lld value)
  23.         {
  24.             while(idx<=size)
  25.             {
  26.                 tree[idx]+=value;
  27.                 idx+=(idx&(-idx));
  28.             }
  29.         }
  30.         lld read(int idx)
  31.         {
  32.             lld sum =0;
  33.             while(idx>0)
  34.             {
  35.                 sum = sum + tree[idx];
  36.                 idx-=(idx&(-idx));
  37.             }
  38.             return sum;
  39.         }
  40. };
  41.  
  42. void unMark(int start,int end,BIT<lld> bit1,BIT<lld> bit2)
  43. {
  44.     if(start>end)
  45.         return;
  46.     int mid = (start+end)/2;
  47.  
  48.     if(start==end)
  49.     {
  50.  
  51.         if(a[start]!=1)
  52.         {
  53.             lld temp = a[start];
  54.             a[start] = floor(sqrtl(a[start]));
  55.             bit1.update(start+1,a[start]-temp);
  56.             if(a[start]==1)
  57.                 bit2.update(start+1,1);
  58.         }
  59.         return;
  60.  
  61.     }
  62.     if(a[mid]!=1)
  63.     {
  64.  
  65.         lld temp = a[mid];
  66.         a[mid] = floor(sqrtl(a[mid]));
  67.  
  68.         bit1.update(mid+1,a[mid]-temp);
  69.  
  70.         if(a[mid]==1)
  71.             bit2.update(mid+1,1);
  72.     }
  73.  
  74.     if(bit2.read(mid)-bit2.read(start)==0)
  75.         unMark(start,mid-1,bit1,bit2);
  76.     if(bit2.read(end+1)-bit2.read(mid+1)==0)
  77.         unMark(mid+1,end,bit1,bit2);
  78. }
  79.  
  80. int main()
  81. {
  82.     int n,q,x,y,type,t=1;
  83.  
  84.     while(scanf("%d",&n)!=EOF)
  85.     {
  86.         printf("Case #%d:\n",t);
  87.         t++;
  88.  
  89.         for(int i=0;i<n;i++)
  90.             scanf("%lld",&a[i]);
  91.  
  92.         BIT<lld> bit1(n),bit2(n);
  93.  
  94.         for(int i=0;i<n;i++)
  95.         {
  96.             bit1.update(i+1,a[i]);
  97.             if(a[i]==1)
  98.                 bit2.update(i+1,1);
  99.         }
  100.  
  101.         scanf("%d",&q);
  102.         while(q--)
  103.         {
  104.             scanf("%d%d%d",&type,&x,&y);
  105.  
  106.             if(x>y)
  107.                swap(x,y);
  108.             x--;
  109.             y--;
  110.  
  111.             if(type==0)
  112.             {
  113.                 unMark(x,y,bit1,bit2);
  114.             }
  115.             else
  116.             {
  117.                 lld sum = bit1.read(y+1) - bit1.read(x);
  118.                 printf("%lld\n",sum);
  119.             }
  120.         }
  121.         printf("\n");
  122.     }
  123.     return 0;
  124. }
  125.  
  126.  
Success #stdin #stdout 0s 4256KB
comments (?)
stdin
copy 
5
1 2 3 4 5
5
1 2 4
0 2 4
1 2 4
0 4 5
1 1 5
4
10 10 10 10
3
1 1 4
0 2 3
1 1 4
stdout
copy 
Case #1:
9
4
6

Case #2:
40
26
https://ideone.com/fyqxJX
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!