题目大意：
给你一个数列，问区间[l,r]内与k最接近的数与k的差是多少。
思路：
将数列中的数和询问的数先从小到大排序，
从小到大枚举每个数，如果是数列上的，就加到线段树中，
如果是询问中的，就在线段树上查找区间最大值，
这样就找到了区间中小于等于这个数的最大值。
反过来也一样。
一个最大值、一个最小值，对于询问的数作差，取min即可。
比原来的主席树算法不知道妙到哪里去了。
主席树加了离散化以后应该能过，不过我的程序一直没过，然而虞皓翔同样是主席树的程序可以随便过。
大概是我写得比较烂吧。
#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
#include<functional> inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
} const int inf=0x7fffffff;
const int N=; struct Num {
int val,pos,l,r,id;
bool operator < (const Num &another) const {
if(val<another.val) return true;
if(val>another.val) return false;
return pos;
}
bool operator > (const Num &another) const {
if(val>another.val) return true;
if(val<another.val) return false;
return pos;
}
};
std::vector<Num> v; class SegmentTree {
#define _left <<1
#define _right <<1|1
private:
int val[N<<];
void push_up(const int &p,const bool &cmp) {
val[p]=cmp?std::max(val[p _left],val[p _right]):std::min(val[p _left],val[p _right]);
}
public:
void reset(const int &x) {
std::fill(&val[],&val[N<<],x);
}
void modify(const int &p,const int &b,const int &e,const int &x,const int &v,const bool &cmp) {
if(b==e) {
val[p]=v;
return;
}
const int mid=(b+e)>>;
if(x<=mid) modify(p _left,b,mid,x,v,cmp);
if(x>mid) modify(p _right,mid+,e,x,v,cmp);
push_up(p,cmp);
}
int query(const int &p,const int &b,const int &e,const int &l,const int &r,const bool &cmp) {
if(b==l&&e==r) {
return val[p];
}
const int mid=(b+e)>>;
int ret=cmp?-:inf;
if(l<=mid) ret=cmp?std::max(ret,query(p _left,b,mid,l,std::min(mid,r),cmp)):std::min(ret,query(p _left,b,mid,l,std::min(mid,r),cmp));
if(r>mid) ret=cmp?std::max(ret,query(p _right,mid+,e,std::max(mid+,l),r,cmp)):std::min(ret,query(p _right,mid+,e,std::max(mid+,l),r,cmp));
return ret;
}
#undef _left
#undef _right
};
SegmentTree t; int ans[N]; int main() {
int T=getint();
for(register int i=;i<=T;i++) {
printf("Case #%d:\n",i);
const int n=getint(),q=getint();
v.clear();
for(register int i=;i<=n;i++) {
v.push_back((Num){getint(),i,,,});
}
for(register int i=;i<q;i++) {
const int l=getint(),r=getint(),k=getint();
v.push_back((Num){k,,l,r,i});
}
std::fill(&ans[],&ans[q],inf);
t.reset(-);
std::sort(v.begin(),v.end(),std::less<Num>());
for(register std::vector<Num>::iterator it=v.begin();it!=v.end();it++) {
if(it->pos) {
t.modify(,,n,it->pos,it->val,true);
} else {
const int tmp=t.query(,,n,it->l,it->r,true);
if(tmp!=-) ans[it->id]=std::min(ans[it->id],std::abs(tmp-it->val));
}
}
t.reset(inf);
std::sort(v.begin(),v.end(),std::greater<Num>());
for(register std::vector<Num>::iterator it=v.begin();it!=v.end();it++) {
if(it->pos) {
t.modify(,,n,it->pos,it->val,false);
} else {
const int tmp=t.query(,,n,it->l,it->r,false);
if(tmp!=inf) ans[it->id]=std::min(ans[it->id],std::abs(tmp-it->val));
}
}
for(register int i=;i<q;i++) {
printf("%d\n",ans[i]);
}
}
return ;
}
原来也写过一个主席树的写法，然而复杂度不是很优秀，一直过不了。
#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
const int inf=0x7fffffff;
const int N=;
int size;
class FotileTree {
private:
struct Node {
int left,right,val;
};
Node nd[N*];
int sz,newNode(const int &p) {
sz++;
nd[sz]=nd[p];
return sz;
}
public:
int root[N];
void reset() {
sz=;
}
int modify(const int &p,const int &b,const int &e,const int &x) {
int new_p=newNode(p);
nd[new_p].val++;
if(b==e) return new_p;
const int mid=(b+e)>>;
if(x<=mid) nd[new_p].left=modify(nd[p].left,b,mid,x);
if(x>mid) nd[new_p].right=modify(nd[p].right,mid+,e,x);
return new_p;
}
int queryleq(const int &p1,const int &p2,const int &b,const int &e,const int &x) const {
if(!(nd[p2].val-nd[p1].val)) return size-;
if(b==e) return e;
const int mid=(b+e)>>;
if(x<=mid) return queryleq(nd[p1].left,nd[p2].left,b,mid,x);
int ret;
if((ret=queryleq(nd[p1].right,nd[p2].right,mid+,e,x))!=size-) return ret;
if((ret=queryleq(nd[p1].left,nd[p2].left,b,mid,x))!=size-) return ret;
return size-;
}
int querygeq(const int &p1,const int &p2,const int &b,const int &e,const int &x) const {
if(!(nd[p2].val-nd[p1].val)) return size-;
if(b==e) return b;
const int mid=(b+e)>>;
if(x>mid) return querygeq(nd[p1].right,nd[p2].right,mid+,e,x);
int ret;
if((ret=querygeq(nd[p1].left,nd[p2].left,b,mid,x))!=size-) return ret;
if((ret=querygeq(nd[p1].right,nd[p2].right,mid+,e,x))!=size-) return ret;
return size-;
}
};
FotileTree t;
int a[N],l[N],r[N],x[N],b[N+N];
int main() {
int T=getint();
for(register int i=;i<=T;i++) {
printf("Case #%d:\n",i);
const int n=getint(),q=getint();
b[]=inf;
for(register int i=;i<=n;i++) {
b[i]=a[i]=getint();
}
for(register int i=;i<=q;i++) {
l[i]=getint();
r[i]=getint();
b[n+i]=x[i]=getint();
}
std::sort(&b[],&b[n+q+]);
size=std::unique(&b[],&b[n+q+])-b;
for(register int i=;i<=n;i++) {
const int id=std::lower_bound(&b[],&b[size],a[i])-b;
t.root[i]=t.modify(t.root[i-],,size-,id);
}
for(register int i=;i<=q;i++) {
const int id=std::lower_bound(&b[],&b[size],x[i])-b;
const int leq=b[t.queryleq(t.root[l[i]-],t.root[r[i]],,size-,id)];
const int geq=b[t.querygeq(t.root[l[i]-],t.root[r[i]],,size-,id)];
printf("%d\n",std::min(std::abs(x[i]-leq),std::abs(x[i]-geq)));
}
}
return ;
}