### thenymphsofdelphi's blog

By thenymphsofdelphi, 4 weeks ago, ## 1828A - Divisible Array

Idea: thenymphsofdelphi
Preparation: Mike4235

Hint 1
Hint 2
Solution
Implementation 1
Implementation 2

## 1828B - Permutation Swap

Idea: thenymphsofdelphi
Preparation: Mike4235

Hint 1
Solution
Implementation

## 1827A - Counting Orders

Idea: Mike4235
Preparation: thenymphsofdelphi

Hint 1
Solution
Implementation

## 1827B2 - Range Sorting (Hard Version)

Idea: lanhf
Preparation: Mike4235

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Implementation 1
Implementation 2
Bonus

## 1827C - Palindrome Partition

Idea: lanhf
Preparation: lanhf

Hint1
Hint2
Solution
Implementation
Bonus

## 1827D - Two Centroids

Idea: Mike4235
Preparation: lanhf

Hint1
Hint2
Solution
Implementation
flowerletter :pensive:

## 1827E - Bus Routes

Idea: Mike4235
Preparation: thenymphsofdelphi

Hint 1
Hint 2
Solution
Implementation 1
Implementation 2
sorry gamegame

## 1827F - Copium Permutation

Idea: lanhf
Preparation: lanhf

Solution
Implementation Tutorial of Codeforces Round 873 (Div. 1) Tutorial of Codeforces Round 873 (Div. 2) Comments (88)
 » fast editorial!
 » I was waiting for it
 » 3 weeks ago, # | ← Rev. 2 →   Lots of solutions for Problem A. You can also observe that sum(1..N) % N is 0 if N is odd, and N/2 if N is even, so you can construct A=1..N if N is odd, and when N is even it's the same except you change A[N/2] = N.
•  » » Here's another one, similar to yours but without odd/even check: [n - (sum(2..n)%n), 2, ..., n]
 » 3 weeks ago, # | ← Rev. 3 →   Hi, relatively new here, probably have a dumb question. Coding in python like a real noob. Can anyone explain to me a detail from problem 3, Counting orders. This part of the code specifically.for i in range(n):; while j < n and a[i] > b[j]:; j += 1; ans = (ans * (j — i)) % int(1e9 + 7); print(ans)why can't we just write print(ans % int(1e9 + 7) in the last line without having to calculate ans = (ans * (j — i)) % int(1e9 + 7) each iteration? im guessing because ans probably gets too large, right?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   (in case of c++) becoz the value will get wrap up in between operations....like if during the operation ur ans has reached ~2e9 then in next operation it will become negative...as it has gone out of the integer limit .....so to avoid that u use modulu at each operation .... read about this modulu operator how it works....plenty of resources on yt
•  » » Well integer have no limits in python, but when they become big (in this case too big), they will slow down the calculation (calculation with numbers that take less space in memory is faster), which is way you should always apply the mod after each step.
 » I solved D1B1 using DSU, if we fix the start of the subarray we can keep adding an element and find its position in the new sorted array with DSU.submission link: https://mirror.codeforces.com/contest/1828/submission/205880043Is it possible to optimize this idea to pass B2
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   Can you please explain the idea or give any similar problem which uses the same idea?
•  » » » We divide the current array into non-overlapping subarrays as the editorial, but we also visualise them as connected components (cost of a component is the size-1, minimum time is the sum of costs of all components). If we know the connected components of a subarray [L,R-1] then we can find the subarray [L,R] by finding the leftmost component k such that it has a value > a[R], and then connecting R with k and every component after it so after sorting that component R will be in its correct position.
•  » » » » 3 weeks ago, # ^ | ← Rev. 4 →   Can you please tell me what these lines of code are doing? Code for(int j=i+1;j<=x;j++){ while(j-sz[get(j)]>=i&&a[j]
•  » » » » leftmost component i such that it has a value > a[R] leftmost component j such that it has a value < a[R] and shouldn't we take leftmost of i and j and merge components between them ? 
•  » » » » » We assume that the subarray [L,R-1] is already sorted, then we just need to add R by shifting the elements greater than a[R] after it, so they have to be in the same connected component as R.
 » Typo in Range sortingWe can see that a triplet (l,k,r) with x
•  » » I fixed that. Thanks.
 » Div2.C and Div2.D have the same points.But why is D much more difficult than C?
•  » » Maybe it's because there are two versions of this problem.
 » For the C bonus:The only part in the editorial solution that is $O(n \log(n))$ is the sparse table for finding the minimum length prefix palindrome. This step can be done in $O(n)$ total instead. Going right to left, we can add the even palindromes with centre at $i$ to a stack. Now the potentially smallest palindrome is at the top of the stack. So the stack can be popped from, while the palindrome at the top of the stack does not reach far enough. Then the topmost palindrome on the stack must be the minimum prefix palindrome. This is $O(n)$ amortized.My submission: 205927403 (I thought instead of removing suffix palindromes, but the logic is equivalent, only reversed)
•  » » Also can use PAM instead.
•  » » » What's the full form of PAM?
•  » » » »
 » I can't figure out what went wrong in my D1A1 submission, I've essentially done the same thing but it is errorsome on a test case. Please help me out.https://mirror.codeforces.com/contest/1828/submission/205890580Thanks in advance!
 » I think we can use 2 stacks for B2, which is $O(n)$. https://mirror.codeforces.com/contest/1828/submission/205931557
•  » » Hey, can you explain your intuition and what your code does it would be very helpful
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   It is the same as in editorial. I just optimize the process finding $x,k,y$. The first stack is to record $k$ and the second is to record $x$.
•  » » Nice solution!
•  » » Great solution, man! Thanks.
•  » » I couldn't come up with this approach in contest. Thanks for a clever solution!
 » I kinda fucked up D. I knew how to find moving centroids, but for some reason I came up with wrong methods to find maximum size subtree there. So I just gave up and used Top tree to find maximum size subtree of given node. CodeIn retrospect either I should not be dumb or I should try to cheese with top trees in the first place
•  » » all the best for next time :) .
 » Cannot pass Div2 D1 with BIT+Seg unless replacing seg with vector :( .
 » 3 weeks ago, # | ← Rev. 2 →   Div2.D1 was equally hard as normal D, then why there is no separate editorial for it ? I want to know how to do it in O ( N ^ 2 ). If you made two separate problems, then please write two separate editorials for both the problems ( or at least explain something ) . downvoting for not explaining D1 clearly.
•  » » Wow man really just saw the headings, and didnt even bother to read. Look prperly.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   I have read it, including the bonus problem where beauty is ( square of min cost ) . not that I can solve that xD
•  » » » » Then why are you complaining? If you read it, you qould see the editorial has nearly same sols for easy and hard version. Why would they make 2 separate editorials when they do not explain anything new.
•  » » But in the last paragraph the author has mentioned about the solution of D1.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   that's true. they have mentioned, but I am not able to understand last 2-3 para's of editorial. I made a mistake by not reading last para clearly. but even after reading it , I am not able to understand clearly.
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   it is D1' solution as well. According to the editoral the only difference between D1 and D2 is the last paragraph.
•  » » If you don't use sparse table or something like that,you will do it in O(N^2)
 » I have a puzzle question, for example 4 and 2, 1, 4, 3, why is the answer 6
•  » » Maybe I didn't understand the meaning of D?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →       cost=0+0+0+0=0 [2 1] [1 4] [4 3] cost=1+0+1=2 [2 1 4] [1 4 3] cost=1+1=2 [2 1 4 3] cost=2 so the sum is 2+2+2=6 
•  » » » Thank you very much. Thank you. I thought a subsequence could only find one set of l's and r's
 » 3 weeks ago, # | ← Rev. 5 →   can someone explain why (k-x) * (y-i) is added to answer in Div2D1 ? •  » » Ok.Thanks!!!
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   Till para 5, it says that for each [ l ... r ] ( 1 <= l < n , l < r <= n ) , we will find number of 'k's such that each max(a[l...k]) < min(a[k+1...r).So, based on this assumption, we would think that for(int l = 0 ; l < n-1 ; l++) { for(int r = l+1 ; r < n ; r++) { // some logic here, which will count number of 'k's which are satisfying (*) in the editorial // but suddenly logic changes } } After this, logic changes on para 6, for each 'i', lets find first left index, which is less that a[i] , lets call that index 'k'. ( a[k] < a[i] )Now, find first index on the left side of 'k' which is greater than a[i], lets call this index 'x' , ( a[x] > a[i] )Now, find first index on the right side of 'i' which is less than a[i], lets call this index 'y' , (a[y] < a[i] )so, putting this in code, for(int i = 0 ; i < n ; i++) { // first go on leftside, and find 'k' and 'x' , int k , x; k = 0 , x = 0; for(int j = i-1 ; j >= 0 ; j--) { // first find 'k' if(a[j] < a[i]) { k = j; break; } } for(int j = k-1 ; j >= 0 ; j--) { // now find 'x' on left of 'k' if(a[j] > a[i]) { x = j ; break; } } int y = n-1; for(int j = i+1 ; j < n ; j++) { // now find 'y' on right of 'i' if(a[j] < a[i]) { y = j ; break; } } ans = ans + (k-x) * (y-i) // but why are we adding this ??? how does this count } But why are we adding this (k-x) * (y-i) , how does that count number of triplets (l , k , r) minus 'k' which was proposed in the first 5 paras ?
•  » » » Why are we adding this (k-x) * (y-i) ? •  » » » » You need to understand that for a position i, k has only one. max{a[l],...,a[k]}
•  » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   I think I understood that part. basically, all the subarrays which are not including x and y, and which are including k and i (both) . but how does that help in counting answer ?
•  » » » » » » The contribution of the subarray a [l, r] to the answer is (r-l)-num, which means we can find num subscripts j, so that max{a[l],...,a[j]}
•  » » » » » » Actually, it is substracted from the answer. For a subarray a[l..r], the beauty is the r - l - count(triplet(l, k, r)).
•  » » » » » » » understood, from total subarray lengths, we are subtracting the triplets which create partitions in subarrays. thanks. got it.
 » Hello, here is a video tutorial/editorial with solutions to these problems: D2B, D2C/D1A, D2D1/D1B1, D2D2/D1B2, D2E/D1C:https://youtube.com/watch?v=VwY7QzStMk4
 » 3 weeks ago, # | ← Rev. 2 →   I could not solve Div2 C in contest time. But later I have given the problem statements to ChatGPT properly and it gave me the correct answer. Here is code that ChatGPT wrote for me 205980801
 » 3 weeks ago, # | ← Rev. 2 →   D2: i think one can hack this solution as its O(n^2)https://mirror.codeforces.com/contest/1828/submission/205990252I just mistakenly submitted without commenting O(n^2) part and suprisingly it got passed.And i thought using segment tree is overkill for 1 sec and n<3e5 during contest
•  » » The compiler optimized away your $\mathcal O(n^2)$ loop, since j is not being used.
•  » » » lol sorry, yeah!!!
 » I think there is a typo in D2B solution: Complexity should be: O(n.log n).
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   The correct complexity is $\mathcal O(n + \log n)$ — see discussion here and here.
•  » » » Technically it should be $\mathcal{O}(n + \log m)$ where $m$ is the maximum value in the input.
•  » » » » But the input is always a permutation, meaning that $m = n$ always holds and the complexity is $O(n + \log n)$.
•  » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   Good point! You're right. I had already forgotten about that.Though it does mean the complexity becomes just $\mathcal{O}(n)$ because $n$ dominates $\log n$ when $n$ goes to infinity.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   Thanks for correcting me.. I was not aware of this amortized analysis.So.. Can I say that in our problem: O(n+log M) = O(n+log n) = O(n) where M is the maximum element of the array?
•  » » » » Yes
 » Great editorial! Really explains the concepts really well! The hints in Div 2 D allowed me to solve the problem without even reading the tutorial, the various ways to frame the problem makes it really interesting.
•  » » Thank you!
 » Can anyone explain the solution of problem B? I mean is there any proof that in order to move pi to position i ,|pi-i| has to be divisible by k?(Apologies for not using subscript)
•  » » Since any swap between two elements will change their position by exactly $k$, the distance between the initial position and the final position of each element will be divisible by $k$ as well.
 » really nice contest unfortunately i couldn't enter it so I entered virtual
 » keep up great work
 » the first graph in the 1827C solution should have l before r-l
•  » » and i think the second case statement should say t[0...2l-r] instead of t[0...2r-l]
•  » » » Fixed. Thanks.
 » problem b in div 2 is simillar to this link a good problem to understand gcd defination.
 » first 3 problems were very easy, but i couldn't write this round:(
 » we can solve div1 A using combinatorics by calculating how many choices we have for a[i] such that a[i] greater than b[i].
»

# include<bits/stdc++.h>

using namespace std; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_real_distribution<> pp(0.0,1.0);

# define se second

const int inf=1e9; const int mod=998244353; const int maxn=500005; const int maxl=25; const int maxa=1000005; int power(int a,int n){ int res=1; while(n){ if(n&1) res=res*a%mod; a=a*a%mod;n>>=1; } return res; } int n,p[maxn]; namespace Solve_left{ struct node{ int Min=0,num=0,lazy=0; node(){} friend node operator+(node a,node b){ node res;res.Min=min(a.Min,b.Min); if(a.Min==b.Min) res.num=a.num+b.num; else if(a.Min<b.Min) res.num=a.num; else res.num=b.num; return res; } }; struct ST{ node tree[4*maxn]; void getnew(int id,int val){ tree[id].Min+=val;tree[id].lazy+=val; } void pushdown(int id){ if(tree[id].lazy!=0){ getnew(id<<1,tree[id].lazy); getnew(id<<1|1,tree[id].lazy); tree[id].lazy=0; } } void change(int l,int r,int id,int x){ if(l==r){ tree[id].num=1; return; } int mid=(l+r)>>1; if(x<=mid) change(l,mid,id<<1,x); else change(mid+1,r,id<<1|1,x); tree[id]=tree[id<<1]+tree[id<<1|1]; } void update(int l,int r,int id,int tl,int tr,int val){ if(r<tl || tr<l) return; if(tl<=l && r<=tr){ getnew(id,val); return; } pushdown(id); int mid=(l+r)>>1; update(l,mid,id<<1,tl,tr,val);update(mid+1,r,id<<1|1,tl,tr,val); tree[id]=tree[id<<1]+tree[id<<1|1]; } }Segtree; long long res[maxn]; void solve(){ for(int i=1;i<=4*n;i++) Segtree.tree[i]=node(); vector Min,Max; for(int i=1;i<=n;i++){ int x=p[i]; while(!Min.empty() && p[Min.back()]>x){ int pos=Min.back();Min.pop_back(); if(Min.empty()) Segtree.update(1,n,1,1,pos,p[pos]-x); else Segtree.update(1,n,1,Min.back()+1,pos,p[pos]-x); } while(!Max.empty() && p[Max.back()]<x){ int pos=Max.back();Max.pop_back(); if(Max.empty()) Segtree.update(1,n,1,1,pos,x-p[pos]); else Segtree.update(1,n,1,Max.back()+1,pos,x-p[pos]); } Min.push_back(i);Max.push_back(i); if(i>1) Segtree.update(1,n,1,1,i-1,-1); Segtree.change(1,n,1,i); res[i]=res[i-1]+Segtree.tree.num; } } } namespace Solve_right{ struct DSU{ int par[maxn],r[maxn]; long long cnt=0; void init(){ cnt=0; for(int i=0;i<=n+1;i++) par[i]=r[i]=0; } int findpar(int u){ if(u!=par[u]) return par[u]=findpar(par[u]); return u; } void unions(int u,int v){ u=findpar(u);v=findpar(v); if(r[u]<r[v]) swap(v,u); cnt+=1LL*r[u]*r[v]; par[v]=u;r[u]+=r[v]; } void get(int x){ par[x]=x;r[x]=1;cnt++; if(par[x] && par[x-1]) unions(x,x-1); if(par[x] && par[x+1]) unions(x,x+1); } }dsu; long long res[maxn]; void solve(){ dsu.init(); for(int i=0;i<=n+1;i++) res[i]=0; for(int i=n;i>=1;i--){ dsu.get(p[i]); res[i]=dsu.cnt; } } } namespace Solve_merge{ struct BIT{ int up[maxn],down[maxn],bit[maxn]; void build(){ for(int i=1;i<=n;i++){up[i]=n+1;down[i]=0;bit[i]=0;} } void update(int x){ for(int i=x;i<=n;i+=(i&(-i))){ down[i]=max(down[i],x); bit[i]++; } for(int i=n-x+1;i<=n;i+=(i&(-i))) up[i]=min(up[i],x); } int query(int x){ int res=0; for(int i=x;i>=1;i-=(i&(-i))) res+=bit[i]; return res; } int query_range(int l,int r){ return query(r)-query(l-1); } int query_up(int x){ int res=n+1; for(int i=n-x;i>=1;i-=(i&(-i))) res=min(res,up[i]); return res; } int query_down(int x){ int res=0; for(int i=x-1;i>=1;i-=(i&(-i))) res=max(res,down[i]); return res; } }Bit; struct Sparse_table{ int Min[maxn][maxl],Max[maxn][maxl],lg2[maxn]; int query_Max(int l,int r){ int p=lg2[r-l+1]; return max(Max[l][p],Max[r-(1<<p)+1][p]); } int query_Min(int l,int r){ int p=lg2[r-l+1]; return min(Min[l][p],Min[r-(1<<p)+1][p]); } void build(){ for(int i=2;i<=n;i++) lg2[i]=lg2[i/2]+1; for(int i=1;i<=n;i++) Max[i]=Min[i]=p[i]; for(int i=1;i<=20;i++){ for(int j=1;j<=(n-(1<<i)+1);j++){ Max[j][i]=max(Max[j][i-1],Max[j+(1<<(i-1))][i-1]); Min[j][i]=min(Min[j][i-1],Min[j+(1<<(i-1))][i-1]); } } } }Sparse; struct state{ int pos=0,num=0,Max=0,cnt=0,cur=0; state(){} }; struct node{ state pMin,sMin,pMax,sMax; bool okMin=true,okMax=true; long long total=0; node(){} friend node operator+(node a,node b){ if(b.pMin.pos==0) return a; node res; res.pMin=a.pMin;res.pMax=a.pMax; res.sMin=b.sMin;res.sMax=b.sMax; res.total=a.total+b.total; res.okMin=res.okMax=false; if(a.sMin.num==b.pMin.num){ int dMax=Sparse.query_Max(a.sMin.pos,b.pMin.pos-1),dMin=Sparse.query_Min(a.sMin.pos,b.pMin.pos-1),d=b.pMax.num; int nwMax=max(a.sMin.Max,b.pMin.Max); res.total-=1LL*(a.sMin.Max+b.pMin.Max)*a.sMin.cur; if(dMin==d+1 && dMax-dMin+1==b.pMin.pos-a.sMin.pos){ res.okMin=(a.okMin && b.okMin); nwMax=max(nwMax,a.sMin.cnt+b.pMin.cnt); res.pMin.cnt+=a.okMin*b.pMin.cnt; res.sMin.cnt+=b.okMin*a.sMin.cnt; } else if(dMax-dMin+1==b.pMin.pos-a.sMin.pos){ nwMax=max(nwMax,a.sMin.cnt+1); res.pMin.cnt+=a.okMin; } res.total+=1LL*nwMax*a.sMin.cur; if(a.pMin.num==a.sMin.num) res.pMin.Max=nwMax; if(b.pMin.num==b.sMin.num) res.sMin.Max=nwMax; } if(a.sMax.num==b.pMax.num){ int dMax=Sparse.query_Max(a.sMax.pos,b.pMax.pos-1),dMin=Sparse.query_Min(a.sMax.pos,b.pMax.pos-1),d=b.pMin.num; int nwMax=max(a.sMax.Max,b.pMax.Max); res.total-=1LL*(a.sMax.Max+b.pMax.Max)*a.sMax.cur; if(dMax==d-1 && dMax-dMin+1==b.pMax.pos-a.sMax.pos){ res.okMax=(a.okMax && b.okMax); nwMax=max(nwMax,a.sMax.cnt+b.pMax.cnt); res.pMax.cnt+=a.okMax*b.pMax.cnt; res.sMax.cnt+=b.okMax*a.sMax.cnt; } else if(dMax-dMin+1==b.pMax.pos-a.sMax.pos){ nwMax=max(nwMax,a.sMax.cnt+1); res.pMax.cnt+=a.okMax; } res.total+=1LL*nwMax*a.sMax.cur; if(a.pMax.num==a.sMax.num) res.pMax.Max=nwMax; if(b.pMax.num==b.sMax.num) res.sMax.Max=nwMax; } return res; } }; struct ST{ node tree[4*maxn]; void getnew_Max(int id,int num,int cur){ tree[id].total-=1LL*tree[id].pMax.Max*tree[id].pMax.cur; tree[id].pMax.num=tree[id].sMax.num=num; tree[id].pMax.cur=tree[id].sMax.cur=cur; tree[id].total+=1LL*tree[id].pMax.Max*tree[id].pMax.cur; } void getnew_Min(int id,int num,int cur){ //cout << "getnew_Min " << id << ' ' << tree[id].pMin.cur << '\n'; tree[id].total-=1LL*tree[id].pMin.Max*tree[id].pMin.cur; tree[id].pMin.num=tree[id].sMin.num=num; tree[id].pMin.cur=tree[id].sMin.cur=cur; tree[id].total+=1LL*tree[id].pMin.Max*tree[id].pMin.cur; } void pushdown(int id){ if(tree[id].pMin.num==tree[id].sMin.num && tree[id<<1].pMin.num!=tree[id].pMin.num){ getnew_Min(id<<1,tree[id].pMin.num,tree[id].pMin.cur); getnew_Min(id<<1|1,tree[id].pMin.num,tree[id].pMin.cur); } if(tree[id].pMax.num==tree[id].sMax.num && tree[id<<1].pMax.num!=tree[id].pMax.num){ getnew_Max(id<<1,tree[id].pMax.num,tree[id].pMax.cur); getnew_Max(id<<1|1,tree[id].pMax.num,tree[id].pMax.cur); } } void update_Max(int l,int r,int id,int tl,int tr,int num,int cur){

if(tr<l || r<tl) return;
if(tl<=l && r<=tr){
//cout << tree[id].total << ' ' << num << ' ' << cur << '\n';
getnew_Max(id,num,cur);
//cout << "Max* " << tl << ' ' << tr << ' ' << l << ' ' << r << ' ' << tree[id].total << '\n';
return;
}
pushdown(id);
int mid=(l+r)>>1;
update_Max(l,mid,id<<1,tl,tr,num,cur);update_Max(mid+1,r,id<<1|1,tl,tr,num,cur);
tree[id]=tree[id<<1]+tree[id<<1|1];
//cout << "Max " << l << ' ' << r << ' ' << tree[id].total << '\n';
}
void update_Min(int l,int r,int id,int tl,int tr,int num,int cur){
//if(id==1) cout << "Min** " << tl << ' ' << tr << ' ' << num << ' ' << cur << '\n';
if(tr<l || r<tl) return;
if(tl<=l && r<=tr){
//cout << tree[id].total << ' ' << num << ' ' << cur << '\n';
getnew_Min(id,num,cur);
//cout << "Min* " << tl << ' ' << tr << ' ' << l << ' ' << r << ' ' << tree[id].total << '\n';
return;
}
pushdown(id);
int mid=(l+r)>>1;
update_Min(l,mid,id<<1,tl,tr,num,cur);update_Min(mid+1,r,id<<1|1,tl,tr,num,cur);
tree[id]=tree[id<<1]+tree[id<<1|1];
//cout << "Min " << l << ' ' << r << ' ' << tree[id].total << '\n';
}
void change(int l,int r,int id,int p,int pos,int num,int curMin,int curMax){
if(l==r){
if(num==0) tree[id]=node();
else{
tree[id].pMin.pos=tree[id].pMax.pos=pos;
tree[id].pMin.num=tree[id].pMax.num=num;
tree[id].pMin.cur=curMin;tree[id].pMax.cur=curMax;
tree[id].pMin.Max=tree[id].pMax.Max=tree[id].pMin.cnt=tree[id].pMax.cnt=1;
tree[id].total=curMin+curMax;
tree[id].sMin=tree[id].pMin;tree[id].sMax=tree[id].pMax;
}
return;
}
pushdown(id);
int mid=(l+r)>>1;
if(p<=mid) change(l,mid,id<<1,p,pos,num,curMin,curMax);
else change(mid+1,r,id<<1|1,p,pos,num,curMin,curMax);
tree[id]=tree[id<<1]+tree[id<<1|1];
//cout << "Change " << mid+1 << ' ' << r << ' ' << tree[id<<1|1].total << ' ' << tree[id<<1|1].pMax.pos << ' ' << tree[id<<1|1].pMax.num << ' ' << tree[id<<1|1].pMax.cnt << '\n';
//cout << "Change " << l << ' ' << mid << ' ' << tree[id<<1].total << ' ' << tree[id<<1].sMax.pos << ' ' << tree[id<<1].sMax.num << ' ' << tree[id<<1].sMax.cnt << '\n';
}
}Segtree;
long long res[maxn];
int st[maxn],sz;
void solve(){
sz=0;
for(int i=1;i<=4*n;i++) Segtree.tree[i]=node();
Bit.build();
Sparse.build();
vector<pii> Min,Max;
for(int i=1;i<=n;i++){
//cout << i << '\n';
int x=p[i],val_up=Bit.query_up(x)-x-1,val_down=x-Bit.query_down(x)-1;
//cout << val_up << ' ' << val_down << '\n';
while(sz && Bit.query_range(Sparse.query_Min(st[sz],i),Sparse.query_Max(st[sz],i))!=i-st[sz]){
//cout << st[sz] << ' ' << Sparse.query_Min(st[sz],i) << ' ' << Sparse.query_Max(st[sz],i) << '\n';
Segtree.change(1,n,1,sz--,0,0,0,0);
}
while((int)Min.size()>=2 && Min[(int)Min.size()-2].se>=sz) Min.pop_back();
if(!Min.empty() && Min.back().se>=sz) Min.back().se=sz;
while((int)Max.size()>=2 && Max[(int)Max.size()-2].se>=sz) Max.pop_back();
if(!Max.empty() && Max.back().se>=sz) Max.back().se=sz;
while(!Min.empty() && Min.back().fi>x){
int pos=Min.back().se;Min.pop_back();
if(Min.empty()) Segtree.update_Min(1,n,1,1,pos,x,val_down);
else Segtree.update_Min(1,n,1,Min.back().se+1,pos,x,val_down);
}
while(!Max.empty() && Max.back().fi<x){
int pos=Max.back().se;Max.pop_back();
if(Max.empty()) Segtree.update_Max(1,n,1,1,pos,x,val_up);
else Segtree.update_Max(1,n,1,Max.back().se+1,pos,x,val_up);
}
Segtree.change(1,n,1,++sz,i,x,val_down,val_up);st[sz]=i;
Min.push_back({p[i],sz});Max.push_back({p[i],sz});
Bit.update(x);
res[i]=Segtree.tree.total+sz;
/*
cout << sz << ' ' << res[i] << ' ' << val_up << ' ' << val_down << '\n';
cout << "vector<Min>\n";
for(pii a:Min) cout << '{' << a.fi << ',' << a.se << '}' << ' ';
cout << '\n';
cout << "vector<Max>\n";
for(pii a:Max) cout << '{' << a.fi << ',' << a.se << '}' << ' ';
cout << '\n';
*/

}
//cout << '\n';
}`

} void solve(){ cin >> n; for(int i=1;i<=n;i++) cin >> p[i]; Solve_left::solve(); Solve_right::solve(); Solve_merge::solve(); cout << 1LL*n*(n+1)/2 << ' '; for(int i=1;i<=n;i++) cout << Solve_left::res[i-1]+Solve_right::res[i+1]+Solve_merge::res[i] << ' '; cout << '\n'; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); int test=1;cin >> test; while(test--) solve(); } Gnu 14

 » I think ,There is huge difference in difficulty of d than c.
 » Hello, I am new here, I could not solve Div.2 D, but I have a feeling that the number of inversions in the array and the size of the array together can be mapped to the required answer using some equation. for example, Inversion = 0, we have Answer = 0. And for max inversion we have,Answer = summation of (i*(n-i)) from i=1 to n-1.And the answers for the rest of the values will stay in that range.While I could not find the function which satisfies this, am I right in thinking this way?
 » lct solution for 1D 206402736
 » Does someone know of a solution for B1 simpler than the one for B2? (probably in O(n^2)).
•  » » 12 days ago, # ^ | ← Rev. 2 →   Obviously we need to beat the answer of $\sum_{l=1}^{n} \sum_{r=l+1}^{n} r-l$. How do we save time? Well, sorting $[L1,R1]$ and $[L2,R2]$ instead of $[L1,R2]$ saves $L2-R1$ seconds. We can only split the sort up like this if $max(L1...R1) •  » » » thanks! I'll implement it.  » I want to start up codeforces again with dedication. Anyone here who needs a partner for programming? I'm absolutely free for 2 months, so will be devote the full time to codeforces,  » 9 days ago, # | ← Rev. 3 → F without any data structures: 207285734. Took me just 10 hours to solve this problem. •  » » I find that you use divide and conquer. Can you explain your solution? •  » » » I used divide and conquer not to solve the problem, but to find some helper array. I wanted to know for every index$i$what is the number of segments of the initial array with their right bound at$i$that are copiums. I actually have no idea what is the easiest way to solve such a subproblem, and the easiest way I found was d&c.  » Ladies and gentlemen, E solution that's$O(N+M\log N)$instead of$O(N\log N)$. As you can see, I'm focusing on the important things. 207457936At this point, I'm pretty sure$O(N+M)$can't be done, but you're welcome to prove me wrong. At least it's$O(N+M)\$ in practice, with the only bad cases being handcrafted to make as many paths as possible get used in multiple depths of recursion. A bit over 1/2 of real runtime is taken up by reading the input and running an initial DFS, so there's not much left to optimise that'd be at least a little bit specific to this problem.