Skip to main content

CSES Range Queries Problem Set Solution

1.Range Sum Queries I CSES problemset solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define str string
#define pb push_back
#define vc vector
#define ci cin
#define co cout

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n,q;
cin>>n>>q;
ll dp[n+100],a[n+10];
dp[0]=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(i==1)
dp[i]=a[i];
else
dp[i]=dp[i-1]+a[i];
}
while(q--)
{
ll l,r;
cin>>l>>r;
cout<<dp[r]-dp[l-1]<<"\n";
}
}



2.Range Minimum Queries I CSES PROBLEMSET SOLUTION

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define str string
#define pb push_back
#define vc vector
#define ci cin
#define co cout
ll rmq[1000000],a[1000000];

ll build_rmq(ll idx,ll st,ll en)
{
if(st==en)
return rmq[idx]=a[st];
else
{
ll mid=(st+en)/2;
return rmq[idx]=min(build_rmq(2*idx,st,mid),build_rmq(2*idx+1,mid+1,en));
}
}
ll query(ll st,ll en,ll l,ll r,ll idx)
{
if(l<=st&&r>=en)
return rmq[idx];
if(l>en||r<st)
{
return INT_MAX;
}
//2.Partial overlap
ll mid=(st+en)/2;
return min(query(st,mid,l,r,2*idx),query(mid+1,en,l,r,2*idx+1));
}
int main()
{
 
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>a[i];
build_rmq(1,0,n-1);
while(m--)
{
ll l,r;
cin>>l>>r;
l--;
r--;
cout<<query(0,n-1,l,r,1)<<"\n";
}
}

3.Range Sum Queries II CSES PROBLEMSET SOLUTION

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define str string
#define pb push_back
#define vc vector
#define ci cin
#define co cout
ll rmq[1000000],a[1000000];
ll build_rmq(ll idx,ll st,ll en)
{
if(st==en)
return rmq[idx]=a[st];
else
{
ll mid=(st+en)/2;
return rmq[idx]=(build_rmq(2*idx,st,mid)+build_rmq(2*idx+1,mid+1,en));
}
}
ll query(ll st,ll en,ll l,ll r,ll idx)
{
if(l<=st&&r>=en)
return rmq[idx];
if(l>en||r<st)
{
return 0;
}
//2.Partial overlap
ll mid=(st+en)/2;
return (query(st,mid,l,r,2*idx)+query(mid+1,en,l,r,2*idx+1));
}
void update(ll st,ll en,ll i,ll idx,ll diff)
{
if(i<st||i>en)
return;
rmq[idx]=rmq[idx]+diff;
if(st!=en)
{ ll mid=(st+en)/2;
update(st,mid,i,2*idx,diff);
update(mid+1,en,i,2*idx+1,diff);
}
}
 
int main()
{
 
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>a[i];
build_rmq(1,0,n-1);
while(m--)
{
ll t;
cin>>t;
if(t==1)
{
ll k,u;
cin>>k>>u;
ll diff=u-a[k-1];
a[k-1]=u;
k--;
update(0,n-1,k,1,diff);
}
else
{
ll l,r;
cin>>l>>r;
l--;
r--;
cout<<query(0,n-1,l,r,1)<<"\n";
}
}
}

4.Range Minimum Queries II CSES PROBLEMSET SOLUTION

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define str string
#define pb push_back
#define vc vector
#define ci cin
#define co cout
ll rmq[1000000],a[1000000];
ll build_rmq(ll idx,ll st,ll en)
{
if(st==en)
return rmq[idx]=a[st];
else
{
ll mid=(st+en)/2;
return rmq[idx]=min(build_rmq(2*idx,st,mid),build_rmq(2*idx+1,mid+1,en));
}
}
ll query(ll st,ll en,ll l,ll r,ll idx)
{
if(l<=st&&r>=en)
return rmq[idx];
if(l>en||r<st)
{
return INT_MAX;
}
ll mid=(st+en)/2;
return min(query(st,mid,l,r,2*idx),query(mid+1,en,l,r,2*idx+1));
}
void update(ll st,ll en,ll i,ll value,ll idx)
{
if(i<st||i>en)
return ;
if(st==en)
{ rmq[idx]=value;
return;
}
ll mid=(st+en)/2;
update(st,mid,i,value,2*idx);
update(mid+1,en,i,value,2*idx+1);
rmq[idx]=min(rmq[2*idx],rmq[2*idx+1]);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>a[i];
build_rmq(1,0,n-1);
while(m--)
{
ll t;
cin>>t;
if(t==1)
{ ll k,u;
cin>>k>>u;
update(0,n-1,k-1,u,1);
 
}
else
{ ll l,r;
cin>>l>>r;
l--,r--;
cout<<query(0,n-1,l,r,1)<<"\n";
}
}
}

5.Range Xor Queries CSES PROBLEMSET SOLUTION

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define str string
#define pb push_back
#define vc vector
#define ci cin
#define co cout
ll rmq[1000000],a[1000000];

ll build_rmq(ll idx,ll st,ll en)
{
if(st==en)
return rmq[idx]=a[st];
else
{
ll mid=(st+en)/2;
return rmq[idx]=(build_rmq(2*idx,st,mid)^build_rmq(2*idx+1,mid+1,en));
}
}
ll query(ll st,ll en,ll l,ll r,ll idx)
{
if(l<=st&&r>=en)
return rmq[idx];
if(l>en||r<st)
{
return 0;
}
ll mid=(st+en)/2;
return (query(st,mid,l,r,2*idx)^query(mid+1,en,l,r,2*idx+1));
}
void update(ll st,ll en,ll i,ll value,ll idx)
{
if(i<st||i>en)
return ;
if(st==en)
{ rmq[idx]=value;
return;
}
ll mid=(st+en)/2;
update(st,mid,i,value,2*idx);
update(mid+1,en,i,value,2*idx+1);
rmq[idx]=min(rmq[2*idx],rmq[2*idx+1]);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>a[i];
build_rmq(1,0,n-1);
while(m--)
{
ll t;
//cin>>t;
t=2;
if(t==1)
{ ll k,u;
cin>>k>>u;
update(0,n-1,k-1,u,1);
 
}
else
{ ll l,r;
cin>>l>>r;
l--,r--;
cout<<query(0,n-1,l,r,1)<<"\n";
}
}
}

6.Forest Queries CSES PROBLEMSET SOLUTION

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define str string
#define pb push_back
#define vc vector
#define ci cin
#define co cout

int main()
{
 
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n,q;
cin>>n>>q;
ll num[n+1][n+1];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
char c;
cin>>c;
num[i][j]=(c=='*'?1:0);
}
}
ll dp[n+1][n+1];
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+num[i][j];
}
}
 
while(q--)
{
ll x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
cout<<dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]<<"\n";
 
}
}

7.List Removals CSES PROBLEMSET SOLUTION


#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less
#include <iostream>
using namespace __gnu_pbds;
using namespace std;
#define ll long long int
template<class T> using oset=tree<T,null_type,less<T>,
rb_tree_tag,tree_order_statistics_node_update>;
 
 
// Driver code
int main()
{
oset<array<ll,2>>p;
ll n;
cin>>n;
for(int i=0;i<n;i++)
{
ll x;
cin>>x;
p.insert({i,x});
}
for(int i=0;i<n;i++)
{
ll x;
cin>>x;
x--;
auto it=p.find_by_order(x);
cout<<(*it)[1]<<" ";
p.erase(it);
}
 
return 0;
}


Comments

Post a Comment

Popular posts from this blog

Write a code simulating ARP /RARP protocols

   Write a code simulating ARP /RARP protocols . Aim:        To write a java program for simulating ARP/RARP protocols ALGORITHM: server 1. Create a server socket and bind it to port. 2. Listen for new connection and when a connection arrives, accept it. 3. Send server ‟ s date and time to the client. 4. Read client ‟ s IP address sent by the client. 5. Display the client details. 6. Repeat steps 2-5 until the server is terminated. 7. Close all streams. 8. Close the server socket. 9. Stop. Client 1. Create a client socket and connect it to the server ‟ s port number. 2. Retrieve its own IP address using built-in function. 3. Send its address to the server. 4. Display the date & time sent by the server. 5. Close the input and output streams. 6. Close the client socket. 7. Stop. Program Program for Address Resolutuion Protocol (ARP) using TCP Client: import java.io.*; import java.net.*; impor...
Post a Comment
Read more

The Future of Web Development: Why Next.js is Going Viral

  Are you ready to level up your web development game? Look no further than Next.js, the latest sensation in the world of web development that's taking the industry by storm. With its powerful features, flexibility, and performance optimizations, Next.js is becoming the go-to framework for building modern web applications. In this blog post, we'll explore why Next.js is going viral and how it's changing the landscape of web development. Supercharged Performance: One of the main reasons why Next.js is making waves is its superior performance capabilities. With built-in optimizations like automatic static site generation (SSG) and server-side rendering (SSR), Next.js allows you to create blazing-fast web applications that load quickly and deliver seamless user experiences. This is especially important in today's fast-paced digital world, where users demand instant gratification and have little patience for slow-loading websites. Flexibility and Scalability: Next.js provid...
Post a Comment
Read more

Importants Links of Leetcode

  Here are all the important discussion posts which contain brief descriptions about a topic with its problem list. Recursion:- A.   https://leetcode.com/tag/recursion/discuss/1733447/Become-Master-In-Recursion Binary Tree and Binary Search Tree:- A.   https://leetcode.com/tag/binary-tree/discuss/1212004/Binary-Trees-study-guide B.   https://leetcode.com/tag/binary-tree/discuss/1820334/Become-Master-in-Tree C.   https://leetcode.com/tag/binary-tree/discuss/1094690/Views-and-Traversal-of-binary-tree-or-Important-topics-or-Must-Read-%3A- ) Dynamic Programming:- A.   https://leetcode.com/discuss/study-guide/458695/Dynamic-Programming-Patterns B.   https://leetcode.com/tag/dynamic-programming/discuss/1437879/Dynamic-Programming-Patterns C.   https://leetcode.com/tag/dynamic-programming/discuss/662866/DP-for-Beginners-Problems-or-Patterns-or-Sample-Solutions D.   https://leetcode.com/tag/dynamic-programming/discuss/1050391/Must-do-Dynamic-programm...
Post a Comment
Read more