Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<fstream>
- #include<algorithm>
- #include<iterator>
- #include<vector>
- #include<string>
- #include<sstream>
- #include<set>
- #include<deque>
- using namespace std;
- #define FOR(i,v,n) for(ll i=v;i<n;++i)
- using namespace std;
- typedef long long ll;
- #define MAX 100001
- vector<ll> arr(MAX);
- vector<ll> stree;
- void create_stree(int i,int a,int b)
- {
- if(a==b)
- {
- stree[i]=arr[a];
- return;
- }
- create_stree(2*i+1,a,(a+b)/2);
- create_stree(2*i+2,(a+b)/2+1,b);
- stree[i]=min(stree[2*i+1],stree[2*i+2]);
- }
- void process2()
- {
- create_stree(0,0,arr.size()-1);
- }
- ll query2(ll i,ll j,ll a=0,ll b=arr.size()-1,ll t=0)
- {
- if(i>b || j<a) return -1;
- if(i<=a && j>=b) return stree[t];
- ll p=query2(i,j,a,(a+b)/2,2*t+1);
- ll q=query2(i,j,(a+b)/2+1,b,2*t+2);
- if(p==-1 && q==-1) return -1;
- else if(p==-1) return q;
- else if(q==-1)return p;
- else return min(p,q);
- }
- int main()
- {
- ll t;
- cin>>t;
- stree.resize(4*MAX);
- ll n,q;
- FOR(i,0,t)
- {
- cin>>n>>q;
- FOR(j,0,n)
- cin>>arr[j];
- process2();
- cout<<"Case "<<i+1<<":\n";
- ll l,r;
- FOR(j,0,q)
- {
- cin>>l>>r;
- cout<<query2(l-1,r-1)<<endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement