Find the median

題目鏈接：

https://ac.nowcoder.com/acm/contest/887/E

題目描述

Let median of some array be the number which would stand in the middle of this array if it was sorted beforehand. If the array has even length let median be smallest of of two middle elements. For example, median of the array \([10,3,2,3,2]\) is 3 (i.e. \([2,2,\underline{3},3,10]\)). Median of the array [1,5,8,1] is 1 (i.e. \([1,\underline{1},5,8]\)).

At first, you're given an empty sequence. There are N operations. The i-th operation contains two integers \(L_i\) and \(R_i\). This means that adding \(R_i-L_i+1\) integers \(L_i, L_i+1, ... , R_i\) into the sequence. After each operation, you need to find the median of the sequence.

輸入描述:

The first line of the input contains an integer \(N\ (1 \leq N \leq 400000)\) as described above.

The next two lines each contains six integers in the following format, respectively:

• \(X_1\ X_2\ A_1\ B_1\ C_1\ M_1\)
• \(Y_1\ Y_2\ A_2\ B_2\ C_2\ M_2\)

These values are used to generate \(L_i, R_i\) as follows:

We define:

• \(X_i = (A_1 \times X_{i-1} + B_1 \times X_{i-2} + C_1)\ module\ M_1\), for \(i= 3\ to\ N\)
• \(Y_i = (A_2 \times Y_{i-1} + B_2 \times Y_{i-2} + C_2)\ module\ M_2\), for \(i = 3\ to\ N\)

We also define:

• \(L_i = min(X_i, Y_i) + 1\), for \(i = 1\ to\ N\).
• \(R_i = max(X_i, Y_i) + 1\), for \(i = 1\ to\ N\).

Limits:
\(1 \leq N \leq 400000\)
\(0 \leq A_1 < M_1\)
\(0 \leq A_2 < M_2\)
\(0 \leq B_1 < M_1\)
\(0 \leq B_2 < M_2\)
\(0 \leq C_1 < M_1\)
\(0 \leq C_2 < M_2\)
\(0 \leq X_1 < M_1\)
\(0 \leq X_2 < M_1\)
\(0 \leq Y_1 < M_2\)
\(0 \leq Y_2 < M_2\)
\(1 \leq M_1 \leq 10^9\)
\(1 \leq M_2 \leq 10^9\)

輸出描述:

You should output lines. Each line contains an integer means the median.

樣例輸入

5
3 1 4 1 5 9
2 7 1 8 2 9

樣例輸出

3
4
5
4
5

說明

L = [3, 2 ,4, 1, 7]
R = [4, 8, 8, 3, 9]

題意

給你一個(gè)空序列,\(n\)條指令，每次給你\(l,r\) ,表示向序列中加入\(l,l+1,\cdots,r\) 總共\(r-l+1\)個(gè)元素，每條指令后輸入序列的中位數(shù)。

\(n\)條指令按題目所給的方法生成。

題解

這題如果不用離散的話，直接上權(quán)值線段樹，這里著重講一下離散的問題。

離散時(shí)我開始覺得很不能理解的地方：

什么時(shí)候左閉右開

什么時(shí)候右端點(diǎn)＋１

什么時(shí)候右端點(diǎn)－１

我們不妨先來想一組數(shù)據(jù)：插入\((1,1) \ \ (1,5) \ \ (5,5)\)

如果按照普通離散是不是離散后就是\((1,1) \ \ (1,2) \ \ (2,2)\)

再用普通線段樹，那么會(huì)發(fā)現(xiàn)\((1,1)+(2,2)\)和\((1,2)\)效果一樣，也就是中間的點(diǎn)沒了，為什么呢？

就是因?yàn)殡x散后我們沒法判斷某個(gè)點(diǎn)是左端點(diǎn)還是右端點(diǎn)還是中間點(diǎn)，導(dǎo)致兩點(diǎn)間隙無法判斷。

我的處理方法：

將離散的點(diǎn)連起來變成求線段長(zhǎng)度，比如求\((1,5)\)改成求\((1,6)\)這條線段的長(zhǎng)度\((\)都是\(5)\)

線段樹每個(gè)節(jié)點(diǎn)\((l,r)\),實(shí)際管理區(qū)間是\((l,r+1)\)

加入線段時(shí)，記得右端－１，因?yàn)榫€段樹會(huì)往右多管理一個(gè)點(diǎn)

這樣\((1,1) \ \ (1,5) \ \ (5,5)\) 就變成了\((1,2)\ \ (1,6)\ \ (5,6)\)，離散后再變成\((1,2)\ \ (1,4) \ \ (3,4)\)，記得加入時(shí)右端點(diǎn)－１，即\((1,1)\ \ (1,3)\ \ (3,3)\)這幾個(gè)區(qū)間權(quán)值＋１。

\(ps:\) 這種區(qū)間覆蓋問題很多都是要考慮端點(diǎn)的問題。

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define INF 0x7f7f7f7f #define N 800050 template<typename T>void read(T&x) {ll k=0; char c=getchar();x=0;while(!isdigit(c)&&c!=EOF)k^=c=='-',c=getchar();if (c==EOF)exit(0);while(isdigit(c))x=x*10+c-'0',c=getchar();x=k?-x:x; } void read_char(char &c) {while(!isalpha(c=getchar())&&c!=EOF);} ll n,num; ll X[N],Y[N],kth[N]; struct Query{ll l,r;}que[N]; struct Tree{ll l,r,lazy,sum;}tr[N<<2]; void push_up(ll x) {ll len=kth[tr[x].r+1]-kth[tr[x].l];if (tr[x].l==tr[x].r)tr[x].sum=0;else tr[x].sum=tr[x<<1].sum+tr[x<<1|1].sum;tr[x].sum+=tr[x].lazy*len; } void push_down(ll x) {Tree &a=tr[x<<1],&b=tr[x<<1|1];a.lazy+=tr[x].lazy;b.lazy+=tr[x].lazy;tr[x].lazy=0;push_up(x<<1);push_up(x<<1|1); } void bt(ll x,ll l,ll r) {tr[x].lazy=tr[x].sum=0; tr[x].l=l; tr[x].r=r; if (l==r)return;ll mid=(l+r)>>1;bt(x<<1,l,mid);bt(x<<1|1,mid+1,r); } void change(ll x,ll l,ll r) {if (l<=tr[x].l&&tr[x].r<=r){tr[x].lazy++;push_up(x);return;}ll mid=(tr[x].l+tr[x].r)>>1;if (l<=mid)change(x<<1,l,r);if (mid<r)change(x<<1|1,l,r);push_up(x); } ll query(ll x,ll k) {if (tr[x].l==tr[x].r)return kth[tr[x].l]+(k-1)/tr[x].lazy;push_down(x);ll ls=tr[x<<1].sum;if (ls<k)return query(x<<1|1,k-ls);else return query(x<<1,k); } void work() {ll A1,B1,C1,A2,B2,C2,M1,M2,sum=0;read(n);read(X[1]); read(X[2]); read(A1); read(B1); read(C1); read(M1);read(Y[1]); read(Y[2]); read(A2); read(B2); read(C2); read(M2);for(ll i=3;i<=n;i++)X[i]=(A1*X[i-1]+B1*X[i-2]+C1)%M1;for(ll i=3;i<=n;i++)Y[i]=(A2*Y[i-1]+B2*Y[i-2]+C2)%M2;for(ll i=1;i<=n;i++){que[i].l=min(X[i],Y[i])+1;que[i].r=max(X[i],Y[i])+2;kth[++num]=que[i].l;kth[++num]=que[i].r;}sort(kth+1,kth+num+1);num=unique(kth+1,kth+num+1)-kth-1;bt(1,1,num);for(ll i=1;i<=n;i++){ll l=lower_bound(kth+1,kth+num+1,que[i].l)-kth;ll r=lower_bound(kth+1,kth+num+1,que[i].r)-kth;sum+=que[i].r-que[i].l;change(1,l,r-1);printf("%lld\n",query(1,(sum+1)/2));}} signed main() { #ifndef ONLINE_JUDGEfreopen("aa.in","r",stdin); #endifwork(); }

轉(zhuǎn)載于:https://www.cnblogs.com/mmmqqdd/p/11514991.html

總結(jié)

以上是生活随笔為你收集整理的2019牛客多校第七场E Find the median 权值线段树＋离散化的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。