首页 > 代码库 > BZOJ2653 middle
BZOJ2653 middle
题目链接：BZOJ2653
解题报告：
很久以前想拿来做联赛模拟的一道题==
然而因为太水了换掉了233333
显然如果我们枚举区间端点的话，复杂度太高。
考虑换个思路：我们对于每个询问二分一个答案x，表示序列中第x小的数，表示看这个数是否可行，可以把这个区间内第x小的数，到第n小的数（最大的数）标为1，最小的数到第x-1小的数的标为-1，如果区间和大于等于0那么可行，否则不可行。
我们从简单处入手，考虑如果只做一次怎么做。
因为我们由原序列和x的关系得到了一个由-1和1所构成的序列（以下称为P序列），我们想知道此时x是否可行，也就是说我们需要在题目要求的左端点区间[l1,r1]找到一个左端点，右端点区间[l2,r2]找到一个右端点，然后使得这一段的和大于等于0，就说明x可行。
也就是说对于序列a，我们如果有∑ai（l<=i<=r，且l属于[l1,r1]，r属于[l2,r2]）大于等于0即可说明可行。
那么我们是不是一定要枚举左右端点呢？
其实不需要，因为我们只需要算出∑ai（l<=i<=r，且l属于[l1,r1]，r属于[l2,r2]）最大的时候是否大于等于0就可以完成判定了。
这也就等价于，对于[l1,r2]求最大子段和，且必须包含[r1+1,l2-1]这一段。
求法很简单，就是求[l1,r1]的最大后缀子段和，和[l2,r2]的最大前缀子段和，加上[r1+1,l2-1]的总和即可。
以上用一个线段树就可以搞定，线段树维护区间的和、区间最大后缀子段和、区间最大前缀子段和。
这是一次的操作，那么多次的呢？
其实关键就在于对于每次二分不同的x的时候，是不是都要根据x的值重构一遍P序列和新的线段树？
每次暴力修改并且建立显然不可行，就必须另辟蹊径。
如果我们已经给定了一个比x-1的P序列的情况，那么若想将其表示为x的情况，则只需要把x-1在x的P序列中标为-1就可以了。
也就是说，我们需要充分运用以前的修改，不需要每次重新修改。
所以我们希望一个数据结构来帮助我们复制一份并且每次修改一段，显然主席树可以胜任。
第i棵主席树维护第i小的数的把所有数表示成1、-1的情况，并且维护前缀最大值、后缀最大值、区间和。
相当于是有n棵线段树，每棵都维护的是一个P序列。
这样一来我们可以排序之后，从1到n构主席树，构i的主席树的时候每次只把i-1在i的主席树中对应的位置改成-1，所以每次在主席树上需要修改一条链。
这样就完美解决了这个问题了，细节有一点多，写的时候注意一下。
时间复杂度：O(n log n+m log n log n)
直接贴一年前的代码好了...
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
const int MAXN = 20011;
const int inf = (1<<30);
int n,ans,cnt,daan,jizhu;
int wen[5],zheng,ql,qr;
int root[MAXN];//每棵主席树的根的编号
struct node{
int lmax,rmax,sum;
int lson,rson;
}a[MAXN*20],tmp,yuan;
struct Num{
int id,val;
}b[MAXN];
inline int getint()
{
int w=0,q=0;
char c=getchar();
while((c<‘0‘ || c>‘9‘) && c!=‘-‘) c=getchar();
if (c==‘-‘) q=1, c=getchar();
while (c>=‘0‘ && c<=‘9‘) w=w*10+c-‘0‘, c=getchar();
return q ? -w : w;
}
inline void update(int root){
a[root].sum=a[a[root].lson].sum+a[a[root].rson].sum;
a[root].lmax=max(a[a[root].lson].lmax, a[a[root].lson].sum+a[a[root].rson].lmax );
a[root].rmax=max(a[a[root].rson].rmax, a[a[root].rson].sum+a[a[root].lson].rmax );
}
inline void build(int l,int r,int &now){
cnt++; now=cnt;
if(l==r) {
a[now].lmax=a[now].rmax=a[now].sum=1;
return ;
}
int mid=(l+r)/2;
build(l,mid,a[now].lson); build(mid+1,r,a[now].rson);
update(now);
}
inline void insert(int last,int pos,int l,int r,int &now){
cnt++; now=cnt;
a[now]=a[last];
if(l==r) {
a[now].lmax=a[now].rmax=a[now].sum=-1;
return ;
}
int mid=(l+r)/2;
if(pos<=mid) insert(a[last].lson,pos,l,mid,a[now].lson);
else insert(a[last].rson,pos,mid+1,r,a[now].rson);
update(now);
}
inline bool cmp(Num q,Num qq){ return q.val<qq.val; }
inline node hebing(node q,node qq){//合并
node xin=yuan;
xin.rmax=max(qq.rmax,qq.sum+q.rmax);
xin.lmax=max(q.lmax,q.sum+qq.lmax);
xin.sum=q.sum+qq.sum;//!!!!!!!
return xin;
}
inline void query_lmax(int root,int l,int r){//查询前缀最大值
if(ql<=l && r<=qr) {
if(!zheng) tmp=a[root],zheng=1;
else tmp=hebing(tmp,a[root]);
return ;
}
int mid=(l+r)/2;
if(ql<=mid) query_lmax(a[root].lson,l,mid);
if(qr>mid) query_lmax(a[root].rson,mid+1,r);
}
inline void query_rmax(int root,int l,int r){//查询后缀最大值
if(ql<=l && r<=qr) {
if(!zheng) tmp=a[root],zheng=1;
else tmp=hebing(tmp,a[root]);
return ;
}
int mid=(l+r)/2;
if(ql<=mid) query_rmax(a[root].lson,l,mid);
if(qr>mid) query_rmax(a[root].rson,mid+1,r);
}
inline void query_sum(int root,int l,int r){
if(ql>qr) return ;
if(ql<=l && r<=qr) {
daan+=a[root].sum; return ;
}
int mid=(l+r)/2;
if(ql<=mid) query_sum(a[root].lson,l,mid);
if(qr>mid) query_sum(a[root].rson,mid+1,r);
}
inline bool check(int x){
ql=wen[1]; qr=wen[2]; zheng=0; tmp=yuan;
query_rmax(root[x],1,n); int nowl=tmp.rmax;
ql=wen[3]; qr=wen[4]; zheng=0; tmp=yuan;
query_lmax(root[x],1,n); int nowr=tmp.lmax;
ql=wen[2]+1; qr=wen[3]-1;
daan=0; query_sum(root[x],1,n);//中间一段一定会选入区间
int li=nowl+nowr+daan; if(li>=0) return true;
return false;
}
inline void work(){
n=getint(); for(int i=1;i<=n;i++) b[i].val=getint(),b[i].id=i;
sort(b+1,b+n+1,cmp);
build(1,n,root[1]);//初始均为1
for(int i=2;i<=n;i++) insert(root[i-1],b[i-1].id,1,n,root[i]);//把前一个设为-1
int q=getint(); int l,r;int mid;
while(q--) {
for(int i=1;i<=4;i++) wen[i]=getint()+1;
//for(int i=1;i<=4;i++) wen[i]+=jizhu,wen[i]%=n,wen[i]++;
//sort(wen+1,wen+4+1);
l=1; r=n;
while(l<=r) {
mid=(l+r)/2;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
jizhu=b[ans].val;
printf("%d\n",jizhu);
}
}
int main()
{
work();
return 0;
}
BZOJ2653 middle