设计一个网站页面需要多少钱,wordpress 畅言,网络推广都有哪些渠道,气动喷枪网站建设题意
小 X 有 n n n 个正整数二元组 ( a i , b i ) ( 1 ≤ i ≤ n ) (a_i, b_i) (1 \leq i \leq n) (ai,bi)(1≤i≤n)。他将会维护初始为空的可重集 S S S#xff0c;并对其进行 n n n 轮操作。第 i ( 1 ≤ i ≤ n ) i (1 \leq i \leq n) i(1≤i≤n) 轮操作中#…题意
小 X 有 n n n 个正整数二元组 ( a i , b i ) ( 1 ≤ i ≤ n ) (a_i, b_i) (1 \leq i \leq n) (ai,bi)(1≤i≤n)。他将会维护初始为空的可重集 S S S并对其进行 n n n 轮操作。第 i ( 1 ≤ i ≤ n ) i (1 \leq i \leq n) i(1≤i≤n) 轮操作中他会在 S S S 中加入 a i a_i ai 个 b i b_i bi。
设 m ∑ i 1 n a i m \sum \limits_{i1}^{n} a_i mi1∑nai在所有操作结束后小 X 会得到一个包含 m m m 个正整数的可重集 S S S。最后他会计算 S S S 的中位数即 S S S 中第 ⌊ m 1 2 ⌋ \left\lfloor \frac{m1}{2} \right\rfloor ⌊2m1⌋ 小的数作为他的幸运数字。
想知道小 X 幸运数字的小 Y 不知道这 n n n 个二元组的具体数值是多少但她得知了每个数的范围。具体地对于每个 1 ≤ i ≤ n 1 \leq i \leq n 1≤i≤n小 Y 知道 a i ∈ [ l i , 1 , r i , 1 ] a_i \in [l_{i,1}, r_{i,1}] ai∈[li,1,ri,1] 且 b i ∈ [ l i , 2 , r i , 2 ] b_i \in [l_{i,2}, r_{i,2}] bi∈[li,2,ri,2]。
小 Y 想知道在满足以上条件的情况下有多少个数可能成为小 X 的幸运数字。
设 ∑ n \sum n ∑n 为单个测试点内所有测试数据的 n n n 的和。对于所有测试点 1 ≤ T ≤ 400 1 \leq T \leq 400 1≤T≤400 1 ≤ n ≤ 2 × 1 0 5 1 \leq n \leq 2 \times 10^5 1≤n≤2×105 1 ≤ ∑ n ≤ 6 × 1 0 5 1 \leq \sum n \leq 6 \times 10^5 1≤∑n≤6×105 ∀ 1 ≤ i ≤ n \forall 1 \leq i \leq n ∀1≤i≤n 1 ≤ l i , 1 ≤ r i , 1 ≤ 1 0 9 1 \leq l_{i,1} \leq r_{i,1} \leq 10^9 1≤li,1≤ri,1≤109 1 ≤ l i , 2 ≤ r i , 2 ≤ 1 0 9 1 \leq l_{i,2} \leq r_{i,2} \leq 10^9 1≤li,2≤ri,2≤109。
思路
假如有一个数列一个值 m m m 的个数为 b b b比它小的数的个数为 a a a比它大的数的个数为 c c c对于中间位置 m i d ⌊ a b c 1 2 ⌋ mid\left \lfloor \frac{abc1}{2} \right \rfloor mid⌊2abc1⌋ m i d ≤ a mid\le a mid≤a那么中间位置在小于 m m m 的数中中位数小于 m m m a m i d ≤ a b amid\le ab amid≤ab那么中间位置在一堆 m m m 中中位数就是 m m m m i d a b midab midab那么中间位置在大于 m m m 的数中中位数大于 m m m。
那么当我们知道 m m m 的个数、小于和大于 m m m 的数的个数就可以知道 m m m 是否为中位数。将这样的操作集成为函数 M i d ( a , b , c ) \rm {Mid}(a,b,c) Mid(a,b,c)三种类型分别为 − 1 , 0 , 1 -1,0,1 −1,0,1。
但是题目中给的是个数的区间那要怎么办呢
考虑从题目给的“个数区间”下手如果可以维护两对区间小于 m m m 的数的个数区间为 [ l l e s , r l e s ] [l_{les},r_{les}] [lles,rles]大于 m m m 的数的个数区间为 [ l b i g , r b i g ] [l_{big},r_{big}] [lbig,rbig]。如果存在 Mid ( r l e s , c n t m , l b i g ) 0 \textup{Mid}(r_{les},cnt_m,l_{big})0 Mid(rles,cntm,lbig)0 或者 Mid ( l l e s , c n t m , r b i g ) \textup{Mid}(l_{les},cnt_m,r_{big}) Mid(lles,cntm,rbig)显然 m m m 为中位数。
还有两种情况就是小于 m m m 的数的个数取得少、大于 m m m 的数的个数取得多或者小于 m m m 的数的个数取得多、大于 m m m 的数的个数取得少。这两种情况的可行性体现于 Mid ( r l e s , c n t m , l b i g ) ≠ Mid ( l l e s , c n t m , r b i g ) \textup{Mid}(r_{les},cnt_m,l_{big})\neq\textup{Mid}(l_{les},cnt_m,r_{big}) Mid(rles,cntm,lbig)Mid(lles,cntm,rbig)
感性理解就是因为两端个数 a ∈ [ l l e s , r l e s ] a\in [l_{les},r_{les}] a∈[lles,rles]、 c ∈ [ l b i g , r b i g ] c\in[l_{big},r_{big}] c∈[lbig,rbig] a a a 和 c c c 可以取各自区间的任意一个数而“不等于”相当于存在 r l e s l b i g , l l e s r b i g r_{les}l_{big},l_{les}r_{big} rleslbig,llesrbig 或者 r l e s l b i g , l l e s r b i g r_{les}l_{big},l_{les}r_{big} rleslbig,llesrbig可以构造出 m m m 是中位数的情况。
ll Mid(ll a,ll b,ll c)
{ll mid(abc1)1;if(amid)return -1;if(abmid)return 0;return 1;
}
bool MID(ll m)
{ll c1Mid(les.r,m,big.l),c2Mid(les.l,m,big.r);return m(!c1||!c2||c1!c2);
}那只要能维护出上文的两对区间就可以了。
因为只求个数不需要知道具体哪一个而且注意到题目给的 l i , 1 , r i , 1 , l i , 2 , r i , 2 l_{i,1},r_{i,1},l_{i,2},r_{i,2} li,1,ri,1,li,2,ri,2 较大考虑离散化。然后套路地用两个动态数组分别季度左右端点的信息以便进行枚举过程中的信息修改。
枚举一堆 m m m 是否为中位数时贪心地取 m m m 的最多数量比较明显的贪心。
先初始化 l e s les les 和 b i g big big 区间然后直接在离散化的下标哪里扫过去在 m m m 和 m 1 m1 m1 的转移中使用先前维护的动态数组分别加入和删除当前中位数和不符合条件的中位数的信息从 b i g big big 区间删去当前中位数的信息在 l e s les les 区间中加入被弹出的数的信息。
答案就是相邻区间个数和。使用离散后的数组就可以计算。
一些细节和写法见代码
#includebits/stdc.h
using namespace std;
#define ll long long
const ll N1e69,inf0x7f7f7f7f;
int id,T,n;
struct term
{ll l,r;
}a[N],b[N],les,big;
ll bb[N];
ll Mid(ll a,ll b,ll c)
{ll mid(abc1)1;if(amid)return -1;if(abmid)return 0;return 1;
}
bool MID(ll m)
{ll c1Mid(les.r,m,big.l),c2Mid(les.l,m,big.r);return m(!c1||!c2||c1!c2);
}
vectorterms[N],t[N];
void clean(ll nn)
{for(int i1;inn;i)s[i].clear(),t[i].clear();
}
int main()
{scanf(%d%d,id,T);while(T--){scanf(%d,n);for(int i1;in;i){scanf(%lld%lld%lld%lld,a[i].l,a[i].r,b[i].l,b[i].r);bb[i*2-1]b[i].l;bb[i*2]b[i].r1;}sort(bb1,bb2*n1);ll nnunique(bb1,bb2*n1)-bb-1;les.lles.rbig.lbig.r0;//在中位数枚举的转移中动态维护两对区间//比中位数大/小的个数区间 //[les.l,les.r] cntmid [big.l,big.r]for(int i1;in;i){b[i].llower_bound(bb1,bbnn1,b[i].l)-bb;//离散化b[i].rlower_bound(bb1,bbnn1,b[i].r1)-bb;// coutb[i].l b[i].rendl;s[b[i].l].push_back(a[i]);//套路地只记录左右端点信息t[b[i].r].push_back(a[i]);big.la[i].l,big.ra[i].r;//big区间初始化}ll cntmid0,ret0;for(int i1;inn;i){for(auto x:s[i]){cntmidx.r;//加入中位数贪心的取数量更多的中位数 big.l-x.l,big.r-x.r;//从big区间删去}for(auto x:t[i]){cntmid-x.r;//弹出不符合条件的 les.lx.l,les.rx.r;//弹出的加入les区间 }// coutles.l les.r big.l big.rendl;if(MID(cntmid))retbb[i1]-bb[i];//这段区间都能是中位数统计个数}printf(%lld\n,ret);clean(nn);}return 0;
}
