PROBLEM LINK:
Setter: Anik Sarker, Ezio Auditore
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
PREREQUISITES:
Segment Tree with Lazy Propagation, Stacks.
PROBLEM:
Given a permutation P of length N, find the value of the following sum.
\sum_{i = 1}^{N}\sum_{j = i}^{N}getMin(i, j) ∧ getMax(i, j) where ∧ denotes AND operation and getMin(i, j) = min(P_i, P_{i+1} \ldots P_{j-1}, P_j) and getMax(i, j) = max(P_i, P_{i+1} \ldots P_{j-1}, P_j).
EXPLANATION
Let us solve the simpler problem instead, where instead of AND operation, we have multiplication operation.
The problem becomes the same as finding the sum of product minimum and maximum value in subarray for all subarrays.
Let us group the subarrays by their endpoints. Suppose cur hold the sum of values for subarrays ending at position p. We want to calculate the same value, for all subarrays ending at position p+1 using this. First of all, the subarray (p+1, p+1) is easy, just add P_{p+1}*P_{p+1} to cur. Now notice how minimum and maximum values are affected by extending subarrays (i, p) to (i, p+1) for 1 \leq i \leq p.
If P_p < P_{p+1}, then let us find rightmost position q such that P_q > P_{p+1}. If there’s no such position, then assume q = 0. P_{p+1} affects only the maximums for subarrays which start in range [q+1, p] and end at p. Now, for a subarray (i, j), the maximum value changes from x to y, it’s contribution to cur changes by (y-x)*min(i, j), since cur includes x*min(i, j) and we now want to include only y*min(i, j).
We want to do this for all subarrays which start in the range [q+1, p] and end at p. Also, the value of y is always P_{p+1}. Let us divide interval [q+1, p] into disjoint exhaustive set of intervals such that for any two positons a and b in same interval, getMax(a, p) = getMax(b, p) = x. For each sub-interval (l, r), we add (y-x)*sumMin(l, r) where sumMin(l, r) = \sum_{i = l}^{r} min(i, p).
For getting sumMin(l, r) we can maintain a segment tree, such that each position i currently stores getMin(i, p). When we move from position p to position p+1, we find the leftmost position q such that getMin(q, p) > P_{p+1} and assign all positions with value P_{p+1}. This is a standard application of Lazy propagation in Segment Tree which you may read about here.
For keeping a record of such intervals, a stack is a nice data structure. Suppose we consider positions from left to right and whenever we consider position p, we keep removing positions in the stack from the top, until either the stack is empty, or the element at the topmost position in P is greater than current element. After this procedure, we insert the current position into the stack. This stack holds the invariant that values at positions are always in strictly increasing order. This way, stack gives us the intervals, as well as automatically helps us to find position q.
We can similarly repeat this process where P_p > P_{p+1} where only the minimums get affected and we have another segment tree for maximum values and a stack for the minimum value positions.
This allowed us to solve the problem where we have multiplication operation.
Coming back to the original problem, we can convert the AND operation into a log(N) subproblems involving multiplication operation, handling each bit individually for the purpose of calculating the sum. For each bit, we need to maintain a separate segment tree, where bit at position i is set if the minimum (maximum) of range (i, p) has current bit set. For each bit, we have to handle updates separately.
This concludes the problem. Refer implementations in case anything is still unclear.
TIME COMPLEXITY
Counting the number of intervals made by the stack, we can see that total N insertions are made in whole process and deletions cannot exceed insertions, so they are also up to N only. The number of updates to each segment trees also do not exceed 2*N and there is log(N) segment trees and each update takes O(log(N)) time, time complexity does not exceed O(N*log^2(N)).
So time complexity is O(N*log^2(N)) per test case.
SOLUTIONS:
Setter 1 Solution
#include <bits/stdc++.h>
using namespace std;
#define LOG 18
#define MAX 100005
#define Left (node*2)
#define Right (node*2+1)
#define mid ((lo+hi)/2)
#define ll long long int
bool Check(int n,int b) {return (n>>b) & 1;}
struct SegmentTree{
int tree[MAX*5];
int lazy[MAX*5];
void Clear(){ memset(tree,0,sizeof(tree)); memset(lazy,-1,sizeof(lazy)); }
SegmentTree() {Clear();}
void lazyPropagation(int node,int lo,int hi){
if(lazy[node] != -1){
tree[node] = (hi-lo+1) * lazy[node];
if(lo != hi) {lazy[Left] = lazy[node]; lazy[Right] = lazy[node];}
lazy[node] = -1;
}
}
void updateRange(int node, int lo, int hi, int i, int j, ll val){
lazyPropagation(node,lo,hi);
if(lo>hi) return;
else if(lo>j || hi<i) return;
if(lo>=i && hi<=j) {lazy[node] = val; lazyPropagation(node,lo,hi); return;}
updateRange(Left,lo,mid,i,j,val);
updateRange(Right,mid+1,hi,i,j,val);
tree[node]= tree[Left] + tree[Right];
}
int queryRange(int node,int lo,int hi,int i,int j){
if(lo>hi) return 0;
else if(lo>j || hi<i) return 0;
lazyPropagation(node,lo,hi);
if(lo>=i && hi <= j) return tree[node];
int p1=queryRange(Left,lo,mid,i,j);
int p2=queryRange(Right,mid+1,hi,i,j);
return p1 + p2;
}
};
stack<int>Max;
stack<int>Min;
int A[MAX], B[MAX];
SegmentTree Maximum[LOG], Minimum[LOG];
int main(){
int t;
cin >> t;
while(t--){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&A[i]), B[i] = A[i];
while(Min.size() > 0) Min.pop();
while(Max.size() > 0) Max.pop();
for(int b=0;b<LOG;b++) Maximum[b].Clear(), Minimum[b].Clear();
ll Sum = 0;
ll Ans = 0;
Min.push(0); Max.push(0);
A[0] = INT_MAX, B[0] = 0;
for(int i=1;i<=n;i++){
while(A[Max.top()] < A[i]){
int x = Max.top(); Max.pop();
int y = Max.top();
for(int b=0;b<LOG;b++){
int xx = Check(A[i],b);
int yy = Check(A[x],b);
if(xx == yy) continue;
Ans += ((xx - yy) * (1LL<<b) * Minimum[b].queryRange(1,1,n,y+1,x));
Maximum[b].updateRange(1,1,n,y+1,x,xx);
}
}
while(B[Min.top()] > B[i]){
ll x = Min.top(); Min.pop();
ll y = Min.top();
for(int b=0;b<LOG;b++){
int xx = Check(B[i],b);
int yy = Check(B[x],b);
if(xx == yy) continue;
Ans += ((xx - yy) * (1LL<<b) * Maximum[b].queryRange(1,1,n,y+1,x));
Minimum[b].updateRange(1,1,n,y+1,x,xx);
}
}
Max.push(i); Min.push(i);
for(int b=0;b<LOG;b++){
Maximum[b].updateRange(1,1,n,i,i,Check(A[i],b));
Minimum[b].updateRange(1,1,n,i,i,Check(B[i],b));
}
Ans += A[i];
Sum += Ans;
}
cout<<Sum<<endl;
}
}
Setter 2 Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100009;
const int maxlogn = 17;
struct Segtree{
int tree[4 * maxn];
int lazy[4 * maxn];
void relax(int node, int beg, int ed)
{
tree[node] = lazy[node] * (ed - beg + 1);
if(beg != ed){
lazy[2 * node] = lazy[node];
lazy[2 * node + 1] = lazy[node];
}
lazy[node] = -1;
}
void build(ll node, ll beg, ll ed)
{
if(beg == ed) {
tree[node] = 0;
lazy[node] = -1;
return;
}
int mid = (beg + ed) / 2;
int lft = 2 * node;
int rgh = lft + 1;
build(lft, beg, mid);
build(rgh, mid + 1, ed);
tree[node] = tree[lft] + tree[rgh];
}
void update(int node, int beg, int ed, int i, int j, int val)
{
if(lazy[node] != -1) relax(node, beg, ed);
if(beg > ed || beg > j || ed < i) return;
if(beg >= i && ed <= j) {
lazy[node] = val;
relax(node, beg, ed);
return;
}
int mid = (beg + ed) / 2;
int lft = 2 * node;
int rgh = lft + 1;
update(lft, beg, mid, i, j, val);
update(rgh, mid + 1, ed, i, j, val);
tree[node] = tree[lft] + tree[rgh];
}
int query(int node, int beg, int ed, int i, int j)
{
if(lazy[node] != -1) relax(node, beg, ed);
if(beg > ed || beg > j || ed < i) return 0;
if(beg >= i && ed <= j) return tree[node];
int mid = (beg + ed) / 2;
int lft = 2 * node;
int rgh = lft + 1;
return query(lft, beg, mid, i, j) + query(rgh, mid + 1, ed, i, j);
}
};
int ara1[maxn], ara2[maxn];
Segtree maximum[maxlogn], minimum[maxlogn];
stack < int > stmx, stmn;
vector < int > vec;
int main()
{
// freopen("input02.txt", "r", stdin);
// freopen("output02.txt", "w", stdout);
int t, n;
cin >> t;
if(t < 1 || t > 10) assert(false);
while(t--){
cin >> n;
if(n < 1 || n > 100000) assert(false);
for(int i = 1; i <= n; i++) scanf("%d", &ara1[i]), ara2[i] = ara1[i],vec.push_back(ara1[i]);
sort(vec.begin(), vec.end());
for(int i = 0; i < vec.size(); i++) if(vec[i] != i + 1) assert(false);
vec.clear();
for(int i = 0; i < maxlogn; i++) maximum[i].build(1, 1, n), minimum[i].build(1, 1, n);
while(stmx.size()) stmx.pop();
while(stmn.size()) stmn.pop();
ara1[0] = INT_MAX, ara2[0] = 0;
ll ans = 0, curans = 0;
stmx.push(0), stmn.push(0);
for(int i = 1; i <= n; i++){
while(ara1[stmx.top()] < ara1[i]){
int id = stmx.top();
stmx.pop();
for(ll j = 0; j < maxlogn; j++){
ll koyta = minimum[j].query(1, 1, n, stmx.top() + 1, id);
bool cc1 = (ara1[id] >> (int)j) & 1;
bool cc2 = (ara1[i] >> (int)j) & 1;
if(cc1) curans -= (1LL << j) * koyta;
if(cc2) curans += (1LL << j) * koyta;
}
}
for(int j = 0; j < maxlogn; j++) {
int cc = (ara1[i] >> j) & 1;
maximum[j].update(1, 1, n, stmx.top() + 1, i, cc);
}
stmx.push(i);
while(ara2[stmn.top()] > ara2[i]){
int id = stmn.top();
stmn.pop();
for(ll j = 0; j < maxlogn; j++){
ll koyta = maximum[j].query(1, 1, n, stmn.top() + 1, id);
bool cc1 = (ara2[id] >> (int)j) & 1;
bool cc2 = (ara2[i] >> (int)j) & 1;
if(cc1) curans -= (1LL << j) * koyta;
if(cc2) curans += (1LL << j) * koyta;
}
}
for(ll j = 0; j < maxlogn; j++) {
int cc = (ara2[i] >> j) & 1;
minimum[j].update(1, 1, n, stmn.top() + 1, i, cc);
}
stmn.push(i);
curans += ara1[i] & ara2[i];
ans += curans;
}
printf("%lld\n", ans);
}
return 0;
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int seg[412345][20][3],lazy[412345][20];
int p1[123456],p2[123456];
int n;
int build(int node,int l,int r){
int i,bit;
rep(bit,20){
lazy[node][bit]=0;
rep(i,3){
seg[node][bit][i]=0;
}
seg[node][bit][0]=(r-l+1);
}
if(l==r)
return 0;
int mid=(l+r)/2;
build(2*node,l,mid);
build(2*node+1,mid+1,r);
return 0;
}
int arr[12];
int update(int node,int s,int e,int bit,int l,int r,int val){
if(lazy[node][bit]){
int i;
rep(i,3){
arr[i]=seg[node][bit][i];
seg[node][bit][i]=0;
}
rep(i,3){
if(i+lazy[node][bit]>=0 && i+lazy[node][bit]<3){
seg[node][bit][i+lazy[node][bit]]+=arr[i];
}
}
if(s!=e){
lazy[2*node][bit]+=lazy[node][bit];
lazy[2*node+1][bit]+=lazy[node][bit];
}
lazy[node][bit]=0;
}
if(r<s || e<l){
return 0;
}
if(l<=s && e<=r){
lazy[node][bit]+=val;
if(lazy[node][bit]){
int i;
rep(i,3){
arr[i]=seg[node][bit][i];
seg[node][bit][i]=0;
}
rep(i,3){
if(i+lazy[node][bit]>=0 && i+lazy[node][bit]<3){
seg[node][bit][i+lazy[node][bit]]+=arr[i];
}
}
if(s!=e){
lazy[2*node][bit]+=lazy[node][bit];
lazy[2*node+1][bit]+=lazy[node][bit];
}
lazy[node][bit]=0;
}
return 0;
}
int mid=(s+e)/2;
update(2*node,s,mid,bit,l,r,val);
update(2*node+1,mid+1,e,bit,l,r,val);
int i;
rep(i,3){
seg[node][bit][i]=seg[2*node][bit][i]+seg[2*node+1][bit][i];
}
return 0;
}
int query(int node,int s,int e,int bit,int l,int r){
if(lazy[node][bit]){
int i;
rep(i,3){
arr[i]=seg[node][bit][i];
seg[node][bit][i]=0;
}
rep(i,3){
if(i+lazy[node][bit]>=0 && i+lazy[node][bit]<3){
seg[node][bit][i+lazy[node][bit]]+=arr[i];
}
}
if(s!=e){
lazy[2*node][bit]+=lazy[node][bit];
lazy[2*node+1][bit]+=lazy[node][bit];
}
lazy[node][bit]=0;
}
if(e<l || r<s){
return 0;
}
if(l<=s && e<=r){
return seg[node][bit][2];
}
int mid=(s+e)/2;
int ans=query(2*node,s,mid,bit,l,r);
ans+=query(2*node+1,mid+1,e,bit,l,r);
return ans;
}
int remov(int l,int r,int val){
int i;
rep(i,20){
if(val&(1<<i)){
update(1,1,n,i,l,r,-1);
}
}
return 0;
}
int adder(int l,int r,int val){
int i;
rep(i,20){
if(val&(1<<i)){
//cout<<i<<" "<<l<<" "<<r<<endl;
update(1,1,n,i,l,r,1);
}
}
return 0;
}
ll getans(int l,int r){
int i;
ll val,ans=0;
rep(i,20){
val=query(1,1,n,i,l,r);
val*=(1<<i);
ans+=val;
}
return ans;
}
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
cin>>n;
int i;
build(1,1,n);
f(i,1,n+1){
cin>>p1[i];
p2[i]=p1[i];
}
p1[0]=inf;
p2[0]=0;
stack<int> st1,st2;
st1.push(0);
st2.push(0);
int gg,previ;
ll ans=0;
f(i,1,n+1){
while(!st1.empty() && p1[st1.top()]<p1[i]){
gg=st1.top();
st1.pop();
previ=st1.top();
remov(previ+1,gg,p1[gg]);
}
while(!st2.empty() && p2[st2.top()]>p2[i]){
gg=st2.top();
st2.pop();
previ=st2.top();
remov(previ+1,gg,p2[gg]);
}
adder(st1.top()+1,i,p1[i]);
adder(st2.top()+1,i,p2[i]);
st1.push(i);
st2.push(i);
ans+=getans(1,i);
}
cout<<ans<<endl;
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class MNMXAR{
//SOLUTION BEGIN
//Into the Hardware Mode
void pre() throws Exception{}
int B = 17;
void solve(int TC) throws Exception{
int n = ni();
int[] p = new int[1+n];
for(int i = 1; i<= n; i++)p[i] = ni();
long ans = 0, cur = 0;
Stack<Integer> lo = new Stack<>(), hi = new Stack<>();
LazySegTree[] min = new LazySegTree[B], max = new LazySegTree[B];
for(int i = 0; i< B; i++){
min[i] = new LazySegTree(n);
max[i] = new LazySegTree(n);
}
for(int i = 1; i<= n; i++){
while(!lo.isEmpty() && p[lo.peek()] > p[i]){
int pos = lo.pop();
int prev = (lo.isEmpty()?0:lo.peek())+1;
for(int b = 0; b< B; b++){
long coeff = ((p[i]>>b)&1) - ((p[pos]>>b)&1);
cur += coeff*max[b].sum(prev, pos)*(1l<<b);
min[b].update(prev, pos, ((p[i]>>b)&1));
}
}
while(!hi.isEmpty() && p[hi.peek()] < p[i]){
int pos = hi.pop();
int prev = (hi.isEmpty()?0:hi.peek())+1;
for(int b = 0; b< B; b++){
long coeff = ((p[i]>>b)&1) - ((p[pos]>>b)&1);
cur += coeff*min[b].sum(prev, pos)*(1l<<b);
max[b].update(prev, pos, ((p[i]>>b)&1));
}
}
for(int b = 0; b< B; b++){
min[b].update(i, i, ((p[i]>>b)&1));
max[b].update(i, i, ((p[i]>>b)&1));
}
lo.push(i);
hi.push(i);
cur += p[i]&p[i];
ans += cur;
}
pn(ans);
}
class LazySegTree{
int m = 1;
int[] sum, lazy;
public LazySegTree(int n){
while(m<=n)m<<=1;
sum = new int[m<<1];
lazy = new int[m<<1];
Arrays.fill(lazy, -1);
}
public void update(int l, int r, int val){
update(l, r, 0, m-1, 1, val);
}
public long sum(int l, int r){return sum(l, r, 0, m-1, 1);}
private void push(int i, int l, int r){
if(lazy[i] != -1){
sum[i] = lazy[i]*(r-l+1);
if(l != r){
lazy[i<<1] = lazy[i];
lazy[i<<1|1] = lazy[i];
}
lazy[i] = -1;
}
}
private void update(int l, int r, int ll, int rr, int i, int val){
if(l == ll && r == rr){
lazy[i] = val;
push(i, ll, rr);
return;
}
int mid = (ll+rr)>>1;
if(r <= mid){
update(l, r, ll, mid, i<<1, val);
push(i<<1|1, mid+1, rr);
}else if(l > mid){
push(i<<1, ll, mid);
update(l, r, mid+1, rr, i<<1|1, val);
}else{
update(l, mid, ll, mid, i<<1, val);
update(mid+1, r, mid+1, rr, i<<1|1, val);
}
lazy[i] = -1;
sum[i] = sum[i<<1]+sum[i<<1|1];
}
private int sum(int l, int r, int ll, int rr, int i){
push(i, ll, rr);
if(l == ll && r == rr)return sum[i];
int mid = (ll+rr)>>1;
if(r <= mid)return sum(l, r, ll, mid, i<<1);
else if(l > mid)return sum(l, r, mid+1, rr, i<<1|1);
else return sum(l, mid, ll, mid, i<<1)+sum(mid+1, r, mid+1, rr, i<<1|1);
}
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
long IINF = (long)1e18, mod = (long)1e9+7;
final int INF = (int)1e9, MX = (int)2e5+5;
DecimalFormat df = new DecimalFormat("0.00000000000");
double PI = 3.141592653589793238462643383279502884197169399, eps = 1e-6;
static boolean multipleTC = true, memory = false, fileIO = false;
FastReader in;PrintWriter out;
void run() throws Exception{
if(fileIO){
in = new FastReader("input.txt");
out = new PrintWriter("output.txt");
}else {
in = new FastReader();
out = new PrintWriter(System.out);
}
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
if(memory)new Thread(null, new Runnable() {public void run(){try{new MNMXAR().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
else new MNMXAR().run();
}
long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach, if you want to. (even if its same 
) . Suggestions are welcomed as always had been. 