PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: manasagarwal12, luvkansal29
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
Prefix sums, sweep line, segment tree/fenwick tree
PROBLEM:
An array is called dominating if every prefix and every suffix of it has a majority element.
Given an array A, count the number of its subarrays that are dominating.
EXPLANATION:
Recall from the solution to the easy version that an array is dominating if and only if:
- It has a majority element, say M.
- M must be the majority element on every prefix and every suffix of A.
Let’s now move to counting subarrays.
We want to count subarrays which start and end with the same element, and that element dominates every prefix and suffix.
Let’s fix an element x, and try to count the subarrays for which x is the majority element satisfying this condition.
Now, suppose we fix an index L such that A_L = x to be the left endpoint of the subarray, and try to find all valid right endpoints R.
Suppose R_0 \geq L is the first index at which the prefix condition “breaks”, i.e. the subarray A[L\ldots R_0] doesn’t have x as its majority element.
Then, observe that any R \geq R_0 will certainly be an invalid right endpoint for L as well so we can discard all of them.
However, we can’t say anything about every R \lt R_0 quite yet: we know that every prefix condition is satisfied for them, but we don’t know anything about the suffix conditions yet.
But, notice that the same reasoning can be applied by fixing the right endpoint instead, i.e. if R is fixed there will be some L_0 \leq R such that the suffix condition ending at R breaks, and makes all L \leq L_0 invalid.
So, suppose we define \text{right}[i] to be the smallest index \geq i such that the prefix condition breaks on A[i\ldots \text{right}[i]], and similarly \text{left}[i] for the suffix condition breaking on A[\text{left}[i] \ldots i].
Then, the subarray A[L, R] is valid if and only if:
- A_L = A_R = x (recall that we’re working with only subarrays with x being the majority).
- \text{right}[L] \gt R, i.e. the prefix condition starting at L hasn’t broken till R.
- \text{left}[R] \lt L, i.e. the suffix condition ending at R hasn’t broken till L.
We now have a few things to deal with.
First, we need to be able to actually compute the values of \text{left}[i] and \text{right}[i] quickly enough.
Second, once we know them, we need to compute all valid pairs (L, R) quickly.
Computing the left and right arrays
Let’s look at how to compute \text{right}[i] for an index i.
To do this, we’ll use a trick that’s quite common when dealing with the majority element.
Consider a new array B, where B_i = +1 if A_i = x and B_i = -1 otherwise.Then, x is the majority of a subarray in A if and only if the sum of the corresponding subarray in B is positive.
So, to find \text{right}[i], what we really want to do is find the first time a subarray starting at i has non-positive sum (in B).
This is pretty easy: build the prefix sums of B and then compute the next smallest element in the prefix sum array.Now, this allows us to process all occurrences of x in linear time.
However, repeating this for every x will be too slow so we need to optimize it a bit.To do that, note that we can build the array B in a compressed form.
Specifically, suppose the occurrences of x are at indices i_1, i_2, \ldots, i_k.
Then, all the -1's between these occurrences can be compressed into their sum, to obtain an array of length at most 2k+1.We can now run the above algorithm on this compressed array, which is enough information.
Since this is now linear in the frequency of x, running it for every x leads to \mathcal{O}(N) overall, given that the sum of frequencies is N.
Computing the answer
Now that we have all the \text{left}[i] and \text{right}[i] values for occurrences of x, we need to count the number of valid pairs (L, R) as described above.
One way to do this quickly is to use a sweepline along with some additional data structure.
Let’s iterate over values of L in descending order, while maintaining the currently valid values of R we have.
When processing a value of L, first discard all R for which \text{left}[R] \geq L: they won’t be valid now, and won’t be for any smaller L either.Now, we only need to count the number of active R that are \lt \text{right}[L].
This is a standard problem, and can be done in several ways. For example:
- Use a segment tree/fenwick tree that marks currently active R with 1 and everything else with 0.
Counting the number of valid R is then just a range sum here.
To not TLE, this structure needs to be “global”, i.e. be reused across all x (which is not hard, since only indices corresponding to x will be updated when processing x - so just make sure to set them all back to 0 in the end).- In C++ specifically, the order statistics set (found in the
__gnu_pbdsnamespace) data structure can be used for a fairly short implementation.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
class Seg{
public:
vector<ll>tree;
ll N;
Seg(vector<ll> &a,ll n){
tree=vector<ll>(4*n+1);
N=n;
build(1,0,N-1,a);
}
void build(ll index,ll L,ll R,vector<ll> &a){
if(L== R)
{
tree[index]=a[L];
return ;
}
ll mid=(L+R)/2;
build(index*2,L,mid,a);
build(index*2+1,mid+1,R,a);
tree[index]=max(tree[index*2],tree[index*2+1]);
return ;
}
ll query(ll index,ll L,ll R,ll l,ll r){
if(l<=L&&R<=r)
return tree[index];
if(l>R||L>r)
return -1e9;
ll mid=(L+R)/2;
return max(query(index*2,L,mid,l,r),query(index*2+1,mid+1,R,l,r));
}
void upd(ll index,ll L,ll R,ll i,ll val){
if(L== R)
{
tree[index]=val;
return ;
}
ll mid=(L+R)/2;
if(mid>=i)
upd(index*2,L,mid,i,val);
else
upd(index*2+1,mid+1,R,i,val);
tree[index]=max(tree[index*2],tree[index*2+1]);
return ;
}
};
vector<ll>a(2e5+1,-1e9);
Seg sg=Seg(a,2e5+1);
int solve(int a[],int n){
vector<int>vis(n,0);
map<int,vector<int> >mp;
long long ans=0;
for(int i=0;i<n;i++){
if(vis[i]==1)
continue;
mp.clear();
int j=i+1;
int c=1;
vector<int>b(1,0);
b.push_back(1);
mp[1].push_back(i);
sg.upd(1,0,sg.N-1,i,1);
while(j<n&&c!=0){
int p=0;
if(a[i]==a[j])
{c++;
p=1;
vis[j]=1;
}
else
c--;
mp[c].push_back(j);
sg.upd(1,0,sg.N-1,j,c);
b.push_back(b.back()+p);
j++;
}
j--;
int io=j;
int u=0;
//mp[c-1].push_back(j);
map<int,vector<int> >::iterator it;
for(it=mp.begin();it!=mp.end();it++){
reverse(it->second.begin(),it->second.end());
}
u+=sg.query(1,0,sg.N-1,i,io);
// cout<<sg.query(1,0,sg.N-1,i,io)<<endl;
sg.upd(1,0,sg.N-1,i,0);
c=1;
j=i+1;
mp[c].pop_back();
while(j<=io&&c!=0){
if(a[i]==a[j]){
c++;
int ind1;
if(mp[c-1].empty())
ind1=io;
else
ind1=mp[c-1].back();
u+=sg.query(1,0,sg.N-1,j,ind1)-c+1;
// cout<<sg.query(1,0,sg.N-1,j,ind1)-c+1<<" "<<j<<" "<<ind1<<endl;
}
else
c--;
sg.upd(1,0,sg.N-1,j,0);
mp[c].pop_back();
j++;
}
ans+=u;
// cout<<u<<" "<<i<<" "<<j<<endl;
}
//cout<<ans<<endl;
return ans;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--) {
int n;
cin >> n;
int a[n];
for(auto & i: a) cin >> i;
cout << solve(a, n) << endl;
}
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
template<typename T>
struct fenwick {
int n;
vector<T> tr;
int LOG = 0;
fenwick() {
}
fenwick(int n_) {
n = n_;
tr = vector<T>(n + 1);
while((1<<LOG) <= n) LOG++;
}
int lsb(int x) {
return x & -x;
}
void pupd(int i, T v) {
for(; i <= n; i += lsb(i)){
tr[i] += v;
}
}
T sum(int i) {
T res = 0;
for(; i; i ^= lsb(i)){
res += tr[i];
}
return res;
}
T query(int l, int r) {
if (l > r) return 0;
T res = sum(r) - sum(l - 1);
return res;
}
int lower_bound(T s){
// first pos with sum >= s
if(sum(n) < s) return n+1;
int i = 0;
rev(bit,LOG-1,0){
int j = i+(1<<bit);
if(j > n) conts;
if(tr[j] < s){
s -= tr[j];
i = j;
}
}
return i+1;
}
int upper_bound(T s){
return lower_bound(s+1);
}
};
void solve(int test_case){
ll n; cin >> n;
vector<ll> a(n+5);
rep1(i,n) cin >> a[i];
map<ll,vector<ll>> mp;
rep1(i,n) mp[a[i]].pb(i);
vector<ll> lx(n+5,1), rx(n+5,n);
ll ans = 0;
fenwick<ll> fenw(n+5);
for(auto [x,pos] : mp){
vector<array<ll,3>> v;
ll siz = sz(pos);
rep(ind,siz){
v.pb({pos[ind],pos[ind],1});
if(ind+1 < siz){
ll l = pos[ind], r = pos[ind+1];
l++, r--;
if(l <= r){
v.pb({l,r,-(r-l+1)});
}
}
}
// compute lx[i]
{
stack<pll> stk;
ll bal = 0;
reverse(all(v));
for(auto [l,r,val] : v){
if(val > 0){
stk.push({l,bal});
}
bal += val;
while(!stk.empty() and bal <= stk.top().ss){
lx[stk.top().ff] = l;
stk.pop();
}
}
reverse(all(v));
}
// compute rx[i]
{
stack<pll> stk;
ll bal = 0;
for(auto [l,r,val] : v){
if(val > 0){
stk.push({l,bal});
}
bal += val;
while(!stk.empty() and bal <= stk.top().ss){
rx[stk.top().ff] = r;
stk.pop();
}
}
}
priority_queue<pll,vector<pll>,greater<pll>> pq;
trav(i,pos){
pq.push({rx[i],i});
fenw.pupd(i,1);
while(!pq.empty()){
auto [rxv,j] = pq.top();
if(rxv < i){
fenw.pupd(j,-1);
pq.pop();
}
else{
break;
}
}
ans += fenw.query(lx[i],n);
}
while(!pq.empty()){
auto [rxv,j] = pq.top();
pq.pop();
fenw.pupd(j,-1);
}
/*
rep(ind1,siz){
for(int ind2 = ind1+1; ind2 < siz; ++ind2){
ll l = pos[ind1], r = pos[ind2];
if(rx[l] >= r and lx[r] <= l){
ans++;
}
}
}
*/
}
cout << ans << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}