PrefixSum + IterativeSegmentTree + Co-ordinate Compression using sorting in C
Intuition\n Describe your first thoughts on how to solve this problem. \nsame as previous problem but using sorting to do co-ordinate compression with segment t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nsame as previous problem but using sorting to do co-ordinate compression with segment tree to do some range query. \n# Approach\n<!-- Describe your approach to solving the problem. -->\nsegment tree is used to search the max over the compressed intervals which we get after sorting to pick the one which has maximum occurence and then adding the remaining part where some different number transformed to this same number with max freq/occ ensuring the total no. of operation is not violated.\n\n# Complexity\n- Time complexity: o(nlogn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: o(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```c []\n#define N (((int)2e5)+100)\nint set[N][2],ori[N][2],temp[N];//segtree[(1<<19)];\nint max(int a,int b){\n    return ((a>=b)?(a):(b));\n}\nint min(int a,int b){\n    return ((a<=b)?(a):(b));\n}\n\n// nonlazyIsgt -> 0-indexed \nint segtree[(1<<19)];\nint _max(int a,int b){\n    return ((a>=b)?(a):(b));\n}\nint _min(int a,int b){\n    return ((a<=b)?(a):(b));\n}\nvoid segtree_init(int n,int* stsz){\n    while((1<<(*stsz))<=n){\n        (*stsz)++;\n    }\n    *stsz = (1<<(*stsz));\n    return;\n}\nvoid update(int pos,int value,int* stsz){\n    int new_pos = pos + (*stsz);\n    segtree[new_pos] = value;\n    new_pos /= 2;\n    while(new_pos>0){\n        int leftChildValue = segtree[2*new_pos] , rightChildValue = segtree[2*new_pos+1];\n        segtree[new_pos] = _max(leftChildValue,rightChildValue);\n        new_pos /= 2;\n    }\n    return;\n}\n\nint query(int start,int end,int* stsz){\n    start = start + (*stsz),end=end+(*stsz);\n    int ans = 0;\n    while(start<=end){\n        if(start&1){\n            ans = _max(ans,segtree[start++]);\n        }   \n        if(end%2==0){\n            ans = _max(ans,segtree[end--]);\n        }\n        start/=2;\n        end/=2;\n    }\n    return ans;\n}\n\ntypedef int compare_self_t(const void* ar,int fr,int sc);\ntypedef void swap_self_t(const void* ar,int fr,int sc);\n\nint compare_self_int(const void* arr,int f,int s){\n    int* a1 =(int*)arr;\n    return (a1[f]<a1[s]);\n}\n\nvoid swap_self_int(const void *arr,int f,int s){\n    int* a1 =(int*)arr; \n    int t=a1[f];\n    a1[f]=a1[s];\n    a1[s]=t;\n    return;\n}\n    \nvoid heapify(const void* arr,int root,int sz,compare_self_t compfn,swap_self_t swapfn){\n    int greatest = root,left=2*root+1,right=2*root+2;\n    if((left<sz)&&(compfn(arr,greatest,left))){\n        greatest = left;    \n    }\n    if((right<sz)&&(compfn(arr,greatest,right))){\n        greatest = right;    \n    }\n    if(greatest!=root){\n        swapfn(arr,greatest,root);\n        heapify(arr,greatest,sz,compfn,swapfn);\n    }\n}\nvoid heapSort(const void* arr,int low,int high,compare_self_t compfn,swap_self_t swapfn){\n    for(int z=(low+(high-low)/2);z>=low;z--){\n        heapify(arr,z,high+1,compfn,swapfn);    \n    }\n    for(int end=high;end>=low;end--){\n        swapfn(arr,low,end);    \n        heapify(arr,low,end,compfn,swapfn);    \n    }\n}\n// int set[N][2],ori[N][2],temp[N];\n// sorting + co-ordinate compression + binarySearch(lowerBound/upperbound) on top of previous question approach\nvoid coord_compresion(const void* oriN,int* nums,int* sz,int n){\n    int z = 0;\n    int* ori = ((int*)oriN);\n    memset(ori,0,sizeof(ori));\n    ori[z*2+0] = nums[0]; // value \n    ori[z*2+1] = 1; // count\n    int prev =  nums[0];\n    for(int i=1;i<n;i++){\n       if(prev!=nums[i]){\n           ori[(++z)*2+0] = nums[i];\n           ori[z*2+1] = 1;\n       }\n       else{\n          ori[z*2+1]++; \n       }\n       prev = nums[i];\n    }\n    *sz = z+1;\n}\nint lower_bound_set(const void* _Set,int value,int low,int high){ // give the exact value as these were the one which were set before\n    int* _set = (int*)_Set;\n    // find value and retunr position\n    int ans = low;\n    while(low<=high){\n        int mid = low + (high-low)/2;\n        if(_set[mid*2+0]>value){\n            high = mid-1; // new lower high\n        }\n        else{\n            ans = mid; // <= new higher low\n            low = mid+1;\n        }\n    }\n    return ans;\n}\nint lb_set(const void* _Set,int value,int low,int high){ // give the exact value as these were the one which were set before\n    int* _set = (int*)_Set;\n    // find value and retunr position\n    int ans = low;\n    while(low<=high){\n        int mid = low + (high-low)/2;\n        if(_set[mid*2+0]>=value){\n            ans = mid; // <= new higher low\n            high = mid-1; // new lower high\n        }\n        else{ // _set[mid*2+0] < value\n            low = mid+1;\n        }\n    }\n    return ans;\n}\n\nint maxFrequency(int* nums, int numsSize, int k, int numOperations) {\n    int ans = 0,i,n=numsSize,op=numOperations,z=0,sz=0,ssz=0,stsz=0;\n    // sorting + co-ordinate compression + binarySearch(lowerBound/upperbound) on top of previous question approach\n    heapSort(nums,0,n-1,compare_self_int,swap_self_int);\n    coord_compresion(ori,nums,&sz,n);\n    memset(temp,0,sizeof(temp));\n    memset(segtree,0,sizeof(segtree));\n    segtree_init(sz,&stsz);\n    // prefix Sum InclStart-ExclEndPlus Technique to simulate line \n    for(i=0;i<sz;i++){\n        temp[z]=ori[i][0]-k;\n        temp[++z]=ori[i][0]+k+1;\n        z++;\n        ans = max(ans,ori[i][1]);\n        update(i,ori[i][1],&stsz); // update happens :- T.C:- log(n)\n    }\n    heapSort(temp,0,z-1,compare_self_int,swap_self_int);    \n    coord_compresion(set,temp,&ssz,z);\n    for(i=0;i<ssz;i++){\n        set[i][1] = 0;\n    }\n    // binarySeaarch simulating set insertion operation \n    for(i=0;i<n;i++){\n        int includeStart = nums[i]-k;\n        int ExclEndPlus  = nums[i]+k+1;\n        int posincludeStart = lower_bound_set(set,includeStart,0,ssz-1);\n        int posExclEndPlus = lower_bound_set(set,ExclEndPlus,0,ssz-1);\n        set[posincludeStart][1] += 1;\n        set[posExclEndPlus][1] -= 1;\n    }\n    // same prefixSum approach as previous problem \n    for(int i=0;i<ssz;i++){\n        if(i==0) {\n           continue;// goto label;\n        }\n        set[i][1] += set[i-1][1];\n        int fix_high = lower_bound_set(ori,set[i][0]-1,0,sz-1); //<=set[i][0]\n        int fix_low  = lb_set(ori,set[i-1][0],0,fix_high);\n        if(set[i][1]<=op){\n            ans = max(ans,set[i][1]);\n        } \n        if(set[i-1][1]<=op){\n            ans = max(ans,set[i-1][1]);\n        } \n        if((ori[fix_low][0]<=set[i][0])&&(ori[fix_low][0]>=set[i-1][0])){\n                int rem = set[i-1][1] - ori[fix_low][1];\n                if(rem>=op){\n                    ans = max(ans,op+ori[fix_low][1]);\n                }\n                int same = query(fix_low,fix_high,&stsz);\n                rem = set[i-1][1] - same;\n                if(rem>op){\n                    ans = max(ans,op+same);\n                }\n                else{\n                    ans = max(ans,set[i-1][1]);\n                }\n        }\n    }\n    return ans;\n}\n```
['C']