সবচেয়ে শরটেস্ট সাব অ্যাারে টা বের করতে বলেছে, যার মধ্যে আমরা ওই অ্যাারের মোট এলিমেন্ট গুলার মধ্যের সবচেয়ে ম্যাক্সিমাম অর সাম টা পেতে পারি ।
যেহেতু সাব অ্যাারে বের করতে বলছে, সাব সিকুয়েন্স না, তাই আমরা স্টারটিং এন্ড লিনিয়ারলি এক বাড়ায়ে বাড়ায়ে চেক করতে করতে যাব । এন্ড , সাব অ্যারের ফিনিশিং এন্ডটার যেহেতু ম্যাক্সিমাম আর সাম এর লোয়ার বাউন্ড টা আমাদের লাগতেসে তাই আমরা এইখানে যতক্ষন অর সাম, ম্যাক্স এর চাইতে বড় বা সমান থাকবে ততক্ষন hi এর মান এক এক করে কমিয়ে কমিয়ে চেক করে সাব এ্যারের ফিনিশিং এন্ডের লোয়ার বাউন্ড পেতে পারি ।
এখানে কোন অ্যাারের অর সাম একটা নন ডিক্রিজিং থিং... তাই এই প্রোপারটি তে আমরা বাইনারি সার্চ চালায়ে সাব অ্যারের নেক্সট এন্ড টা ফিক্স করে নিতেই পারি ।
আর তার মানে এক পাশ ফিক্স রেখে অন্য পাশ বাইনারি সার্চ করে অপটিমাল সাব অ্যাারে ফিক্স করতে পারি। কিন্তু এখন O(logn) টাইমে যদি আমরা ওই লিনিয়ার এন্ড আর বাইনারি সার্চ করা পরের এন্ডের অর সাম পেতে চাই , তাহলে আমাদের অবশ্যই সেগমেন্ট ট্রি অথবা স্পারস টেবিল ডেটা স্ট্রাকচার ব্যবহার করতে পারি। তাহলেই হয়ে যাবে। এইতো আর কিছু লাগবে নাহ...। ওকেই ।
Code:
// aarifshuvo ``CSEJU #include <bits/stdc++.h> #define ll long long #define pb push_back #define SZ(x) ((int)(x).size()) #define scl(x) scanf("%lld", &x) #define scll(x,y) scanf("%lld %lld", &x, &y) #define all(x) (x).begin(),(x).end() #define mem(a,d) memset(a,d,sizeof a) #define REP(i,n) for(int i=0;i<n;i++) #define REV(i,n) for(int i=n-1;i>=0;i--) #define FOR(i,a,b) for(int i=a;i<=b;i++) #define pri(a) cout<<a<<endl #define prii(a,b) cout<<a<<" "<<b<<endl using namespace std; #define inf 12345678912 #define sz 100007 ll ar[sz], tr[sz*3]; void update(int node, int nb, int ne, int id, ll val) { if(nb==ne) { ar[nb] = val; tr[node] = val; return; } int mid = (nb+ne)/2; int lft = 2*node; int rgt = lft + 1; if(id <= mid) update(lft, nb, mid, id, val); else if(id > mid) update(rgt, mid+1, ne, id, val); tr[node] = tr[lft] | tr[rgt]; } ll query(int node, int nb, int ne, int i, int j) { if(i>ne or j<nb) return 0; if(i<=nb and j>=ne) return tr[node]; int mid = (nb+ne)/2; int lft = 2*node; int rgt = lft + 1; ll p1 = query(lft, nb, mid, i, j); ll p2 = query(rgt, mid+1, ne, i, j); return p1 | p2; } int main() { ll n,x,y; scl(n); ll mx = 0; FOR(i,1,n) { scl(ar[i]); update(1,1,n,i,ar[i]); mx |= ar[i]; } ll res = INT_MAX, ans = 0; FOR(i,1,n) { int lo = i, hi = n; while( lo <= hi) { int mid = (lo + hi)/2; if(query(1,1,n,i,mid) >= mx) { ans = mid; hi = mid-1; res = min(res, ans-i+1); } else { lo = mid + 1; } } } printf("%lld\n", res); return 0; }
