### thenymphsofdelphi's blog

By thenymphsofdelphi, 10 months 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
• +183

 » 9 months ago, # |   -13 fast editorial!
 » 9 months ago, # |   +6 I was waiting for it
 » 9 months ago, # | ← Rev. 2 →   +7 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.
•  » » 9 months ago, # ^ |   +3 Here's another one, similar to yours but without odd/even check: [n - (sum(2..n)%n), 2, ..., n]
 » 9 months ago, # | ← Rev. 3 →   0 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?
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 (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
•  » » 9 months ago, # ^ |   +20 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.
 » 9 months ago, # |   +50 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
•  » » 9 months ago, # ^ | ← Rev. 2 →   +6 Can you please explain the idea or give any similar problem which uses the same idea?
•  » » » 9 months ago, # ^ |   +29 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.
•  » » » » 9 months ago, # ^ | ← Rev. 4 →   +6 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]
•  » » » » 9 months ago, # ^ |   +5 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 ? 
•  » » » » » 9 months ago, # ^ |   +3 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.
•  » » 8 months ago, # ^ |   0 Can u explain the time complexity for the inner while loop(amortised ananlysis) ? Worst case O(n)?
•  » » » 8 months ago, # ^ |   0 The while loop must stop when there is only one component left (j - sz[get(j)] >= i is true when there are more than one component), and every iteration the number of components decreases by $1$. So for each $i$, the total number of iterations is at most $n - i$.
•  » » » » 8 months ago, # ^ |   0 Thanks with a upvote
 » 9 months ago, # |   +9 Typo in Range sortingWe can see that a triplet (l,k,r) with x
•  » » 9 months ago, # ^ |   +11 I fixed that. Thanks.
 » 9 months ago, # |   +3 Div2.C and Div2.D have the same points.But why is D much more difficult than C?
•  » » 9 months ago, # ^ |   +3 Maybe it's because there are two versions of this problem.
 » 9 months ago, # |   +28 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)
•  » » 9 months ago, # ^ |   +16 Also can use PAM instead.
•  » » » 9 months ago, # ^ |   0 What's the full form of PAM?
•  » » » » 9 months ago, # ^ |   0
 » 9 months ago, # |   0 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!
 » 9 months ago, # |   +56 I think we can use 2 stacks for B2, which is $O(n)$. https://mirror.codeforces.com/contest/1828/submission/205931557
•  » » 9 months ago, # ^ |   0 Hey, can you explain your intuition and what your code does it would be very helpful
•  » » » 9 months ago, # ^ | ← Rev. 2 →   +7 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$.
•  » » 9 months ago, # ^ |   0 Nice solution!
•  » » 9 months ago, # ^ |   0 Great solution, man! Thanks.
•  » » 9 months ago, # ^ |   0 I couldn't come up with this approach in contest. Thanks for a clever solution!
 » 9 months ago, # |   +15 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
•  » » 9 months ago, # ^ |   0 all the best for next time :) .
 » 9 months ago, # |   +3 Cannot pass Div2 D1 with BIT+Seg unless replacing seg with vector :( .
 » 9 months ago, # | ← Rev. 2 →   +7 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.
•  » » 9 months ago, # ^ |   -22 Wow man really just saw the headings, and didnt even bother to read. Look prperly.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 I have read it, including the bonus problem where beauty is ( square of min cost ) . not that I can solve that xD
•  » » » » 9 months ago, # ^ |   0 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.
•  » » 9 months ago, # ^ |   0 But in the last paragraph the author has mentioned about the solution of D1.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   0 it is D1' solution as well. According to the editoral the only difference between D1 and D2 is the last paragraph.
•  » » 9 months ago, # ^ |   -8 If you don't use sparse table or something like that,you will do it in O(N^2)
 » 9 months ago, # |   -16 I have a puzzle question, for example 4 and 2, 1, 4, 3, why is the answer 6
•  » » 9 months ago, # ^ |   -16 Maybe I didn't understand the meaning of D?
•  » » 9 months ago, # ^ | ← Rev. 2 →   +14 [2] [1] [4] [3] 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 
•  » » » 9 months ago, # ^ |   0 Thank you very much. Thank you. I thought a subsequence could only find one set of l's and r's
 » 9 months ago, # | ← Rev. 5 →   0 can someone explain why (k-x) * (y-i) is added to answer in Div2D1 ?
•  » » 9 months ago, # ^ |   -8 Ok.Thanks!!!
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 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 ?
•  » » » 9 months ago, # ^ |   0 Why are we adding this (k-x) * (y-i) ?
•  » » » » 9 months ago, # ^ |   0 You need to understand that for a position i, k has only one. max{a[l],...,a[k]}
•  » » » » » 9 months ago, # ^ | ← Rev. 2 →   0 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 ?
•  » » » » » » 9 months ago, # ^ |   0 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]}
•  » » » » » » 9 months ago, # ^ |   0 Actually, it is substracted from the answer. For a subarray a[l..r], the beauty is the r - l - count(triplet(l, k, r)).
•  » » » » » » » 9 months ago, # ^ |   0 understood, from total subarray lengths, we are subtracting the triplets which create partitions in subarrays. thanks. got it.
•  » » 6 months ago, # ^ |   0 can you explain in problem B(div2) to have the maximum K why we need to do gcd of all the differences we got i mean from where you got the intuition to do gcd??
 » 9 months ago, # |   +41 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
 » 9 months ago, # | ← Rev. 2 →   0 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
 » 9 months ago, # | ← Rev. 2 →   0 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
•  » » 9 months ago, # ^ |   +4 The compiler optimized away your $\mathcal O(n^2)$ loop, since j is not being used.
•  » » » 9 months ago, # ^ |   0 lol sorry, yeah!!!
 » 9 months ago, # |   0 I think there is a typo in D2B solution: Complexity should be: O(n.log n).
•  » » 9 months ago, # ^ | ← Rev. 2 →   +11 The correct complexity is $\mathcal O(n + \log n)$ — see discussion here and here.
•  » » » 9 months ago, # ^ |   0 Technically it should be $\mathcal{O}(n + \log m)$ where $m$ is the maximum value in the input.
•  » » » » 9 months ago, # ^ |   +3 But the input is always a permutation, meaning that $m = n$ always holds and the complexity is $O(n + \log n)$.
•  » » » » » 9 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » 6 months ago, # ^ |   0 cann you explain why we have taken gcd of all the differences we got i mean out of nowhere he said about gcd how this intuition came i mean i didn't understoos the proof
•  » » » 9 months ago, # ^ | ← Rev. 2 →   +3 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?
•  » » » » 9 months ago, # ^ |   0 Yes
 » 9 months ago, # |   0 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.
•  » » 9 months ago, # ^ |   0 Thank you!
 » 9 months ago, # |   0 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)
•  » » 9 months ago, # ^ |   +8 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.
 » 9 months ago, # |   0 really nice contest unfortunately i couldn't enter it so I entered virtual
 » 9 months ago, # |   0 keep up great work
 » 9 months ago, # |   0 the first graph in the 1827C solution should have l before r-l
•  » » 9 months ago, # ^ |   0 and i think the second case statement should say t[0...2l-r] instead of t[0...2r-l]
•  » » » 9 months ago, # ^ |   0 Fixed. Thanks.
 » 9 months ago, # |   0 problem b in div 2 is simillar to this link a good problem to understand gcd defination.
 » 9 months ago, # |   0 first 3 problems were very easy, but i couldn't write this round:(
 » 9 months ago, # |   0 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].
»
9 months ago, # |
-76

# 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[1].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][0]=Min[i][0]=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[1].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

 » 9 months ago, # |   0 I think ,There is huge difference in difficulty of d than c.
 » 9 months ago, # |   -8 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?
 » 9 months ago, # |   0 lct solution for 1D 206402736
 » 9 months ago, # |   0 Does someone know of a solution for B1 simpler than the one for B2? (probably in O(n^2)).
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 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) •  » » » 9 months ago, # ^ | 0 thanks! I'll implement it.  » 9 months ago, # | 0 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 months ago, # | ← Rev. 3 → +8 F without any data structures: 207285734. Took me just 10 hours to solve this problem. •  » » 9 months ago, # ^ | 0 I find that you use divide and conquer. Can you explain your solution? •  » » » 9 months ago, # ^ | 0 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.  » 9 months ago, # | 0 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.  » 9 months ago, # | 0 I'm so bad, lmao, I can't solve any of these problems :/  » 8 months ago, # | 0 Hello, why this solution for A doesn't work? It's absolutely clear and using two points concept. First we sort the array, then go from end to start on array B and count how much elements can we place from array A to the place in array B? Thanks for future replies!t = int(input()) for _ in range(t): n = int(input()) a, b = list(map(int, input().split())), list(map(int, input().split())) a.sort() b.sort() j = n — 1 cnt = 1 for i in range(n — 1, -1, -1): while j — 1 >= 0 and a[j — 1] > b[i]: j -= 1 cnt *= (n — j — (n — i — 1)) print(cnt)  » 8 months ago, # | 0 Problem D2 can be solved using simple sorting instead of a sparse table. But the time complexity remains O(nlogn). Here is the solution https://mirror.codeforces.com/contest/1828/submission/211818091  » 5 months ago, # | 0 int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);/////////////////////////////////////////////////ll t; cin>>t; while(t--) { ll n; cin>>n; vector a(n); vector b(n); for(int i = 0; i < n; i++) cin>>a[i]; for(int i = 0; i < n; i++) cin>>b[i]; unordered_map m; sort(a.begin(), a.end()); sort(b.begin(), b.end()); int i = n-1, j = n-1; while(j >= 0) { while(i > 0 and a[i] > b[j]) { i--; } if(a[i] <= b[j]) i++; m[b[j]] = n-i; j--; } // for(auto it : m) { // cout<second; ll dif = 1; for(int i = n-2; i >= 0; i--) { ll num = m.find(b[i])->second - dif; // cout<<"num "<  » 4 months ago, # | ← Rev. 2 → 0 Div1-C can also be solved in$O(n\log^2{n})$using dsu.This solution doesn't require the lemma of the editorial, and is based on the fact that if the prefix of any even palindrome is an even palindrome, then the suffix can always be divided into disjoint even palindromes.(note to self: write complete explanation later)Implementation: link  » 7 weeks ago, # | 0 Cam somebody explain the intuition behind 1828B? I am not able to understand how calculating GCD is the answer. Part about how to find the right pos is obvious but I am not able to understand GCD part. •  » » 6 weeks ago, # ^ | 0 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.So, a valid value of$k$must be a divisor of the difference between all the initial position ($i$) and the final position ($p_i$) of each element, which is$|i - p_i|$. The largest value of$k$is thus the greatest common divisor (GCD!) of$|1 - p_1|, |2 - p_2|, \dots, |n - p_n|\$.