下克上の天邪鬼

更好的阅读体验：

链接：https://pan.baidu.com/s/1o4smgWB19XF7_N_0SJ1R9Q ，提取码：dkq4 。

$\textsf{题目背景}$

天邪鬼是一种性格扭曲的妖怪。而作为幻想乡的不稳定分子的鬼人正邪，一天到晚脑子里总想着和其他人相反的事情。她天天想着把幻想乡整个翻转过来。

作为看热闹不嫌事大的天邪鬼，正邪非常喜欢看别的妖怪「下克上」。也就是更为弱小（实力上或者是地位上）的妖怪，战胜比他更强的妖怪。正邪拥有让任何事物都翻转过来程度的能力，因此下克上往往都是她主导的。

正邪选出了幻想乡的若干个妖精，希望在其中制造出「下克上」。一次「下克上」的精彩程度，就是两只妖精的能力之和。但是正邪的能力有限，如果两只妖怪实力相差悬殊，那就不大可能达成下克上了。又因为幻想乡的妖精实在是太多了，正邪计算不出怎么策划这场「下克上」。

于是正邪找到了你，希望你根据她的询问，分别找出一对妖精，使得「下克上」的程度最精彩。

$\textsf{题目描述}$

正邪选中了幻想乡的 $\mathit n$ 个妖精作为她的考虑对象，并按照次序排成了一列。妖精从左往右编号为 $1,2,\cdots n$ 。每个妖精的实力可以用一个正整数 $a_i$ 表示。

正邪一共会发起 $\mathit m$ 次询问，每次给出两个区间 $[l_1,r_1],[l_2,r_2]$ 。你需要选择一对妖精 $\mathrm (i,j)$ ，满足妖精 $\mathit i$ 在区间 $[l_1,r_1]$ 内，并且妖精 j 在区间 $[l_2,r_2]$ 内。正邪会试图让妖精 $\mathit j$ 击败妖精 $\mathit i$ 。为了防止实力悬殊，它们还满足：

$\left\lfloor \dfrac{a_i}{2} \right \rfloor \le a_j < a_i$

正邪希望你找到 $a_i + a_j$ 的最大值。特别地，如果不存在合法数对，你只要输出 $\mathrm 0$ 就行了。

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <stack> #include <queue> using namespace std; typedef long long ll; typedef pair<int,int> PII; const int N=2e7+10,V=1e9,mod=998244353; void add(int &a,ll b); int lc[N],rc[N],cnt[N],root[N],idx=0; int l1,l2,r2,r1,x,y,ans; void modify(int &a,int b,int l,int r,int x) { a=++idx; lc[a]=lc[b];rc[a]=rc[b];cnt[a]=cnt[b]+1; if(l==r)return ; int mid=l+r>>1; if(mid>=x)modify(lc[a],lc[b],l,mid,x); else modify(rc[a],rc[b],mid+1,r,x); } int quary(int x,int y,int l,int r,int t) { if(l>t||cnt[x]-cnt[y]==0)return -1; if(l==r)return l; int mid=l+r>>1,res=-1; if(t>mid) res=quary(rc[x],rc[y],mid+1,r,t); if(!~res)return quary(lc[x],lc[y],l,mid,t); return res; } void quary(int f,int t){if(f)x=quary(root[r1],root[l1-1],1,V,t);else y=quary(root[r2],root[l2-1],1,V,t);} int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { int num; scanf("%d",&num); modify(root[i],root[i-1],1,V,num); } for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&l1,&r1,&l2,&r2); quary(1,V); quary(0,V); while(1) { if(x==-1||y==-1||(y>=x/2&&y<x))break; if(y<x/2)quary(1,2*y+1); else quary(0,x-1); } if(x==-1||y==-1)ans=0; else ans=x+y; printf("%d\n",ans); } } void add(int &a,ll b){a=((a+b)%mod+mod)%mod;return;}

详情