PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Yuriy Fedorov
Tester: Rahul Dugar
Editorialist: Aman Dwivedi
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Segment Tree, Binary Search
PROBLEM:
You are given array A_1,A_2,…,A_n. You have to process queries of two types:
- Find the number of students who cut in line if the array of discontent is [A_l, A_{l+1},…, A_r] - that is, the subsegment of the array A;
- Add a number W to [A_l,a_{l+1},…,A_r] - that is, the subsegment of the array A.
You also have to find the number of students who cut in line using the initial aa as an array of discontent.
EXPLANATION:
Subtask 1:
Here q=0
The student that enters the queue, at last, will have the value of discontent 0, as after that no student is going to enter the queue. Also, all the students that are the right to this student will have the discontent value greater than 0. As their discontent value will increase by 1.
Hence, we can make a conclusion that the rightmost index whose value is 0 is the person that enters last in the queue. Also, observe that if the last student is at the end of the queue then this student didn’t cut the line.
Now we will remove the last student from our queue and decrement 1 from every student right to it. We will keep doing it till there is no student left in the queue.
Time Complexity
O(N*log(N))
Solution
#include <iostream>
#include <vector>
using namespace std;
struct SegTree {
vector<int> t, mod;
int sz = 1, n;
void build(int v, int l, int r, vector<int> &a) {
if (r - l == 1) {
t[v] = a[l];
return;
}
int m = (l + r) / 2;
build(v * 2 + 1, l, m, a);
build(v * 2 , m, r, a);
t[v] = min(t[v * 2 + 1], t[v * 2]);
}
void push(int v) {
t[v * 2 + 1] += mod[v];
t[v * 2] += mod[v];
mod[v * 2 + 1] += mod[v];
mod[v * 2] += mod[v];
mod[v] = 0;
}
int get_first_zero(int v, int l, int r) {
if (r <= l || t[v] > 0)
return -1;
if (r - l == 1)
return l;
push(v);
int m = (l + r) / 2;
int res = get_first_zero(v * 2, m, r);
if (res == -1)
res = get_first_zero(v * 2 + 1, l, m);
return res;
}
int get_first() {
return get_first_zero(1, 0, n);
}
int get_val(int v, int l, int r, int L, int R) {
if (r <= L || R <= l)
return 1e9;
if (L <= l && r <= R)
return t[v];
push(v);
int m = (l + r) / 2;
return min(get_val(v * 2 + 1, l, m, L, R), get_val(v * 2, m, r, L, R));
}
void update(int v, int l, int r, int L, int R, int val) {
if (r <= L || R <= l)
return;
if (L <= l && r <= R) {
t[v] += val;
mod[v] += val;
return;
}
push(v);
int m = (l + r) / 2;
update(v * 2 + 1, l, m, L, R, val);
update(v * 2, m, r, L, R, val);
t[v] = min(t[v * 2 + 1], t[v * 2]);
}
void update(int l, int r, int val) {
update(1, 0, n, l, r, val);
}
int get_val(int l, int r) {
return get_val(1, 0, n, l, r);
}
SegTree(int _n, vector<int> a) {
while (sz <= 2 * _n)
sz *= 2;
n = _n;
t.resize(sz);
mod.resize(sz);
build(1, 0, n, a);
}
};
int solve(int n, vector<int> a) {
SegTree val(n, a);
vector<int> tmp(n);
for (int i = 0; i < n; ++i)
tmp[i] = i;
SegTree num(n, tmp);
int pos = val.get_first_zero(1, 0, n);
int ans = 0;
int now_size = n;
while (pos != -1 && now_size > -2) {
if (num.get_val(pos, pos + 1) != now_size - 1)
++ans;
val.update(pos, pos + 1, 1e9 + 228);
val.update(1, 0, n, pos + 1, n, -1);
num.update(pos + 1, n, -1);
--now_size;
pos = val.get_first_zero(1, 0, n);
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
cout << solve(n, a) << '\n';
int q;
cin >> q;
while (q--) {
int t, l, r;
cin >> t >> l >> r;
if (t == 1) {
vector<int> b;
for (int i = l - 1; i < r; ++i)
b.push_back(a[i]);
cout << solve(b.size(), b) << '\n';
} else {
int val;
cin >> val;
for (int i = l - 1; i < r; ++i)
a[i] += val;
}
}
}
Subtask 2:
Let’s go from right to the left, maintaining maximum discontent (x). It is clear that the last student got up correctly, then val = a[n]. Now if the (n-1)^{th} student enters the queue correctly then the value of a[n-1] should be the same as that of a[n]. But what if the (n-1)^{th} student enters the queue by cutting the line then it will increase the discontent value of n^{th} student.
Hence we say that, if a[n-1] < x, then (n-1)^{th} person got up incorrectly. Also, we decrease our x by 1. (since we took into account one who did not get up correctly), otherwise, he got up correctly and val = a[n-1], We repeat the process till we reach the leftmost end of an array.
From this solution, it is easy to show the following fact: Let c_i = a_i - i. Then the answer is the number i : i > a_j, for all j > i.
Time Complexity
O(N*Q)
Solution
#include <iostream>
#include <vector>
using namespace std;
int solve(int n, vector<int> a) {
int val = a.back();
int ans = 0;
for (int i = n - 2; i >= 0; --i) {
if (a[i] < val)
--val, ++ans;
else
val = a[i];
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
cout << solve(n, a) << '\n';
int q;
cin >> q;
while (q--) {
int t, l, r;
cin >> t >> l >> r;
if (t == 1) {
vector<long long> b;
for (int i = l - 1; i < r; ++i)
b.push_back(a[i]);
cout << solve(b.size(), b) << '\n';
} else {
int val;
cin >> val;
for (int i = l - 1; i < r; ++i)
a[i] += val;
}
}
}
Subtask 3:
We can make sqrt decompositions.
-
We will store all the maxima in the block in sorted order. We will go to the left and will apply a binary search in the block.
-
Updates can be easily done by rebuilding the side bocks and adding W to every block in between.
Time Complexity
O (N * sqrt(N * log(N)))
Solution
#include <iostream>
#include <vector>
#include <algorithm>
#define all(a) a.begin(), a.end()
using namespace std;
const int K = 650;
const int N = 1e5 + K + 228;
const int INF = 1e9 + 228;
vector<int> records[N / K];
int add[N / K];
int A[N];
int n;
void build(int k) {
int last_max = -INF;
records[k].clear();
for (int i = min((k + 1) * K - 1, n - 1); i >= k * K; --i) {
if (A[i] > last_max) {
records[k].push_back(A[i]);
last_max = A[i];
}
}
}
int get(int l, int r) {
int last_max = -INF;
int ans = r - l + 1;
while (r >= l) {
if (r % K == K - 1 && r - K + 1 >= l) {
ans -= (records[r / K].end() - upper_bound(all(records[r / K]), last_max - add[r / K]));
if (records[r / K].size())
last_max = max(last_max, records[r / K].back() + add[r / K]);
r -= K;
} else {
if (A[r] + add[r / K] > last_max)
last_max = A[r] + add[r / K], --ans;
--r;
}
}
return ans;
}
void update(int l, int r, int val) {
while (l < r) {
if (l % K == 0 && l + K <= r) {
add[l / K] += val, l += K;
} else {
int nxt = min(l - l % K + K, r);
for (int j = l; j < nxt; ++j)
A[j] += val;
build(l / K);
l = nxt;
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> A[i];
A[i] -= i;
}
for (int i = 0; i < n; i += K)
build(i / K);
cout << get(0, n - 1) << '\n';
int q;
cin >> q;
while (q--) {
int t, l, r;
cin >> t >> l >> r;
if (t == 1) {
cout << get(l - 1, r - 1) << '\n';
} else {
int val;
cin >> val;
update(l - 1, r, val);
}
}
}
Subtask 4:
Author's Sketch
We implement the query(v, w) function - the number of maxima is greater than w. ($cnt[v]# - count maximum on segment, max[v] - maximum in segment). If max[v->R] > w, then we do not care what is in the left segment (we took it into account at the vertex). Then query(v, w) = query(v - >r, w) + cnt[v] - cnt[v - >r] (count maximum in left son) If max[v->R] <= w, then there are no suitable maxima at this vertex, then query(v, w) = query(v->l, w). With this function, it is easy to combine the segment, and therefore respond to the segment. And the modifier on the segment is a regular push in SegmentTree.
TIME COMPLEXITY:
O(Q*log^2 N)
SOLUTIONS:
Setter
#include <iostream>
#include <vector>
using namespace std;
const int N = (1 << 19);
pair<int, int> t[2 * N];
int mod[2 * N];
bool its_list[2 * N];
void push(int v) {
t[v * 2 + 1].second += mod[v];
t[v * 2].second += mod[v];
mod[v * 2 + 1] += mod[v];
mod[v * 2] += mod[v];
mod[v] = 0;
}
int query(int v, int w) {
if (its_list[v]) {
if (t[v].second > w)
return 1;
return 0;
}
push(v);
int r = v * 2, l = v * 2 + 1;
if (t[r].second <= w)
return query(l, w);
else
return query(r, w) + t[v].first - t[r].first;
}
void update(int v, int l, int r, int L, int R, int val) {
if (R <= l || r <= L)
return;
if (L <= l && r <= R) {
t[v].second += val;
mod[v] += val;
return;
}
push(v);
int m = (l + r) / 2;
update(v * 2 + 1, l, m, L, R, val);
update(v * 2, m, r, L, R, val);
t[v].first = t[v * 2].first + query(v * 2 + 1, t[v * 2].second);
t[v].second = max(t[v * 2 + 1].second, t[v * 2].second);
}
void build(int v, int l, int r, vector<int> &a) {
if (r - l == 1) {
its_list[v] = 1;
t[v] = make_pair(1, a[l]);
return;
}
int m = (l + r) / 2;
build(v * 2 + 1, l, m, a);
build(v * 2, m, r, a);
t[v].first = t[v * 2].first + query(v * 2 + 1, t[v * 2].second);
t[v].second = max(t[v * 2 + 1].second, t[v * 2].second);
}
pair<int, int> get(int v, int l, int r, int L, int R, int max_val) { // ans, max_val
if (R <= l || r <= L)
return {0, max_val};
if (L <= l && r <= R)
return {query(v, max_val), max(t[v].second, max_val)};
push(v);
int m = (l + r) / 2;
auto z1 = get(v * 2, m, r, L, R, max_val);
auto z2 = get(v * 2 + 1, l, m, L, R, z1.second);
return {z1.first + z2.first, max(z1.second, z2.second)};
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
a[i] -= i;
}
int q;
cin >> q;
build(1, 0, n, a);
cout << n - get(1, 0, n, 0, n, -n).first << '\n';
while (q--) {
int t, l, r;
cin >> t >> l >> r;
if (t == 1) {
cout << r - l + 1 - get(1, 0, n, l - 1, r, -n).first << '\n';
} else {
int val;
cin >> val;
update(1, 0, n, l - 1, r, val);
}
}
}
Tester
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
return readString(l,r,' ');
}
int a[500005];
pii tr[2000005];
int lazy[2000005];
int n;
void push(int seg){
if(lazy[seg]) {
tr[seg<<1].fi+=lazy[seg];
tr[seg<<1|1].fi+=lazy[seg];
lazy[seg<<1]+=lazy[seg];
lazy[seg<<1|1]+=lazy[seg];
lazy[seg]=0;
}
}
int get(int seg, int ll, int rr, int val) {
if(ll==rr)
return (tr[seg].fi>val);
push(seg);
if(tr[seg<<1|1].fi>val)
return get(seg<<1|1,(ll+rr)/2+1,rr,val)+tr[seg].se-tr[seg<<1|1].se;
else if(tr[seg<<1].fi>val)
return get(seg<<1,ll,(ll+rr)/2,val);
return 0;
}
void update(int seg, int ll, int rr, int l, int r, int v) {
if(ll>r||l>rr)
return;
if(l<=ll&&rr<=r) {
tr[seg].fi+=v;
lazy[seg]+=v;
return;
}
push(seg);
update(seg<<1,ll,(ll+rr)/2,l,r,v);
update(seg<<1|1,1+(ll+rr)/2,rr,l,r,v);
tr[seg].fi=max(tr[seg<<1].fi,tr[seg<<1|1].fi);
tr[seg].se=tr[seg<<1|1].se+get(seg<<1,ll,(ll+rr)/2,tr[seg<<1|1].fi);
}
int query(int seg, int ll, int rr, int l, int r, int& val) {
if(ll>r||l>rr)
return 0;
if(l<=ll&&rr<=r) {
int pp=get(seg,ll,rr,val);
val=max(tr[seg].fi,val);
return pp;
}
push(seg);
int right=query(seg<<1|1,(ll+rr)/2+1,rr,l,r,val);
return query(seg<<1,ll,(ll+rr)/2,l,r,val)+right;
}
void solve() {
n=readIntLn(3,500000);
// cin>>n;
fr(i,1,n) {
// cin>>a[i];
if(i!=n)
a[i]=readIntSp(0,n-1);
else
a[i]=readIntLn(0,n-1);
update(1,1,n,i,i,a[i]-i);
}
int pp=-n-1;
cout<<n-query(1,1,n,1,n,pp)<<endl;
int q=readIntLn(0,500000);
// int q;
// cin>>q;
while(q--) {
// int ty;
// cin>>ty;
int ty=readIntSp(1,2);
if(ty==1) {
// int l,r;
// cin>>l>>r;
pp=-n-1;
int l=readIntSp(1,n),r=readIntLn(l,n);
cout<<r-l+1-query(1,1,n,l,r,pp)<<endl;
} else {
// int l,r,w;
// cin>>l>>r>>w;
int l=readIntSp(1,n),r=readIntSp(l,n),w=readIntLn(-n+1,n-1);
update(1,1,n,l,r,w);
}
}
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(10);
// int t=readIntLn(1,100000);
int t=1;
// cin>>t;
fr(i,1,t)
solve();
#ifdef rd
cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}