2019牛客多校第七場E Find the median 權值線段樹＋離散化

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]

題意

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

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

題解

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

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

1. 什么時候左閉右開

2. 什么時候右端點＋１

3. 什么時候右端點－１

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

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

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

就是因為離散后我們沒法判斷某個點是左端點還是右端點還是中間點，導致兩點間隙無法判斷。

我的處理方法：

1. 將離散的點連起來變成求線段長度，比如求\((1,5)\)改成求\((1,6)\)這條線段的長度\((\)都是\(5)\)
2. 線段樹每個節點\((l,r)\),實際管理區間是\((l,r+1)\)
3. 加入線段時，記得右端－１，因為線段樹會往右多管理一個點

這樣\((1,1) \ \ (1,5) \ \ (5,5)\) 就變成了\((1,2)\ \ (1,6)\ \ (5,6)\)，離散后再變成\((1,2)\ \ (1,4) \ \ (3,4)\)，記得加入時右端點－１，即\((1,1)\ \ (1,3)\ \ (3,3)\)這幾個區間權值＋１。

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

代碼

#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();
}