[bzoj5052][Codeforces765F][主席树]繁忙的财政官/Souvenirs_综合

Description

伟大的王朝即将在下个月迎来奥西利斯节，这是整个埃及最盛大的节日。胡夫非常重视这次盛会，所以他经常向财
政官询问国家的财政事项。但是同时，有成堆的文件等待着财政官检视，为此他忙得不可开交。现在他正处于崩溃
的边缘（辞职申请都写好了）。他听说你这个异乡人拥有神奇的能力，于是带着丰厚的礼品来带了你的居所，看样
子你是没法拒绝他了…….财政官的工作很简单，但是国王的视察很繁琐（官僚主义嘛），所以他想请你帮他应付
国王的询问。现在按时间先后顺序给你n份物资申请，每份物资申请有一个种类值ai，种类值越相近的申请所申请
的物资越相近，现在国王想知道从时间L到时间R以内最相近的两份申请的差异值为多少，如果在他的接受范围内他
就会同意这两份申请（相似的物资较容易同时准备），他一共会有m次询问，现在请你帮助繁忙的财政官完成这项任务。

Input

第一行包括两个整数n，m代表文件数及询问数。第二行包括n个整数a1，a2，a3，a4……an代表文件的种类。
接下来m行，每行两个整数L,R代表询问的时间段。保证L<R。 n <= 100000，m <= 100000. 对于没有说明ai的数据
保证1<=ai <= 1e9，且保证ai互不相同。

Output

对于每个询问，输出最相近的两份文件的种类值的差异的绝对值。

Sample Input

3 2

1 3 2

1 2

1 3

Sample Output

2

1

题解

我居然看到了我曾经想出的题…
~~还能把我的n值域做法打成sb的题~~
哦cf那里m的输入要换一下…上界也要开大一点不过总体都是相似的
不妨考虑每个点与哪些点可能成为答案吧
分后面一个点与前面一个点的大小关系讨论，此处仅讨论大于的，小于同理
对于当前点 $i$ ，先找到后面第一个比他大的点 $j$ ，显然他们可能成为答案
然后我们再去找 $j$ 后面可能成为答案的点 $k$ ，显然 $a_i<a_k<a_j$
有一个很有用的东西：我们需要满足 $a_k-a_i<=a_j-a_k$ ，否则显然用 $a_j,a_k)$ 作为答案会更优并且覆盖了 $a_i,a_k)$ 的所有情况
不难发现每次值域至少缩小了一半，所以一个点后有用的点仅有 $l o g$ 个
小于的同理
故总合法点数仅为 $n l o g n$
剩余是简单问题
em…感觉自己还是很容易忘记去做一些最优化的处理，很容易导致自己走向自闭数据结构的死路
脑子还是要清醒点啊

bzoj的

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{
    int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
    x=x*10+ch-'0';ch=getchar();}return x*f;
}
int stack[20];
inline void write(int x)
{
    if(x<0){
    putchar('-');x=-x;}if(!x){
    putchar('0');return;}int top=0;while(x)stack[++top]=x%10,x/=10;while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){
    write(x);putchar(' ');}
inline void pr2(int x){
    write(x);putchar('\n');}
const int INF=(1<<31-1);
const int MAXN=100005;
const int MAXM=300005;
int a[MAXN],ca[MAXN],id[MAXN],n,m;
int answer[MAXM];int rt[MAXN];
struct chairmantree
{
    int c[MAXN*30],lc[MAXN*30],rc[MAXN*30],tot;void add(int &now,int l,int r,int p){
    if(!now)now=++tot;c[now]++;if(l==r)return ;int mid=(l+r)/2;if(p<=mid)add(lc[now],l,mid,p);else add(rc[now],mid+1,r,p);}void merge(int &x,int y){
    if(x==0){
    x=y;return ;}if(y==0)return ;c[x]+=c[y];merge(lc[x],lc[y]);merge(rc[x],rc[y]);}int findrk(int x,int y,int l,int r,int p){
    if(!(c[x]-c[y]))return 0;if(l==r)return c[x]-c[y];int mid=(l+r)/2;if(p<=mid)return findrk(lc[x],lc[y],l,mid,p);else return findrk(rc[x],rc[y],mid+1,r,p)+c[lc[x]]-c[lc[y]];}int findpos(int x,int y,int l,int r,int K){
    if(c[x]-c[y]<K)return -1;if(l==r)return l;int mid=(l+r)/2;if(c[lc[x]]-c[lc[y]]>=K)return findpos(lc[x],lc[y],l,mid,K);else return findpos(rc[x],rc[y],mid+1,r,K-(c[lc[x]]-c[lc[y]]));}int findnxt(int x,int y,int u){
    int cal=findrk(rt[x],rt[y-1],1,n,u);return findpos(rt[x],rt[y-1],1,n,cal+1);}
}cht;
vector<pii> vec[MAXN],ask[MAXN];
int sta1[MAXN],sta2[MAXN],tp1,tp2;int s[MAXN];
int lowbit(int x){
    return x&-x;}
void modify(int x,int c){
    for(;x<=n;x+=lowbit(x))s[x]=min(s[x],c);}
int qry(int x){
    int ret=INF;for(;x>=1;x-=lowbit(x))ret=min(ret,s[x]);return ret;}
int vis[MAXN];
int main()
{
    
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);memset(s,63,sizeof(s));n=read();m=read();for(int i=1;i<=n;i++)a[i]=ca[i]=read();sort(ca+1,ca+1+n);int ln=unique(ca+1,ca+1+n)-(ca+1);for(int i=1;i<=n;i++)id[i]=lower_bound(ca+1,ca+1+ln,a[i])-(ca);for(int i=1;i<=n;i++)cht.add(rt[id[i]],1,n,i);for(int i=1;i<=n;i++)cht.merge(rt[i],rt[i-1]);sta1[tp1=1]=sta2[tp2=1]=n;LL cnt=0;for(int i=n-1;i>=1;i--){
    int nx1=-1,nx2=-1;while(tp1&&a[sta1[tp1]]>a[i])tp1--;if(tp1)nx1=sta1[tp1];sta1[++tp1]=i;while(tp2&&a[sta2[tp2]]<a[i])tp2--;if(tp2)nx2=sta2[tp2];sta2[++tp2]=i;while(nx1!=-1){
    vis[i]++;int cal=a[i]-a[nx1];
// printf("NO1 %d %d %d\n",i,nx1,cal);vec[nx1].push_back(mp(i,cal));int down=a[i]-cal/2;if(cal==0)break;int pos=lower_bound(ca+1,ca+1+ln,down)-ca;nx1=cht.findnxt(id[i],pos,nx1);}while(nx2!=-1){
    vis[i]++;
// printf("%d %lld\n",i,++cnt);int cal=a[nx2]-a[i];
// printf("NO2 %d %d %d\n",i,nx2,cal);vec[nx2].push_back(mp(i,cal));int up=a[i]+cal/2;if(cal==0)break;int pos=upper_bound(ca+1,ca+1+ln,up)-(ca+1);nx2=cht.findnxt(pos,id[i],nx2);}
// printf("%d %d\n",i,vis[i]);}for(int i=1;i<=m;i++){
    int x=read(),y=read();ask[y].push_back(mp(x,i));}for(int i=1;i<=n;i++){
    for(int j=0;j<(int)vec[i].size();j++){
    int u=vec[i][j].first,cal=vec[i][j].second;modify(n-u+1,cal);}for(int j=0;j<(int)ask[i].size();j++){
    int l=ask[i][j].first,op=ask[i][j].second;answer[op]=qry(n-l+1);}}for(int i=1;i<=m;i++)pr2(answer[i]);return 0;
}