Blog

Problem link

আলোচনাঃ

প্রশ্নে বলা আছে যে,আমাকে কিছু পয়েন্ট দেয়া আছে আর কিছু সেগমেন্ট

(খণ্ড) দেয়া আছে । আমাকে বলতে হবে প্রতিটা খণ্ডে কয়টা করে পয়েন্ট আছে।

প্রশ্নে দেয়া কেস টা নিয়ে চিন্তা করা যাক,

পয়েন্ট – 1, 4, 6, 8, 10  -> p_i 

সেগমেন্ট – 0 , 5 -> A , B

                   6 , 10

                   7 , 100000

এখন, কোন পয়েন্ট টা কোন সেগমেন্ট এ আছে তার জন্য শর্ত হচ্ছে , A≤ p_i ≤B.

তার মানে 0 থেকে 5 পর্যন্ত যত গুলো পয়েন্ট আছে তারা 1 নাম্বার সেগমেন্ট এ থাকবে। 0 থেকে 5 পর্যন্ত পয়েন্ট আছে 1 আর 4। তার মানে প্রথম সেগমেন্ট এ 2টা পয়েন্ট আছে। তেমনি ভাবে ২য় সেগমেন্ট (6 থেকে 10) এ পয়েন্ট আছে 6,8,10=3 টি । আর ৩য় সেগমেন্ট (7 থেকে 100000) এ 8 আর 10 নাম্বার পয়েন্ট আছে। তাই উত্তর 2 ।

উত্তরঃ

এখানে প্রতিটা সেগমেন্ট এর ১ম নাম্বার টা হচ্ছে সেগমেন্ট এর lower bound আর ২য় নাম্বার টা হচ্ছে  সেগমেন্ট এর upper bound। তাহলে lower bound আর upper bound এর মধ্যে কত গুলো পয়েন্ট আছে সেটাই হচ্ছে আমাদের আন্সার।

C++ Code:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int main(){

    // if you use cin/cout, then you will get TLE
    // always use scanf/printf for I/O
    
    int t,n,q;

    scanf("%d",&t);
    for(int i=1;i<=t;i++){

        scanf("%d%d",&n,&q);
        vector<int> v(n);
        for(int j=0;j<n;j++){

            scanf("%d",&v[j]);
        }
        printf("Case %d:\n",i);

        for(int j=0;j<q;j++){
            int x,y;

            scanf("%d%d",&x,&y);
            int LB=lower_bound(v.begin(),v.end(),x)-v.begin(); //O(logN)
            int UB=upper_bound(v.begin(),v.end(),y)-v.begin(); //O(logN)

            printf("%d\n",UB-LB);
        }
        v.clear();
    }
}

      
       // Time Complexity : O(logN)