[toph.co] Yet Another Update Query Problem

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Yet Another Upate Query Problem
Source            : toph.co
Category          : Data Structure
Algorithm         : Square Root Decomposition, Lazy Propagation
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
static const int maxn = 200000 + 5;
static const int maxb = 320;
 
struct information
{
      bool lazy;
      int s, e, val;
      information(bool lazy = 0, int s = 0, int e = 0, int val = 0) :
            lazy(lazy), s(s), e(e), val(val) {}
};
 
int arr[maxn], freq[320][maxn];
information block[320];
 
inline int get_block(int l)
{
      return l / maxb;
}
 
inline void updateLazy(int b)
{
      information &bl = block[b];
      if (bl.lazy == 0) return;
      for (int i = bl.s; i <= bl.e; i++)
      {
            freq[b][ arr[i] ]--;
            arr[i] += bl.val;
            freq[b][ arr[i] ]++;
       }
       bl.lazy = 0;
       bl.val = 0;
}
 
inline void update_a_query(int l, int r, int val)
{
      int ls = get_block(l);
      int rs = get_block(r);
      updateLazy(ls);
      information &bl = block[ls];
      information &rl = block[rs];
      for (int i = l; i <= min(r, bl.e); i++)
      {
            freq[ls][ arr[i] ]--;
            arr[i] += val;
            freq[ls][ arr[i] ]++;
      }
      if (ls == rs) return;
      for (int i = ls+1; i < rs; i++)
      {
            block[i].lazy = 1;
            block[i].val += val;
      }
      updateLazy(rs);
      for (int i = rl.s; i <= r; i++)
      {
            freq[rs][ arr[i] ]--;
            arr[i] += val;
            freq[rs][ arr[i] ]++;
      }
}
 
inline int ans_a_query(int l, int r, int val)
{
      int frequency = 0;
      int ls = get_block(l);
      int rs = get_block(r);
      updateLazy(ls);
      information &bl = block[ls];
      information &rl = block[rs];
      for (int i = l; i <= min(r, bl.e); i++)
      {
            frequency += arr[i] == val;
      }
      if (ls == rs) return frequency;
      for (int i = ls+1; i < rs; i++)
      {
            int req = val - block[i].val;
            if (req >= 0) frequency += freq[i][req];
      }
      updateLazy(rs);
      for (int i = rl.s; i <= r; i++)
      {
            frequency += arr[i] == val;
      }
      return frequency;
}
 
inline void create_block(int n)
{
      int pre = 0;
      block[0] = new information();
      block[0].s = 1;
      for (int i = 1; i <= n; i++)
      {
            int bl = get_block(i);
            if (pre < bl)
            {
                  block[pre].e = i - 1;
                  block[bl] = new information();
                  block[bl].s = i;
                  pre = bl;
            }
      }
      block[pre].e = n;
}
 
int main()
{
      //freopen("in.txt", "r", stdin);
 
      int tc;
      scanf("%d", &tc);
      for (int tcase = 1; tcase <= tc; tcase++)
      {
            int n, q;
            scanf("%d %d", &n, &q);
            create_block(n);
            for (int i = 1; i <= n; i++)
            {
                  scanf("%d", &arr[i]);
                  int bl = get_block(i);
                  freq[bl][ arr[i] ]++;
            }
            printf("Case %d:\n", tcase);
            for (int i = 0; i < q; i++)
            {
                  int type;
                  scanf("%d", &type);
                  if (type == 1)
                  {
                        int l, r, v;
                        scanf("%d %d %d", &l, &r, &v);
                        update_a_query(l, r, v);
                  }
                  else
                  {
                        int l, r, v;
                        scanf("%d %d %d", &l, &r, &v);
                        int ans = ans_a_query(l, r, v);
                        printf("%d\n", ans);
                  }
            }
            memset(freq, 0, sizeof freq);
      }
}