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

Create a socket for HTTP for web page upload and download

Create a socket for HTTP for web page upload and download. Aim: To write a java program for socket for HTTP for web page upload and download . Algorithm 1.Start the program. 2.Get the frame size from the user 3.To create the frame based on the user request. 4.To send frames to server from the client side. 5.If your frames reach the server it will send ACK signal to client otherwise it will send NACK signal to client. 6.Stop the program Program : Client import javax.swing.*; import java.net.*; import java.awt.image.*; import javax.imageio.*; import java.io.*; import java.awt.image.BufferedImage; import java.io.ByteArrayOutputStream; import java.io.File; import java.io.IOException; import javax.imageio.ImageIO; public class Client{ public static void main(String args[]) throws Exception{ Socket soc; BufferedImage img = null; soc=new Socket("localhost",4000); System.out.println("Client is running. ");  try { System.out.println("Reading image from disk. "); im...
Post a Comment
Read more

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

Write program to find ε – closure of all states of any given NFA with ε transition.

 Write program to find ε – closure of all states of any given NFA with ε transition. Agenda 1.Program 2.Input/Output 1.Program #include <stdio.h> #include <string.h> char  result[ 20 ][ 20 ], copy[ 3 ], states[ 20 ][ 20 ]; void  add_state( char  a[ 3 ],  int  i) {   strcpy(result[i], a); } void  display( int  n) {    int  k =  0 ;   printf( "nnn Epsilon closure of %s = { " , copy);    while  (k < n) {     printf( " %s" , result[k]);     k++;   }   printf( " } nnn" ); } int  main() {   FILE * INPUT;   INPUT = fopen( "input.dat" ,  "r" );    char  state[ 3 ];    int  end, i =  0 , n, k =  0 ;  ...
Post a Comment
Read more