fork download
copy 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<cmath>
  5. #include<cstring>
  6. #define MAX 100001LL
  7. #define SMAX 262144LL
  8. using namespace std;
  9. typedef long long ll;
  10. struct element
  11. {
  12.     ll f;
  13.     ll m;
  14. };
  15. ll A[MAX];
  16. element tree[SMAX];
  17. ll fmid(ll a,ll b)
  18. {
  19.     return(a+((b-a)/2LL));
  20. }
  21. void construct_tree(ll index,ll ss,ll se)
  22. {
  23.     if(ss==se)
  24.     {
  25.         tree[index].f=A[ss];
  26.         tree[index].m=A[ss]*ss;
  27.     }
  28.     else
  29.     {
  30.         ll mid=fmid(ss,se);
  31.         construct_tree(2LL*index+1LL,ss,mid);
  32.         construct_tree(index*2LL+2LL,mid+1LL,se);
  33.         tree[index].f=tree[2LL*index+1LL].f+tree[2LL*index+2LL].f;
  34.         tree[index].m=tree[2LL*index+1LL].m+tree[2LL*index+2LL].m;
  35.     }
  36. }
  37. void update_tree(ll index,ll i,char ch,ll ss,ll se)
  38. {
  39.     if(i>=ss && i<=se)
  40.     {
  41.         if(ch=='+')
  42.         {
  43.             tree[index].f++;
  44.             tree[index].m+=i;
  45.         }
  46.         else if(ch=='-')
  47.         {
  48.             tree[index].f--;
  49.             tree[index].m-=i;
  50.         }
  51.         if(ss!=se)
  52.         {
  53.             ll mid=fmid(ss,se);
  54.             update_tree(2LL*index+1LL,i,ch,ss,mid);
  55.             update_tree(2LL*index+2LL,i,ch,mid+1LL,se);
  56.         }
  57.     }
  58. }
  59. element query_tree(ll index,ll ss,ll se,ll qs,ll qe)
  60. {
  61.     element temp,a,b;
  62.     temp.f=temp.m=0LL;
  63.     if(qe<ss || qs>se)
  64.         return temp;
  65.     if(ss>=qs && se<=qe)
  66.         return tree[index];
  67.     ll mid=fmid(ss,se);
  68.     a=query_tree(2LL*index+1LL,ss,mid,qs,qe);
  69.     b=query_tree(2LL*index+2LL,mid+1LL,se,qs,qe);
  70.     temp.f=a.f+b.f;
  71.     temp.m=a.m+b.m;
  72.     return temp;
  73. }
  74. int main()
  75. {
  76.     element temp={0LL,0LL};
  77.     std::fill(tree,tree+SMAX,temp);
  78.     ll a,b,x,l,r,y,ans,s;
  79.     int m,n;
  80.     char ch;
  81.     cin>>n;
  82.     std::fill(A,A+MAX,0LL);
  83.     for(int i=1;i<=n;i++)
  84.     {
  85.         cin>>a>>b;
  86.         A[a]+=b;
  87.     }
  88.     construct_tree(0LL,0LL,MAX-1LL);
  89.     /*
  90.     printf("Tree:\n");
  91.     for(int i=0;i<SMAX;i++)
  92.     {
  93.         printf("(%d,%d) ",tree[i].f,tree[i].m);
  94.     }
  95.     printf("\n");
  96.     */
  97.     cin>>m;
  98.     while(m--)
  99.     {
  100.         cin>>ch>>x;
  101.         if(ch=='+')
  102.         {
  103.             A[x]++;
  104.             update_tree(0LL,x,ch,0LL,MAX-1LL);
  105.         }
  106.         else if(ch=='-')
  107.         {
  108.             A[x]--;
  109.             update_tree(0LL,x,ch,0LL,MAX-1LL);
  110.         }
  111.         else if(ch=='?')
  112.         {
  113.             l=x+1LL;
  114.             r=MAX-1LL;
  115.             temp=query_tree(0LL,0LL,MAX-1LL,l,r);
  116.             ans=0LL;
  117.             ans+=(temp.f)*x;
  118.             //printf("ans at this stage: %d\n",ans);
  119.             y=1;
  120.             s=sqrt(x);
  121.             while(y<=s)
  122.             {
  123.                 l=(x/(y+1LL))+1LL;
  124.                 r=x/y;
  125.                 if(l>=r)
  126.                     break;
  127.                 temp=query_tree(0LL,0LL,MAX-1LL,l,r);
  128.                 ans+=temp.f*x-temp.m*y;
  129.                 y++;
  130.             }
  131.             for(ll i=1LL;i<=(x/y);i++)
  132.                 ans+=(x%i)*A[i];
  133.             cout<<ans<<endl;
  134.         }
  135.     }
  136.  
  137.     return 0;
  138. }
  139.  
Success #stdin #stdout 0s 7568KB
comments (?)
stdin
copy 
3
1 4
3 2
2 2
6
? 10
? 8
+ 4
? 9
- 2
? 8
stdout
copy 
2
4
3
4
https://ideone.com/JxDfUG
language:
C++ 4.3.2 (gcc-4.3.2)
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!