PROBLEM LINK:
Author: Harris Leung
Tester: Yash Chandnani
Editorialist: Michael Nematollahi
DIFFICULTY:
Hard
PREREQUISITES:
Segment Trees, Min-Cost Max Flow
PROBLEM:
You are given N boxes. The i^{th} box has a value val[i] and a size size[i] associated with it.
You can choose k pairs of boxes (a_i, b_i) such that no box belongs to more than one pair and size[a_i] \ge size[b_i]. The score of this pair would be val[a_i] - val[b_j]. The score of the k chosen pairs is the sum of the score of the individual pairs.
Your task is to find the maximum score you can achieve choosing at most k pairs, for each k from 1 to N/2.
EXPLANATION:
First, sort the boxes by their sizes. If two boxes have the same size, the box with the lower value comes first. This way, in an optimal choice of k pairs, a_i > b_i for the i^{th} pair.
Construct a weighted flow graph where for each box v there are two nodes in[v] and out[v] and there are two additional nodes for the source and the sink. Add the edges described below to the graph.
- For each box v, add an edge from in[v] to out[v] with capacity 1 and weight 0.
- For each box v, add an edge from source to in[v] with capacity 1 and weight 0.
- For each box v, add an edge from out[v] to sink with capacity 1 and weight 0.
- For any pair of boxes u, v where u < v, add an edge from out[v] to in[u] with capacity 1 and weight -(val[v] - val[u]).
The problem of finding an optimal k pairs of boxes is equivalent to finding k edge-disjoint paths with minimum total weight from source to sink in the constructed graph. The latter is the MCMF (min cost max flow) problem.
A typical approach to solve the MCMF problem is to successively find a shortest path from source to root in the residual graph. While we will not talk about MCMF in our solution, it helps with proving the claims that we make. Our solution will try to efficiently simulate the process of running the mentioned algorithm.
We will find the answer for different k's successively, starting from k=1 going all the way up to k = N/2.
Let S_k refer to an optimal choice of k pairs. Assuming we have S_k, we will try to find S_{k+1}.
Let A_k refer to the set of all a_i's in S_k. Similarly we define B_k.
The total score of the chosen pairs can be represented as (\sum_{a \in A_k} val[a]) - (\sum_{b \in B_k} val[b]).
Consider a string constructed based on the boxes chosen so far in the following way:
start from v = 1 and go all the way up to v = N.
- if v \in A_k, add a ) to the end of the string.
- if v \in B_k, add a ( to the end of the string.
- If none of the above hold, add nothing to the string.
Two sets A_k and B_k are a valid pairing (ignoring the score resulting from them) iff the constructed bracket string is a valid one.
Note that just knowing A_k and B_k is enough to find the maximum score (and possibly a way to construct it, though the problem does not require this) for k pairs.
Now, let’s see how A_{k+1} and B_{k+1} can be augmented from A_k and B_k.
Claim 1: There is an optimal solution of k+1 pairs in which A_{k+1} is A_k \cup {new\_a}, where new\_a is a new box. A similar claim applies to B_{k+1} and B_k.
This claim can be proven using the changes made to the residual graph of the graph we constructed above when we try to find a new shortest path.
Assume A_{k+1} and B_{k+1} are constructed by adding new\_a and new\_b to them. To make the total score maximum, we want val[new\_a] - val[new\_b] to be maximal. There are two cases:
Case 1: new\_a > new\_b
Any pairs of such boxes can be added to A_k and B_k without disrupting the validity of the bracket sequence. So we only need to find the pair that maximizes val[new\_a] - val[new\_b].
To do so, we maintain a segment tree of the unused boxes on the array bestToLeft[v] that stores the maximum value of val[new\_a] - val[new\_b] if new\_a = v and new\_b < new\_a.
Each node of this segment tree stores the box in its range with the highest value.
After removing a box v (as in using it in a pair), we can update the segment tree like this:
- Let r be the last box having v as its bestToLeft. At the beginning, we know r and after the removal of each box, we can update r as we update the segment tree.
- The range [v, r] is the range of boxes whose bestToLeft needs to be updated.
- Let l be the unused box with the lowest value to the left of v. We can find l by using another segment tree (let’s call it “the min segment tree”).
- The range of boxes [v, r] will be updated with a combination of members of the range or l. As long as the minimum unused box in [v, r] (found using “the min segment tree”) is better than l, we’ll use it. The moment it’s not, we’ll know that l should be used to update the other members of the range. This step will take at most O(N) iterations amortized because if a member of the range updates the range, it will be the first time it does so.
- The idea above requires range addition queries on the main segment tree of this case, which are not difficult to handle.
The overall complexity of this case will be O(N \times log(n)).
Case 2: new\_a < new\_b
Consider the bracket sequence again. We’ll introduce a new array c where c[i] = 0 initially. For each opening bracket, add +1 to the c[i] of all the boxes following that box. Similarly, for each closing bracket, add -1 to the c[i] of all the boxes following that box. For new\_a and new\_b to not break the validity of the bracket sequence, we need all the boxes between them to have a positive c[i]. A box that has c[i] = 0 is called a “zero-box” (note that c[i] \ge 0 for all i, as the bracket sequence is valid).
We will build a segment tree on c. We need this segment tree to support range addition and deduction and we need it to tell us the maximum difference between the val of two boxes within its range who have no “zero-boxes” between them. We’ll have the nodes of this segment tree store the following values so it can answer the mentioned queries effectively.
- The minimum c[i] in the range of this node. (let’s call this value mn).
- The maximum difference in val between any two boxes in this range.
- The maximum difference in val between any two boxes in this range who don’t have any boxes u in between them such that c[i] = mn.
The update of this segment tree and querying it would take O(log(N)) per query or update. Hence, the complexity of this part will also be O(N \times log(N)).
To view an implementation of this solution, refer to the tester’s code.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
bool debug=false;
typedef long long ll;
const int N=2e5+1,K=2e5+1,ts=1<<20;
int n,k;
deque<ll>bs[K];
ll c[N],p[N];//capacity,prettiness
ll ord[N];
ll ans1[N],ans2[N],ans3[N],ans[N];
void gen(){
cin >> n;k=K-1;
for(int i=0; i<=k ;i++) bs[i].clear();
for(int i=1; i<=n ;i++){
cin >> c[i] >> p[i];
bs[c[i]].push_back(p[i]);
}
bs[0].push_back(689*777);
}
void solve1(){
for(int i=1; i<=n ;i++) ord[i]=(i+1)/2;
for(int i=1; i<=n ;i++) ans1[i]=0;
ll doo[11];
do{
for(int i=1; i<=n ;i++) doo[i]=0;
for(int i=1; i<=n ;i++){
if(doo[ord[i]*2-1]) doo[ord[i]*2]=i;
else doo[ord[i]*2-1]=i;
}
ll cc=0;
for(int i=1; i<=n/2 ;i++){
if(c[doo[i*2]]>c[doo[i*2-1]]) cc+=p[doo[i*2]]-p[doo[i*2-1]];
else if(c[doo[i*2]]<c[doo[i*2-1]]) cc+=p[doo[i*2-1]]-p[doo[i*2]];
else cc+=abs(p[doo[i*2-1]]-p[doo[i*2]]);
ans1[i]=max(ans1[i],cc);
}
}while(next_permutation(ord+1,ord+n+1));
for(int i=1; i<=n/2 ;i++) ans1[i]=max(ans1[i],ans1[i-1]);
}
void solve2(){
int inv[111];
for(int i=1; i<=n ;i++) inv[i]=0;
for(int i=0; i<=k ;i++) bs[i].clear();
for(int i=1; i<=n ;i++){
bs[c[i]].push_back(p[i]);
}
bs[0].push_back(689*777);
for(int i=1; i<=k ;i++) sort(bs[i].begin(),bs[i].end());
for(int r=1; r<=n/2 ;r++){
int mi=0,mj=0;
for(int i=1; i<=k ;i++){
bool ok=true;
for(int j=k; j>=1 ;j--){
if(j<i) ok&=inv[j+1]>0;
if(!ok) break;
if(bs[i].empty() || bs[j].empty()) continue;
if(bs[j].back()-bs[i].front()>bs[mj].back()-bs[mi].front()) mi=i,mj=j;
}
}
ans2[r]=ans2[r-1]+bs[mj].back()-bs[mi].front();
for(int i=1; i<=mj ;i++) inv[i]++;
for(int i=1; i<=mi ;i++) inv[i]--;
if(mi!=0){
bs[mi].pop_front();bs[mj].pop_back();
}
}
}
typedef pair<int,int> info;
#define fi first
#define se second
ll s[K],t[K];
info gmx(info x,info y){
if(t[x.se]-s[x.fi]>t[y.se]-s[y.fi]) return x;
return y;
}
int tag[ts];
info rd[ts],wdo[ts],wdw[ts];
int ms[ts],mt[ts],msw[ts],mtw[ts];
void pull(int id){
//if(debug) cout << "pull " << id << endl;
int lc=id*2,rc=id*2+1;
rd[id]=gmx(gmx(rd[lc],rd[rc]),{ms[lc],mt[rc]});
wdo[id]=gmx(gmx(wdo[lc],wdo[rc]),{ms[rc],mt[lc]});
wdw[id]={tag[rc]?ms[rc]:msw[rc],tag[lc]?mt[lc]:mtw[lc]};
wdw[id]=gmx(wdw[id],tag[rc]?wdo[rc]:wdw[rc]);
wdw[id]=gmx(wdw[id],tag[lc]?wdo[lc]:wdw[lc]);
ms[id]=s[ms[lc]]>s[ms[rc]]?ms[rc]:ms[lc];
mt[id]=t[mt[lc]]>t[mt[rc]]?mt[lc]:mt[rc];
if(tag[lc]) msw[id]=s[ms[lc]]>s[msw[rc]]?msw[rc]:ms[lc];
else msw[id]=msw[lc];
if(tag[rc]) mtw[id]=t[mt[rc]]>t[mtw[lc]]?mt[rc]:mtw[lc];
else mtw[id]=mtw[rc];
//if(debug) cout << wdw[id].fi << ' ' << wdw[id].se << endl;
//if(debug) cout << msw[id] << ' ' << mtw[id] << endl;
}
void updt(int id,int l,int r,int ql,int qr,int t){
if(l>=qr || r<=ql){
if(tag[id]>0 && tag[id^1]>0){
//if(debug) cout << "Oh GG! " << id << endl;
int mi=min(tag[id],tag[id^1]);
tag[id]-=mi;tag[id^1]-=mi;
tag[id/2]+=mi;
}
return;
}
if(ql<=l && r<=qr) tag[id]+=t;
else{
int mid=(l+r)/2;
//if(debug) cout << "Russian roulette! " << id << ' ' << tag[id] << endl;
tag[id*2]+=tag[id];tag[id*2+1]+=tag[id];tag[id]=0;
updt(id*2,l,mid,ql,qr,t);
tag[id*2]+=tag[id];tag[id*2+1]+=tag[id];tag[id]=0;
updt(id*2+1,mid,r,ql,qr,t);
}
if(tag[id]>0 && tag[id^1]>0){
//if(debug) cout << "Oh GG! " << id << endl;
int mi=min(tag[id],tag[id^1]);
tag[id]-=mi;tag[id^1]-=mi;
tag[id/2]+=mi;
}
if(ql>l || r>qr) pull(id);
}
void updv(int id,int l,int r,int p){
if(l>p || r<p) return;
if(r==l+1){
rd[id]=gmx(gmx({l,l},{r,r}),{l,r});
wdo[id]={r,l};
wdw[id]={0,0};
ms[id]=s[l]>s[r]?r:l;
mt[id]=t[l]>t[r]?l:r;
msw[id]=l;
mtw[id]=r;
}
else{
int mid=(l+r)/2;
updv(id*2,l,mid,p);
updv(id*2+1,mid,r,p);
pull(id);
}
}
void build(int id,int l,int r){
tag[id]=0;
if(r==l+1){
rd[id]=gmx(gmx({l,l},{r,r}),{l,r});
wdo[id]={r,l};
wdw[id]={0,0};
ms[id]=s[l]>s[r]?r:l;
mt[id]=t[l]>t[r]?l:r;
msw[id]=l;
mtw[id]=r;
}
else{
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid,r);
pull(id);
}
}
void flush(int id,int l,int r){
cout << id << ' ' << l << ' ' << r << ' ' << tag[id] << '\n';
if(r==l+1);
else{
int mid=(l+r)/2;
flush(id*2,l,mid);
flush(id*2+1,mid,r);
}
}
void solve3(){
if(k==1) k++;
for(int i=1; i<=k ;i++) sort(bs[i].begin(),bs[i].end());
for(int i=1; i<=k ;i++){
if(bs[i].empty()) s[i]=1e18,t[i]=-1e18;
else s[i]=bs[i].front(),t[i]=bs[i].back();
}
build(1,1,k);
for(int i=1; i<=n/2 ;i++) ans[i]=0;
for(int i=1; i<=n/2 ;i++){
//if(debug) cout << i << endl;
info tot=rd[1];
if(tag[1]) tot=gmx(rd[1],wdo[1]);
else tot=gmx(rd[1],wdw[1]);
int cs=tot.fi,ct=tot.se;
//if(debug) cout << cs << ' ' << ct << endl;
if(t[ct]-s[cs]<=0) break;
ans[i]=ans[i-1]+t[ct]-s[cs];
bs[ct].pop_back();
if(bs[ct].empty()) s[ct]=1e18,t[ct]=-1e18;
else s[ct]=bs[ct].front(),t[ct]=bs[ct].back();
updv(1,1,k,ct);
bs[cs].pop_front();
if(bs[cs].empty()) s[cs]=1e18,t[cs]=-1e18;
else s[cs]=bs[cs].front(),t[cs]=bs[cs].back();
updv(1,1,k,cs);
//if(debug) flush(1,1,k);
if(cs<ct) updt(1,1,k,cs,ct,1);
else if(cs>ct) updt(1,1,k,ct,cs,-1);
//if(debug) flush(1,1,k);
}
for(int i=1; i<=n/2 ;i++) ans[i]=max(ans[i],ans[i-1]);
}
bool check(){
for(int i=1; i<=n/2 ;i++){
cout << ans[i] << '\n';
}
return true;
}
int main(){
ios::sync_with_stdio(false);
int t=1;
for(int i=1; i<=t ;i++){
gen();solve3();
//solve2();
if(!check()){
cout << "test " << i << endl;
cout << "You sucko\n";
return 0;
}
}
//cout << "AC!!!!!!" << endl;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repA(i, a, n) for(int i = a; i <= (n); ++i)
#define repD(i, a, n) for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a) memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
void pre(){
}
void solve(){
}
typedef pair<ll,int> pli;
struct Tree {
typedef pli T;
const pii LOW = mp(1234567890,-1);
T f(T a, T b) { return min(a, b); }
int n;
vector<pli> s;
Tree() {}
Tree(int m, T def=mp(0,0)) { init(m, def); }
void init(int m, T def) {
n = 1; while (n < m) n *= 2;
s.assign(n + m, def);
s.resize(2 * n, LOW);
for (int i = n; i --> 1; )
s[i] = f(s[i * 2], s[i*2 + 1]);
}
void update(int pos, T val) {
pos += n;
s[pos] = val;
for (pos /= 2; pos >= 1; pos /= 2)
s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
}
T query(int l, int r) { return que(1, l, r, 0, n); }
T que(int pos, int l, int r, int lo, int hi) {
if (r <= lo || hi <= l) return LOW;
if (l <= lo && hi <= r) return s[pos];
int m = (lo + hi) / 2;
return f(que(2 * pos, l, r, lo, m),
que(2 * pos + 1, l, r, m, hi));
}
};
const int inf = 1e9+7;
struct Node {
Node *l = 0, *r = 0;
int lo, hi, madd = 0;
pair<ll,int> val = mp(-inf,-1);
Node(vi& v, int lo, int hi) : lo(lo), hi(hi) {
if (lo + 1 < hi) {
int mid = lo + (hi - lo)/2;
l = new Node(v, lo, mid); r = new Node(v, mid, hi);
val = max(l->val, r->val);
}
else val = mp(v[lo],lo);
}
pli query(int L, int R) {
if (R <= lo || hi <= L) return mp(-inf,-1);
if (L <= lo && hi <= R) return val;
push();
return max(l->query(L, R), r->query(L, R));
}
void add(int L, int R, int x) {
if (R <= lo || hi <= L) return;
if (L <= lo && hi <= R) {
madd += x;
val.fst -= x;
}
else {
push(), l->add(L, R, x), r->add(L, R, x);
val = max(l->val, r->val);
}
}
void push() {
if (madd)
l->add(lo,hi,madd), r->add(lo,hi,madd), madd = 0;
}
};
int p[200009];
int maxi(int l,int r){
if(p[l]>p[r]) return l;
else return r;
}
int mini(int l,int r){
if(p[l]<p[r]) return l;
else return r;
}
pii maxi(pii l,pii r){
if(p[l.fst]-p[l.snd]>p[r.fst]-p[r.snd]) return l;
else return r;
}
pii mini(pii l,pii r){
if(p[l.fst]-p[l.snd]<p[r.fst]-p[r.snd]) return l;
else return r;
}
int n;
struct Node2 {
Node2 *l = 0, *r = 0;
int lo, hi, madd = 0;
pii val;
int maxv,minv,lmaxv,lminv,rmaxv,rminv,mx,mn;
Node2(int lo, int hi) : lo(lo), hi(hi) {
if (lo + 1 < hi) {
int mid = lo + (hi - lo)/2;
l = new Node2( lo, mid); r = new Node2( mid, hi);
val = mp(n,n+1);
lmaxv=rmaxv=n;
lminv=rminv=n+1;
maxv=maxi(l->maxv,r->maxv);
minv=mini(l->minv,r->minv);
mx=mn=0;
}
else {
val = mp(n,n+1);
lmaxv=rmaxv=n;
lminv=rminv=n+1;
maxv=minv=lo;
mx=mn=0;
}
}
pli query(int L, int R) {
if (R <= lo || hi <= L) return mp(n,n+1);
if (L <= lo && hi <= R) return val;
push();
return val;
}
void add(int L, int R, int x) {
if (R <= lo || hi <= L) return;
if (L <= lo && hi <= R) {
if(x==inf){
val=mp(n,n+1);
lmaxv=rmaxv=maxv=n;
lminv=rminv=minv=n+1;
return;
}
madd += x;
mx+=x,mn+=x;
if(mx<=0){
val = mp(n,n+1);
lmaxv=rmaxv=n;
lminv=rminv=n+1;
}
else if(mn>0){
val=mp(maxv,minv);
lmaxv=rmaxv=maxv;
lminv=rminv=minv;
}
else{
push();
}
}
else {
if(madd) push();
l->add(L,R,x);
r->add(L,R,x);
push();
}
}
void push() {
if(madd) l->add(lo,hi,madd), r->add(lo,hi,madd), madd = 0;
val = maxi(maxi(l->val,r->val),maxi(mp(l->rmaxv,r->lminv),mp(r->lmaxv,l->rminv)));
maxv=maxi(l->maxv,r->maxv),minv=mini(l->minv,r->minv);
if(l->mn>0) lmaxv=maxi(l->maxv,r->lmaxv),lminv=mini(l->minv,r->lminv);
else lmaxv=l->lmaxv,lminv=l->lminv;
if(r->mn>0) rmaxv=maxi(r->maxv,l->rmaxv),rminv=mini(r->minv,l->rminv);
else rmaxv=r->rmaxv,rminv=r->rminv;
mx=max(l->mx,r->mx),mn=min(l->mn,r->mn);
}
};
int main() {
cin.sync_with_stdio(0); cin.tie(0);
cin.exceptions(cin.failbit);
pre();
cin>>n;
Tree T(n);
vector<pii> v(n);
rep(i,n) cin>>v[i].fst>>v[i].snd;
sort(all(v));
vi vals;
int mn = 1234567890;
set<pii> lol;
lol.insert({-1,inf-1});
lol.insert({n,-inf-1});
rep (i,n) {
vals.pb(v[i].snd-mn);
if(v[i].snd<mn) lol.insert({i,v[i].snd});
mn=min(mn,v[i].snd);
T.update(i,mp(v[i].snd,i));
p[i] = v[i].snd;
}
p[n] = -inf,p[n+1]=inf;
Node2 N2(0,n);
Node N(vals,0,n);
ll ans = 0;
rep(i,n/2){
pli cur = N.query(0,n);
pii z = N2.query(0,n);
if(p[z.fst]-p[z.snd]<=cur.fst){
ans+=cur.fst;
pli cur2 = T.query(0,cur.snd);
N2.add(0,cur.snd,1);
N2.add(cur.snd,cur.snd+1,inf);
N2.add(cur2.snd,cur2.snd+1,inf);
N2.add(0,cur2.snd,-1);
N.add(cur.snd,cur.snd+1,2*inf);
N.add(cur2.snd,cur2.snd+1,2*inf);
auto it = lol.lower_bound({cur.snd,p[cur.snd]});
if(it!=lol.end()&&*it==mp(cur.snd,p[cur.snd])) {
auto it2 = it;
T.update(cur.snd,{inf+1,cur.snd});
T.update(cur2.snd,{inf+1,cur2.snd});
auto it3 = it;
it2++;it3--;
int st = it->fst+1,en=it2->fst;
while(st<en){
pli gg = T.query(st,en-1);
if(gg.fst<it3->snd){
N.add(gg.snd+1,en,gg.fst-it->snd);
lol.insert({gg.snd,gg.fst});
en = gg.snd+1;
}
else{
N.add(st,en,it3->snd-it->snd);
en=st;
}
}
lol.erase(it);
}
it = lol.lower_bound({cur2.snd,-inf});
auto it2 = it;
T.update(cur.snd,{inf+1,cur.snd});
T.update(cur2.snd,{inf+1,cur2.snd});
auto it3 = it;
it2++;it3--;
int st = it->fst+1,en=it2->fst;
while(st<en){
pli gg = T.query(st,en-1);
if(gg.fst<it3->snd){
N.add(gg.snd+1,en,gg.fst-it->snd);
lol.insert({gg.snd,gg.fst});
en = gg.snd+1;
}
else{
N.add(st,en,it3->snd-it->snd);
en=st;
}
}
lol.erase(it);
}
else{
N2.add(z.fst,z.fst+1,inf);
N2.add(z.snd,z.snd+1,inf);
N2.add(0,z.fst,1);
N2.add(0,z.snd,-1);
ans+=p[z.fst]-p[z.snd];
N.add(z.fst,z.fst+1,2*inf);
N.add(z.snd,z.snd+1,2*inf);
T.update(z.fst,{inf+1,z.fst});
T.update(z.snd,{inf+1,z.snd});
auto it = lol.lower_bound({z.fst,p[z.fst]});
if(*it==mp(z.fst,p[z.fst])){
auto it2 = it;
auto it3 = it;
it2++;it3--;
int st = it->fst+1,en=it2->fst;
while(st<en){
pli gg = T.query(st,en-1);
if(gg.fst<it3->snd){
N.add(gg.snd+1,en,gg.fst-it->snd);
lol.insert({gg.snd,gg.fst});
en = gg.snd+1;
}
else{
N.add(st,en,it3->snd-it->snd);
en=st;
}
}
lol.erase(it);
}
it = lol.lower_bound({z.snd,p[z.snd]});
if(*it==mp(z.snd,p[z.snd])){
auto it2 = it;
auto it3 = it;
it2++;it3--;
int st = it->fst+1,en=it2->fst;
while(st<en){
pli gg = T.query(st,en-1);
if(gg.fst<it3->snd){
N.add(gg.snd+1,en,gg.fst-it->snd);
lol.insert({gg.snd,gg.fst});
en = gg.snd+1;
}
else{
N.add(st,en,it3->snd-it->snd);
en=st;
}
}
lol.erase(it);
}
}
cout<<ans<<'\n';
}
return 0;
}