fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define lld long long int
  3. #define MAX 400005
  4. using namespace std;
  5.  
  6. lld tree[MAX];
  7. lld lazy[MAX]={0};
  8.  
  9. lld a[100005];
  10.  
  11. void init(int i,int start,int end)
  12. {
  13.     if(start==end)
  14.     {
  15.         tree[i] = a[start];
  16.         return;
  17.     }
  18.     int mid = (start+end)/2;
  19.     init(2*i,start,mid);
  20.     init(2*i+1,mid+1,end);
  21.     tree[i] = min(tree[2*i],tree[2*i+1]);
  22. }
  23.  
  24. lld X(int i,int start,int end,lld x)
  25. {
  26.     if(lazy[i]!=0)
  27.     {
  28.         tree[i] = tree[i]+lazy[i];
  29.  
  30.         if(start>end)
  31.         {
  32.             lazy[2*i]+=lazy[i];
  33.             lazy[2*i+1]+=lazy[i];
  34.         }
  35.  
  36.         lazy[i]=0;
  37.     }
  38.     if(tree[i]>=x)
  39.     {
  40.         return end-start+1;
  41.     }
  42.  
  43.     if(start==end)
  44.     {
  45.         return (tree[i]>=x)?1:0;
  46.     }
  47.  
  48.     int mid = (start+end)/2;
  49.  
  50.     return X(2*i,start,mid,x) + X(2*i+1,mid+1,end,x);
  51. }
  52.  
  53. void Y(int i,int start,int end,lld y)
  54. {
  55.     if(lazy[i]!=0)
  56.     {
  57.         tree[i] = tree[i]+lazy[i];
  58.         if(start>end)
  59.         {
  60.             lazy[2*i]+=lazy[i];
  61.             lazy[2*i+1]+=lazy[i];
  62.         }
  63.         lazy[i]=0;
  64.     }
  65.     if(tree[i]>=y)
  66.     {
  67.         tree[i] = tree[i]-1;
  68.         if(start>end)
  69.         {
  70.             lazy[2*i]-=1;
  71.             lazy[2*i+1]-=1;
  72.         }
  73.         return;
  74.     }
  75.  
  76.     if(start==end)
  77.     return;
  78.  
  79.     int mid = (start+end)/2;
  80.  
  81.     Y(2*i,start,mid,y);
  82.     Y(2*i+1,mid+1,end,y);
  83. }
  84.  
  85. void add(int i,int start,int end,int index)
  86. {
  87.     if(lazy[i]!=0)
  88.     {
  89.         tree[i] = tree[i]+lazy[i];
  90.         if(start>end)
  91.         {
  92.             lazy[2*i]+=lazy[i];
  93.             lazy[2*i+1]+=lazy[i];
  94.         }
  95.         lazy[i]=0;
  96.     }
  97.     if(start>index||end<index)
  98.     return;
  99.  
  100.     if(start==end&&start==index)
  101.     {
  102.         tree[i] = tree[i]+1;
  103.         return;
  104.     }
  105.  
  106.     if(start<=index&&index<=end)
  107.     {
  108.         if(tree[i]==a[index])
  109.         tree[i]=tree[i]+1;
  110.     }
  111.  
  112.     int mid = (start+end)/2;
  113.     add(2*i,start,mid,index);
  114.     add(2*i+1,mid+1,end,index);
  115. }
  116.  
  117. int main()
  118. {
  119.  
  120.     lld n,q,m;
  121.     scanf("%lld",&n);
  122.     scanf("%lld",&q);
  123.  
  124.     for(int i=0;i<n;i++)
  125.     scanf("%lld",&a[i]);
  126.  
  127.  
  128.     init(1,0,n-1);
  129.     memset(lazy,0,sizeof(lazy));
  130.  
  131.     int type;
  132.  
  133.     while(q--)
  134.     {
  135.         scanf("%d",&type);
  136.         scanf("%lld",&m);
  137.         switch(type)
  138.         {
  139.             case 1:
  140.                   m--;
  141.                   add(1,0,n-1,m);
  142.                   break;
  143.             case 2:
  144.                    printf("%lld\n",X(1,0,n-1,m));
  145.                    break;
  146.             case 3:
  147.                    Y(1,0,n-1,m);
  148.                    break;
  149.         }
  150.     }
  151.     return 0;
  152. }
  153.  
Success #stdin #stdout 0s 10376KB
comments (?)
stdin
copy 
5 6
20 30 10 50 40
2 31
1 2
2 31
3 11
2 20
2 50
stdout
copy 
2
3
4
1
https://ideone.com/7CkURQ
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

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!