Maximizing the Function
Problem Statement :
Consider an array of binary integers (i.e., 's and 's) defined as . Let be the bitwise XOR of all elements in the inclusive range between index and index in array . In other words, . Next, we'll define another function, : Given array and independent queries, perform each query on and print the result on a new line. A query consists of three integers, , , and , and you must find the maximum possible you can get by changing at most elements in the array from to or from to . Note: Each query is independent and considered separately from all other queries, so changes made in one query have no effect on the other queries. Input Format The first line contains two space-separated integers denoting the respective values of (the number of elements in array ) and (the number of queries). The second line contains space-separated integers where element corresponds to array element . Each line of the subsequent lines contains space-separated integers, , and respectively, describing query . Output Format Print lines where line contains the answer to query (i.e., the maximum value of if no more than bits are changed).
Solution :
Solution in C :
In C :
#include <stdio.h>
#include <stdlib.h>
int a[500000],odd_sum[500000],even_sum[500000];
int main(){
int n,q,x,y,k,odd,even,i;
scanf("%d%d",&n,&q);
for(i=0;i<n;i++){
scanf("%d",a+i);
if(i){
a[i]^=a[i-1];
if(a[i]){
odd_sum[i]=odd_sum[i-1]+1;
even_sum[i]=even_sum[i-1];
}
else{
odd_sum[i]=odd_sum[i-1];
even_sum[i]=even_sum[i-1]+1;
}
}
else
if(a[i]){
odd_sum[i]=1;
even_sum[i]=0;
}
else{
odd_sum[i]=0;
even_sum[i]=1;
}
}
while(q--){
scanf("%d%d%d",&x,&y,&k);
if(k)
printf("%lld\n",(y-x+2)/2*((long long)(y-x+3)/2));
else{
odd=odd_sum[y];
even=even_sum[y];
if(x){
odd-=odd_sum[x-1];
even-=even_sum[x-1];
}
if(!x || !a[x-1])
printf("%lld\n",odd*(long long)(even+1));
else
printf("%lld\n",even*(long long)(odd+1));
}
}
return 0;
}
Solution in C++ :
In C++ :
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }
int main() {
int n; int q;
while(~scanf("%d%d", &n, &q)) {
vector<int> a(n);
for(int i = 0; i < n; ++ i)
scanf("%d", &a[i]);
vector<int> sum(n + 1);
rep(i, n) sum[i + 1] = sum[i] ^ a[i];
vector<int> sum2(n + 2);
rep(i, n + 1) sum2[i + 1] = sum2[i] + sum[i];
rep(ii, q) {
int x; int y; int k;
scanf("%d%d%d", &x, &y, &k), ++ y;
int cnt0 = sum2[y + 1] - sum2[x];
int cnt1 = (y + 1 - x) - cnt0;
if(cnt0 > cnt1) swap(cnt0, cnt1);
ll ans = k == 0 ? (ll)cnt0 * cnt1 :
(ll)((y + 1 - x) / 2) * ((y + 1 - x + 1) / 2);
printf("%lld\n", ans);
}
}
return 0;
}
Solution in Java :
In Java :
import java.io.*;
import java.util.*;
public class C {
BufferedReader br;
PrintWriter out;
StringTokenizer st;
boolean eof;
void solve() throws IOException {
int n = nextInt();
int q = nextInt();
int[] b = new int[n + 1];
for (int i = 0; i < n; i++) {
int x = nextInt();
b[i + 1] = b[i] ^ x;
}
int[] c = new int[n + 2];
for (int i = 0; i < n + 1; i++) {
c[i + 1] = c[i] + b[i];
}
while (q-- > 0) {
int x = nextInt();
int y = nextInt();
int k = nextInt();
int len = y - x + 2;
int ones;
if (k == 0) {
ones = c[y + 2] - c[x];
} else {
ones = len / 2;
}
out.println((long)ones * (len - ones));
}
}
C() throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(System.out);
solve();
out.close();
}
public static void main(String[] args) throws IOException {
new C();
}
String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
eof = true;
return null;
}
}
return st.nextToken();
}
String nextString() {
try {
return br.readLine();
} catch (IOException e) {
eof = true;
return null;
}
}
int nextInt() throws IOException {
return Integer.parseInt(nextToken());
}
long nextLong() throws IOException {
return Long.parseLong(nextToken());
}
double nextDouble() throws IOException {
return Double.parseDouble(nextToken());
}
}
Solution in Python :
In Python3 :
#!/usr/bin/python3
def init(A,n):
retA = [0]*(n+1);
B = [0]*(n+1)
tmp = 0
for i in range(n):
tmp ^= A[i]
B[i+1] = tmp
retA[i+1] += retA[i] + tmp
return retA,B
if __name__ == "__main__":
n,q = list(map(int,input().rstrip().split()))
A = list(map(int,input().rstrip().split()))
newA, B = init( A, n )
while q > 0 :
x,y,k = list(map(int,input().rstrip().split()))
num = newA[y+1] - newA[x]
if B[x]:
num = (y + 1 - x) - num
size = y - x + 2
num = abs(int(size/2)) if k else num
print( num*(size-num) )
q-=1
View More Similar Problems
Inserting a Node Into a Sorted Doubly Linked List
Given a reference to the head of a doubly-linked list and an integer ,data , create a new DoublyLinkedListNode object having data value data and insert it at the proper location to maintain the sort. Example head refers to the list 1 <-> 2 <-> 4 - > NULL. data = 3 Return a reference to the new list: 1 <-> 2 <-> 4 - > NULL , Function Description Complete the sortedInsert function
View Solution →Reverse a doubly linked list
This challenge is part of a tutorial track by MyCodeSchool Given the pointer to the head node of a doubly linked list, reverse the order of the nodes in place. That is, change the next and prev pointers of the nodes so that the direction of the list is reversed. Return a reference to the head node of the reversed list. Note: The head node might be NULL to indicate that the list is empty.
View Solution →Tree: Preorder Traversal
Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's
View Solution →Tree: Postorder Traversal
Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the
View Solution →Tree: Inorder Traversal
In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func
View Solution →Tree: Height of a Binary Tree
The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary
View Solution →
